Level 3. 디스크 컨트롤러 처음에 소요 시간으로만 정렬해 시작 시간을 빼 더하면 되는 줄 알았는데, 그게 아니어서 설명이 잘 돼 있는 이 블로그를 참고했다. 프로그래머스_힙(Heap)_디스크 컨트롤러 (JAVA) 문제 설명 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입 codevang.tistory.com 소요 시간으로 정렬하되, 현재까지 소요된 시간들을 더해 그 중에서도 수행할 수 있는 가장 빠른 시작 시간을 가진 작업을 선택해야 하는 문제였다. 생각 외로 쉽지 않았다.. #include #include #include #include #include using names..
Level 3. 야근 지수 처음에 문제 지문이 이해가 되지 않았는데 예제를 보니 이해가 됐다. (n - 1)² - (n - 2)² < n² - (n - 1)² 이기 때문에 가능한 큰 수부터 감소시켜야 한다. 그렇기에 매번 가장 큰 수를 뽑을 수 있는 우선순위 큐가 효율적이다. 작은수부터 큰 수로 나열시킨다면 직각삼각형 모양이 되는데, 횡스크롤 비행기 게임의 느낌처럼 큰 수부터 위에서 아래로 총알을 쏴 줄여나가는 모습이 떠올랐다. n의 값을 1씩 줄여나가는 사람들이 많았는데, 우선순위 큐에서 뽑은 최댓값과 현재 큐에 있는 최댓값을 비교하면 가능한 만큼 한번에 줄일 수 있다. 줄일 수 있는 최댓값은 (뽑은 수 - 큐의 최댓값 + 1)이다. #include #include #include #include us..
Level 2. 수식 최대화 우선 숫자들과 연산자들을 분리했다. 문자를 하나씩 읽으면서 숫자면 기존 숫자에 10을 곱한 후 더하고, 문자면 연산자로 취급했다. 이후 +, -, * 세 가지 연산자의 우선순위인 6가지 경우의 수에 대해 직접 계산해 해결했다. 우선순위가 높은 순으로 앞에서부터 검색하며 해당 연산자가 있으면 계산하면 된다. a ￮ b의 계산은 a 위치에 a ￮ b의 결괏값을 저장하고 숫자 b와 연산자 ￮를 제거하는 식으로 진행했다. 계산을 마치면 숫자 vector에는 최종 결괏값 1개만 남게 된다. #include #include #include #include using namespace std; long long calculate(long long A, long long B, char op..
Level 2. 테이블 해시 함수 사용자 정의 비교로 정렬할 수 있는지 묻는 문제였다. #include #include #include #include using namespace std; int solution(vector data, int col, int row_begin, int row_end) { int answer = 0; --col; auto pred = [col](auto& t1, auto& t2) { return (t1[col] == t2[col]) ? (t1[0] > t2[0]) : (t1[col] < t2[col]); }; stable_sort(data.begin(), data.end(), pred); auto S = [&data](int i) { return accumulate(dat..
Level 3. 등굣길 BFS가 가물가물해서 BFS로 풀어봤더니 시간 초과가 발생했다. 최단 거리순으로 확인하기 때문에, 최초 최단거리를 넘어서는 순간부터는 확인하지 않아도 된다. // 이 풀이는 시간 초과가 발생한다. #include #include #include using namespace std; struct point { int dist; int x; int y; }; int solution(int m, int n, vector puddles) { int answer = 0; int minDist = 0; int dx[] = {1, 0}, dy[] = {0, 1}; queue que; vector map(n, vector(m, true)); for (vector& puddle : puddles)..
Level 3. 최고의 집합 재귀를 이용해 합이 s가 되는 모든 n개의 조합을 구해 계산하는 방법이다. 나를 제외한 나머지에 해당하는 조합을 구한 후 나를 앞에 붙이는 방식이므로, vector보다는 deque을 사용했다. 하지만, 시간 초과가 발생했다. // 이 풀이는 시간 초과가 발생한다. #include #include #include using namespace std; deque get_sum_sets(int num, int n, int sum) { if (n == 1 && num