Level 2. 택배 배달과 수거하기 이동 경로를 최소화하기 위해서는 가장 먼 곳부터 배달과 수거를 마쳐야 한다. 배달과 수거를 각각 진행하면서 가장 먼 집을 유지하고, 가장 먼 집까지의 거리를 더하는 방식으로 진행한다. 카카오 문제 치고는 파싱이나 다양한 개념들이 섞여있진 않은데, 그렇다고 구현이 마냥 쉽지도 않았다. #include #include #include using namespace std; long long solution(int cap, int n, vector deliveries, vector pickups) { long long answer = 0; int ed = n - (find_if(deliveries.rbegin(), deliveries.rend(), [](int num) { ..

Level 2. 숫자 블록 10,000,000 이하의 가장 큰 약수를 찾는 문제다. 수의 제곱근까지만 순회하면 되고, 약수와 수/약수를 최댓값을 구하는 데 사용하면 된다. #include #include #include #include using namespace std; int max_divisor(int num) { if (num

Level 2. 요격 시스템 Level 3. 단속카메라와 정확히 같은 문제다. 새로운 구간으로 넘어갈지 검사할 때 =을 붙이는 것만 다르다. 구간이 나온다면 항상 시작점을 기준으로 정렬해 생각하면 된다. 두 구간이 겹치는 경우가 대부분이지만, 구간을 완전히 포함하는 경우도 있으므로 끝점을 최솟값으로 갱신해주어야 한다. #include #include #include #include using namespace std; struct Section { int start; int end; friend bool operator B.start; } }; int solution(vector targets) { i..

Level 2. 순위 검색 레벨 2가 맞나 싶을 정도로 파싱, 해시, 이진 탐색 그리고 효율성까지 정말 다양한 것들을 잘 알고 활용해야 하는 카카오 문제다. 꽤 어려웠지만 나름 성장했다고 느낀다. 우선 첫 번째 시도에서 시간 초과가 발생했다. 파싱은 정규 표현식을 이용해 and를 없애고 istringstream을 이용했다. 이후 언어부터 점수까지 조건에 맞는 인덱스를 구하는 방식으로 해결했다. [0, 1, 2, 3, 4, 5, 6, 7] [0, 2, 3, 5, 7] [0, 5, 7] [0, 5] [5] // 이 풀이는 시간 초과가 발생한다. #include #include #include #include #include #include using namespace std; enum class LANG {..

Level 2. 디펜스 게임 정답이 몇 라운드가 되던지, 그 중 무적권을 사용한 라운드는 가장 몬스터가 많이 나오는 n개여야 하므로 우선순위 큐를 사용해야 할 것 같았다. 이번 문제는 솔직히 당연히 틀릴 줄 알고 제출했는데 정답 처리돼서 당황스러웠다. 무적권을 사용할 수 있으면 일단 사용하고 최소힙에 넣는다. 이후 무적권이 없을 때부터는 최소힙의 최솟값과 현재 라운드의 몬스터 수를 비교해, 이전에 썼던 것보다 현재 라운드에 쓰는 게 이득이면 이전 라운드의 몬스터 수를 n에서 빼고 현재 라운드에 무적권을 사용한다. 나중에 현재 라운드에 사용한 것보다 이득인 상황이 올 수 있으므로, 현재 라운드의 몬스터 수도 최소힙에 넣어 주어야 한다. 현재 라운드보다 이전에 썼던 것이 이득이면, 현재 라운드의 몬스터 수를..

Level 3. 단속카메라 여러 개의 구간이 주어진 문제라면, 일단 시작점을 기준으로 정렬할 생각부터 해야 한다. 이 문제에서는 최소힙을 구성하기 위해 Section의 < 연산자를 반대로 오버로딩했다. set, map 등과 달리 우선순위 큐는 최대힙이 기본이기 때문이다. 별도 관리하는 끝점과 각 구간의 시작점을 비교하므로, 끝점은 정렬하지 않아도 된다. 현재 단속 카메라를 배치할 수 있는 끝점을 end 변수로 관리하고, end보다 큰 시작점이 나오면 새로운 카메라를 배치해야 한다. end보다 작거나 같은 시작점이 나오면 현재 카메라를 공유할 수 있다는 뜻인데, 이 때도 가능한 작은 위치에 카메라를 배치해 더 많은 카메라를 공유할 수 있도록 갱신해야 한다. #include #include #include ..