2023 KAKAO BLIND RECRUITMENT 1차 코딩테스트 풀이

코테를 후딱 끝내고 글을 쓴다.

 

이번에도 저번이랑 비스무리하게 1시간반 정도 걸려서 올솔에 성공했다.

다만 난이도는 확실히 저번보다는 어려웠는데, 뒤쪽에 무지성 완전탐색을 박아놨던 작년 문제와는 달리 생각을 해야하는 그리디 문제들이 있어서 그랬다고 생각한다.

 

다음은 각 문제들 풀이이다. 코드는 생략한다.

---

1번

카카오는 개인정보를 가지고 있다. 각 개인정보는 생성된 시기와 약관 종류로 이루어져 있다.

약관 종류는 해당 개인정보를 몇 달 후에 파기 해야 하는지 여부를 나타낸다.

현재 날짜가 주어지고 개인정보들이 주어질 때, 파기해야 하는 개인정보들의 번호를 반환하면 된다.

 

하라는 그대로 구현하면 된다.

각 달이 최대 28일까지만 존재한다는 감사한 조건 덕분에 날짜 노가다를 할 필요가 없어서 다행이었다.

---

2번

직선 위에 \(n \le 10^5\)개의 집이 있다. \(i\)번 집과 \(j\)번 집 사이의 거리는 \(|i-j|\)이다. 물류창고는 0번 위치에 있다.

이 집들에 재활용 박스를 이용해 택배를 배달하고, 재활용 박스를 수거하려고 한다.

각 집에 배달해야 하는 택배 수와 수거해야 하는 박스 수가 주어지고 한번에 최대 \(cap\)개의 박스만 옮길 수 있다고 할 때, 최소 이동 거리를 출력해야 한다.

 

가장 멀리 있는 집부터 빠르게 처리해 주는것이 무조건 이득임을 알 수 있다.

현재까지 택배를 배달해야 하거나, 박스를 수거해야 하는 가장 먼 집부터 방문하는 것을 반복하면 된다.

배달하거나 수거해야 하는 박스의 수가 집당 최대 50개이므로 단순 시뮬레이션으로도 풀 수 있다.

---

3번

\(n\)명의 카카오톡 사용자들이 있고, 이들에게 \(m \le 7\)개의 이모티콘을 판매하려고 한다.

각 이모티콘은 10, 20, 30, 40퍼센트 중 한가지 방법으로 할인을 한다.

각 사용자는 다음과 같이 이모티콘을 구매한다.

1. 이모티콘 할인율이 일정 이상이면, 그 이모티콘을 구매한다.

2. 총 이모티콘 구매 가격이 일정 이상이면, 구매하는 대신 이모티콘 구독 서비스에 가입한다.

 

이를 통해

1. 이모티콘 구독 서비스에 최대한 많이 가입시키고,

2. 서비스 가입 수가 같다면 이모티콘 판매가격이 최대화 되도록

이모티콘 할인율을 조정해야 한다.

 

이모티콘이 많아도 7개이므로, 완전탐색을 통해 \(n \times 4^7\)가지의 모든 경우를 따져보면 된다.

---

4번

이진트리를 이용해 수를 표현할 수 있다.

이진트리가 있으면, 해당 이진트리를 더미 노드로 채워 포화 이진트리로 만든 다음, 왼쪽에서부터 읽어서 이진수로 만들 수 있다.

더미 노드는 0, 그렇지 않은 노드는 1로 읽는다.

 

수 \(n \le 10^{15}\)가 최대 10000개 주어지는데, 각 수를 이진트리를 이용해 만들 수 있는지 여부를 출력하면 된다.

 

수가 주어지면, 일단 이진트리로 만들어 볼 수 있다.

 

예를 들어 수가 13이라면, 이진수로 1101로 만들고, 포화 이진트리가 되기 위해서는 자릿수가 \(2^n-1\)꼴이어야 하니 앞에 그만큼 0을 붙여 0001101로 만들면 된다.

이 트리를 DFS 탐색하여 더미노드 밑에 더미노드가 아닌 노드가 있는지 여부만 확인하면 된다. 그런 경우가 있으면 불가능하다.

---

5번

표 편집 프로그램이 있다.

50 x 50크기의 표에 다음과 같은 쿼리를 날리려고 한다.

1. (r, c)에 value를 넣는다.

2. value1가 들어있는 모든 칸의 내용을 value2로 바꾼다.

3. (r1, c1)와 (r2, c2) 칸을 합친다. 두 칸은 인접해 있지 않을 수 있으며, 합친 후에는 (r1, c1)이 비워져 있지 않다면 (r1, c1)의 값으로, 그렇지 않으면 (r2, c2) 값으로 치환된다.

4. (r, c)칸이 합쳐져 있다면 합쳐진 모든 칸을 풀고 초기화 한다. 합쳐진 칸에 들어있던 내용은 (r, c)에 들어간다.

5. (r, c)에 있는 값을 출력한다.

 

두 셀을 합치는 MERGE연산이 있는 걸 봤다면, union-find (disjoint set)을 사용해야겠다고 쉽게 생각할 수 있다.

 

 

(이걸 쓰지 않고 단순 구현하면 쿼리당 \(50^4\)번의 연산이 될 수도 있기 때문에, 시간 초과가 날 수 있다.)

그 외에 다른 연산들은 표가 작기 때문에, 쿼리당 \(50^2\)번의 연산으로 충분히 커버할 수 있다.

---

6번

\(n \times m\) 크기의 격자에서, (x,y)에서 시작해서 (r,c)까지 이동하는데, 정확히 \(k\)번 상하좌우로 이동해서 도착해야 한다.

가능한지 여부를 알아내고, 가능하면 사전순으로 가장 작은 경로를 출력하면 된다.

 

불가능한지 여부를 알아내는 것은 쉽다. 이동해야 하는 최소거리보다 \(k\)가 작거나, 홀짝이 맞지 않으면 불가능하다.

그렇지 않으면, 그리디하게 "dlru" 순으로 갈 수 있는지 여부를 체크하고, 갈 수 있으면 무조건 가는게 이득이라는 사실을 알 수 있다.

---

7번

트리가 주어진다. 트리의 각 노드에서 자식노드로 연결하는 경로중에 단 1가지만 "길"로 정의된다.

길은 한번 사용하고 나면 길이 아니게 되고, 해당 노드의 다음 자식으로 이어지는 경로가 새로운 길이 된다.

루트에서 무게가 1, 2, 또는 3인 상자를 떨어뜨리려고 한다.

상자는 길을 따라 이동하고, 결국 리프 노드에 쌓이게 된다.

 

각 리프 노드에 쌓인 상자들의 합이 사전에 정한대로 될 수 있는지를 판단하고, 가능하다면

1. 가장 적은 상자를 사용해서

2. 상자를 사용한 개수가 같다면 사전순으로 가장 앞서는 것을

출력하면 된다.

 

트리의 노드가 최대 101개고, 각 리프 노드에 최대 100의 무게가 쌓일 수 있으니 아무리 많아도 101 * 100 번 안에 답이 나온다는 사실을 알 수 있다.

해당 횟수만큼 시뮬레이션해서, \(i\)번째에 상자를 떨어트렸을 때 몇번 (리프)노드로 떨어지는지를 모두 미리 계산해 놓자.

 

이제 1번부터 101 * 100번까지가 각각 답이라고 했을 때, 그게 가능한지 여부를 생각하면 된다.

상자를 적당히 떨어트렸을 때 어떤 리프 노드에 상자가 \(x\)회 떨어지고, 필요한 무게가 \(w\)라고 하면, \(x \le w \le 3x\)가 모든 리프노드에 대해 성립하는지 확인하면 된다.

 

가능하다면, 이제 사전순으로 적절히 정렬하면 된다.

이 역시 그리디하게 해당 순번에 가벼운 상자를 놓을 수 있는지 여부를 계속 계산함으로써 구현할 수 있다.