코테나 PS에 관심을 갖기 시작한게 9월~10월 쯤이었어서 신청을 못했었던게 아쉬웠었다.
최근 알고리즘 스터디에 들어가게 되면서 프로그래머즈에 카카오 2023 문제가 들어왔길래 풀어봤다.
문제 푸는 시간은 14:00~19:00로 5시간을 준다고 했었어서 시간을 재면서 문제를 풀어봤다.
1,2,3,4번을 푸는데 2시간이 걸렸고
7번 푸는데 2시간, 6번 푸는데 1시간 좀 넘게 걸리면서 타임 오버
5번을 푸는데 방향성을 잘못잡아서 2시간정도 쓴 것 같다.
6솔까진 할만했을 거 같은데 아쉬움이 남는다..
1번. 개인정보 수집 유효기간 (프로그래머즈 링크)
단순한 문자열 파싱문제이다.
날짜는 YYYY.MM.DD 형식으로 주어지고, 모든 달은 28일까지 있다고 한다.
즉, 문자열은 YYYY*(28*12) + MM*(28) + DD 로 해체해서 정수형으로 만들어서 계산한다.
약관 이름은 A~Z의 알파벳 대문자 하나로 이루어져 있으므로 굳이 HashMap을 이용하지 않고, Array를 사용할 수 있고,
보관하는 달 수는 1이상 100이하 이므로 byte[]를 이용하면된다.
이후, privacies를 순회하면서 '수집일' + '최대기간'*28 이 'today'를 넘는가?를 확인하여 리스트를 만든다.
2번. 택배 배달과 수거하기 (프로그래머즈 링크)
택배 배달 및 상자 수거를 할 때 최소 이동 거리를 구해야 하는 문제다.
단순한 문제인데, 끝에서부터 배달 해야하는 걸 모두 배달하고, 수거할 걸 모두 수거하면 된다.
예시에서 주어진 배달 : [1, 0, 3, 1, 2], 수거 : [0, 3, 0, 4, 0]을 볼 때,
모두 배달해야하므로 순서를 어떻게 하더라도, 반드시 거리 5에 2개를 배달하는 회차가 존재한다.
그렇다면, 굳이 앞에서 부터 배달할 필요 없이, 멀리서부터 배달한다면 모든 거리를 측정할 수 있을 것이다.
트럭은 cap개까지 담을 수 있으므로,
배달에서 끝에서부터 cap개, 수거에서 끝에서부터 cap개를 수거하는 과정이 한 회차가 된다.
이 때, 해당 회차에서 처음 배달한 지점과 처음 수거한 지점 중 큰 수가 이번 회차의 편도 이동거리가 된다.
예를 들어, 위 예제에서는 첫 회차는 집#5에 2개, 집#4에 1개, 집#3에 1개를 배달하고, 집#4에서 4개를 수거한다.
그러면 이동거리는 Max(5, 4)이므로 5가 되고, 집#5까지 갔다가 창고로 돌아와야하므로 5*2 = 10.
10이 이번 회차의 총 이동거리가 된다.
이 구현에서 유의해야할 점은, 배달이나 수거할 곳이 없는 곳을 카운트 하면 안된다는 것이다.
이러한 회차들을 반복하면서 배달과 수거를 모두 완료했을 때까지의 회차들의 거리의 합이 답이 된다.
3. 이모티콘 할인 행사 (프로그래머즈 링크)
각 사용자는 자신의 비율 이상 할인하는 이모티콘만 구매하며,
자신의 예산을 벗어나게 결제하는 경우 이모티콘 플러스를 가입한다.
상점의 각 이모티콘은 10, 20, 30, 40%중에 하나로 할인한다고 할 때,
이모티콘 플러스 이용자 증가 수를 1순위, 이모티콘 결제금액을 2순위로 가장 극대화 하는 경우의 수를 구해야한다.
조건을 보면 이모티콘의 종류는 7개가 최대이고, 할인의 경우의 수는 4개 이므로,
총 경우의수가 4^7 = 16,384개 밖에 되지 않는다.
그러므로 그냥 Brute-force로 풀었다.
4. 표현 가능한 이진트리 (프로그래머즈 링크)
처음에 주어진 입력의 수들을 하나의 이진트리로 표현할 수 있냐는 말인 줄 알고,
result가 말이 안되는데... 하면서 좀 헤맸던 문제다.
아무튼, 주어진 입력의 수를 binary로 바꿨을 때, 0은 빈 노드고 1은 노드가 있는 경우다.
이 때, binary code가 하나의 트리로 표현될 수 있다면 1, 없다면 0을 result에 올린다.
구분하는 법은 간단하다.
1. 해당 수를 binary로 전환한다. Java의 경우 Long.toBinaryString()이 있다.
2. 변환한 BinaryString의 길이를 표현할 수 있는 가장 작은 이진트리의 크기에 맞춘다.
- 예를 들어, 숫자 42는 101010이다.
- 101010은 길이가 6이고, 노드 6개를 포함할 수 있는 가장 작은 트리는 노드 7개인 트리이다.
- 이것은 log_2(길이)를 올림하면 가장 작은 트리의 Height가 나오고, 2^Height - 1이 가장 작은 트리의 노드 수가 된다.
※ log_2(6) = 2.58... => 3, (2^3)-1 = 7, 부족한 자리수는 0으로 채운다. 0101010
3. root노드 부터 왼쪽 자식, 오른쪽 자식을 탐색하면서
해당 노드가 1이라면 0으로 교체하고 자식을 탐색하고, 0이라면 탐색하지 않는다.
4. 트리 탐색이 끝난 뒤, binary string에 1이 남아있다면, root와 이어지지 않은 노드가 존재한다는 의미이다.
=> 표현이 불가능하다.
5. 표 병합 (프로그래머즈 링크)
이 문제는 MERGE나 UNMERGE같은 것들의 구현이 까다로운 문제다.
처음에는 bfs,dfs를 이용해볼려고 하면서 시간을 좀 태웠던 문제다.
(문제 조건상 사용할 수 없었다..)
일단 풀이 방식에 핵심은 다음과 같다.
- "UPDATE value1 value2"를 봤을 때, 같은 값을 가진 모든 셀을 변경하는 일이 존재하므로, 각 셀에 직접 데이터를 보관하지 말고, 데이터의 Key(포인터)를 저장하자.
Java에서 기본적으로 int배열을 생성하면 0으로 초기화 되므로, key=0에는 "EMPTY"를 대응한다.
UPDATE를 통해 값을 추가하는 경우,
이미 사전에 존재하는 단어라면, 그 단어의 key를 가져와 입력하고,
존재하지 않는 단어라면 사전에 추가하고, 그 key를 입력한다.
MERGE에서도 똑같이,
(r1, c1)에서 가리키는 값이 0이 아니면 (r1,c1)의 값을 쓰고,
0이라면 (r2, c2)의 값을 사용한다.
그리고 UNMERGE를 구현하기 위해서는
각 셀들이 어떤 셀들과 MERGE되었는가?를 알기 위한 merge data도 필요하다.
여기서 사용될 merge data는 다른 merge에서 중복으로 사용되면 안되므로, 중복되지 않는 값이 필요했고,
이는 명령어가 실행된 횟수로 사용했다. (동일한 타이밍에 MERGE가 두 번 실행될 수 없으므로)
그래서 MERGE를 하게 되면, (r1, c1)의 Merge data와 (r2, c2)의 Merge data를 구한 뒤,
그 값이 0이 아닌 경우, 엑셀 전체를 탐색하며 하나의 merge로 통합하고,
UNMERGE를 하게 되면, (r, c)의 merge data를 가지는 모든 셀의 merge data와 가리키는 값을 0으로 초기화 하고,
(r,c)에만 다시 값을 입력해준다.
처음에는 이 과정을 dfs,bfs로 했었는데,
MERGE과정에서 (r1,c1)과 (r2,c2)가 인접하지 않은 경우가 있으므로, 작동하지 않았다.
그 다음에는 merge가 있으므로 tree의 union을 써야하나... 하고 한 5분정도 고민하다가
엑셀의 크기는 50x50 = 2,500이고, 명령어는 최대 1,000개이므로,
전체탐색으로 해도 되겠다는 생각이 들어, 전체탐색으로 진행했다.
MERGE는 (r1,c1)의 data, (r2,c2)의 data를 모두 cmdline으로 변경하므로
2500*2번의 연산이 진행되고, 명령어 1000번이 모두 MERGE더라도
5,000 * 1,000 = 5,000,000번의 연산 내에 수행 가능하다.
6. 미로 탈출 명령어 (프로그래머즈 링크)
l,r,u,d를 사전순으로 배치해야한다는게 골치아픈 문제였는데,
처음 접근했던 방법은 먼저 bfs로 최단 경로를 구하는 것이었다.
이 때, 이동을 d,l,r,u 순서로 하면, 가장 먼저 골 지점에 도달하는 방법은 무조건 사전순이기 때문이다.
그리고 남은 거리가 홀수거나, 도달하지 못했다면 impossible을 반환한다.
이제 불가능한 경우의 수를 모두 쳐냈으니, 문제는 남은 거리를 어떻게 채울 거냐 인데,
일단 사각 격자내에 장애물이 없으므로, 최단거리는 반드시 'dl', 'dr', 'lu', 'ru'로 나오게 된다.
그러므로 'dl', 'dr'의 경우는 d가 끝나는 지점부터 남은 거리를 채우고,
'lu', 'ru'는 'l, r'이 끝나는 지점부터 남은 거리를 채우자.. 뭐 그런 발상을 했었는데,
커버해야할 예외 사항이 너무 많았다.
그래서 그냥 싹 지우고, 문제의 제한사항에 집중했다.
사전순으로 가장 빠른 경우의 수를 배치해야하고, 목표거리를 채워야한다.
그러면 남은 이동거리와 목적지와의 거리가 같아질 때 까지,
d,l,r,u 순으로 이동가능한 방향으로 계속 이동하다가 목적지로 이동하면 되는게 아닌가?
그래서 이걸 구현하고 통과했다.
무작정 bfs, dfs부터 밀어넣고 보는 습관은 좀 없애야겠다...
7. 1,2,3 떨어트리기 (프로그래머즈 링크)
구현문제?라고 생각해서 직접 시뮬레이션하는 방법을 생각했다.
시뮬레이션 과정은 다음과 같다.
1. 각 단말 노드에 도달하는 사이클을 구한다.
- 사이클을 구하는 법은 간단한데, bottom-up방식으로 자식에서부터의 모든 경우의 수를 곱하면 된다.
예를 들어, 문제의 예제#1의 경우, 2*2*3 = 12이므로, 12번마다 같은 cycle이 반복된다.
2. cycle을 돌면서 각 노드들이 몇 번 탐색되는지의 회수를 구한다.
- 예제#1의 사이클은 [3, 7, 6, 8, 3, 9, 6, 7, 3, 8 ,6, 9]다.
- 사이클을 돌면서 각 노드의 방문횟수를 1씩 증가시키고, 해당 방문횟수로 target의 수를 만들 수 있는지를 체크한다.
모든 단말 노드의 수를 만들 수 있게 되면 탐색을 종료한다.
3. 각 target의 수를 해당 회수로 표현해 Queue에 넣는다.
- 이 때, target의 수 보다 회수가 많다면, 1만 넣는 경우에도 target을 over하므로, 불가능한 경우가 된다.
- '3*(남은 회수) - 남은 target의 수'에 따라 1,2,3 중 어떤 수를 넣어야하는지가 결정된다.
4. cycle을 순회하면서 Queue의 값들을 꺼내 결과 배열에 넣고 반환한다.
총평
시간복잡도 자체가 빡빡하지 않은 문제들이 대다수라 편했다.
그리고 프로그래머즈에 가보면 카카오 기출 문제들이 꽤 있는데,
몇 번 풀어본 이전 프로그래머즈 2,3렙 문제들에 비하면 7문제 모두 비교적 쉬운 문제인 것 같다.
백준으로 치면 최대 골드에 프로그래머즈도 2,3렙정도.. 7번은 왜 4레벨인지 모르겠다.
올해는 여기저기 기업코테 열리면 놓치지 않고 가보고 싶다.. 어디서 일정을 봐야 안놓칠까..