[Programmers] 2022 KAKAO BLIND RECRUITMENT 문제 풀어보기
1. 대회 문제 링크
2. 대회 공식 풀이 링크
대회 풀이 링크 (https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/)
3. 문제 풀이 코드
4. 대회 문제 풀이
직접 참가하지는 않았고, 나중에 프로그래머스에 올라온 문제를 시간을 재보면서 풀어보았다.
1. 신고 결과 받기
Time: 19분 26초
단순 구현 문제였다. String을 key로 두는 자료구조를 만들어야 함을 깨닫고 python의 dictionary가 떠올랐다. 그러나 아직 python을 다루는 것에 익숙하지 않아서 원래 하던대로 c++로 구현하였다.
C++에서는 map을 사용하여 이를 해결하였다. 공백을 기준으로 문자열을 분리하는 split도 python 내장함수로 하는 것이 훨씬 편하다. C++에는 이를 지원하지 않아 isstream으로 만들어야 했는데 너무 복잡해서 그냥 단순 구현으로 split 함수를 직접 만들어 사용하였다. 이렇듯 아예 파이썬 구현을 노리고 만든 문제인 것 같다는 생각이 들어 나중에 파이썬으로도 구현해보았다.
해당 유저(key: string)를 신고한 유저들(value: set<string>)을 map으로 만들었다. Value의 중복이 제거되어야 하므로 set 자료구조에 데이터를 담았다. 이 value의 길이가 $k$보다 크거나 같으면, value 집합의 원소들(string) 즉, 이 유저를 신고한 유저의 cnt 값을 $1$ 증가시키는 방식으로 처리 결과 메일을 받는 횟수를 구현하였다.
끝나고 파이썬으로 구현해봤더니 19분 13초가 걸려서 사실상 c++ 구현과 걸린 시간이 동일했다. 파이썬에 익숙하지 않아 dictionary의 value에 set을 집어넣는 방법과 같은 것들을 검색하다보니 시간이 많이 소요됐던 것 같다. 두 언어 모두 익숙한 경우, 이 문제는 파이썬으로 구현하는 것이 훨씬 효율적일 것이다.
2. k진수에서 소수 개수 구하기
Time: 11분 35초
조건이 많고 복잡해 보이지만, 결국 양의 정수 $n$의 양쪽에 $0$을 붙이면, $0$ 사이에 있는 수들 중 소수의 개수를 찾는 문제로 정리된다. (수 양쪽에 $0$이 존재해야 하므로, $0$이 아닌데 수가 중간에 잘리는 경우는 없다.) 이 방식 그대로 구현했다.
3. 주차 요금 계산
Time: 28분 28초
공백을 기준으로 문자열을 자르는 작업이 필요해서 $1$번에서 구현했던 split 함수를 가져와 조금 변경하여 사용하였다. String을 key로 하는 자료구조가 필요하여 $1$번과 마찬가지로 map을 사용하였다.
하나의 입차와 하나의 출차가 짝을 이루기 때문에, 출차 다음에 다음 입차가 발생한다. 이 특징을 이용하여 입차인 경우 해당 차(key)의 value로 입차 시간을 저장하고, 출차인 경우 해당 차(key)와 매칭된 value 시간 값(입차 시간)을 가져와서 출차 시간과의 차이 값을 계산하는 방식으로 구현하였다.
4. 양궁대회
Time: 36분 17초, WA: 1
딱히 그리디한 방법이 존재하지 않는 거 같아서 완전탐색으로 구현하였다. $0\sim 10$점 중에 라이언이 가져갈 점수가 어떤 점수인지를 정하는 방식으로 비트마스킹을 사용하여 완전탐색을 진행하였다.
라이언은 $n$발의 화살을 쏴서 어피치를 가장 큰 점수 차이로 이겨야 한다. 따라서 라이언은 가져갈 어떤 점수에 어피치가 맞춘 화살보다 정확히 한발 더 맞춰야 효율적이다. (이거보다 더 맞추든 말든 어차피 점수는 라이언이 갖기 때문에 다른 곳에 화살을 사용하는 것이 효율이 좋다.)
이렇게 라이언이 가져갈 모든 점수에 어피치보다 한발씩 더 맞춘다고 가정했을 때, 화살의 합계가 $n$을 넘으면 불가능하므로 넘어간다. 반대로 화살의 합계가 $n$보다 작을 경우, 문제의 조건에 따라 가장 낮은 점수를 더 많이 맞힌 경우가 정답이 되므로, 남은 모든 화살을 $0$에 맞힌다. 이런 모든 가능성에 대해 문제의 조건에 따라 maximum 값을 갱신해가면서 정답을 찾았다.
구현 방법은 머리속에 금방 정리되었으나, 실제 구현은 굉장히 힘들었던 문제였다. 백준의 구현 문제들을 많이 풀어보면서 연습하지 않았다면, 방법은 다 생각해놓고 구현에 실패했을 수도 있을 것 같다. 부등호 하나를 잘못 설정하여 WA를 $1$번 받았다.
5. 양과 늑대
Time: 56분 22초
Info의 길이가 $17$이어서 완전탐색으로 충분히 가능해 보였으나, 정확히 어떤 방식으로 완전탐색을 할지가 관건이었다. 이미 방문한 노드라도 다른 곳에서 양의 개수를 늘려온 상태면 다시 방문이 가능하게 만들어야 하는 문제이다.
따라서, 다음 탐색할 노드를 지정하기 위해서는 지금까지 어떠한 곳들을 방문했는지, 그 모든 곳을 방문해서 양과 늑대의 개수 차이가 몇인지, 위 두가지의 정보를 담으면서 탐색해야 했다.
각 노드의 방문과 관련된 정보가 필요하고 노드의 최대 개수가 $17$이어서 최종적으로 Bitmasking(비트마스킹)이 떠올랐다.
$dp[node][vis] \rightarrow$ 현재 node에서 vis($0\sim 16$ 노드 중 어떤 노드들을 방문했는지에 대한 정보)를 방문했을 때, 양($+1$)과 늑대($-1$) 점수의 합
다음 노드로 이동하면, 그 노드를 처음 방문한 경우(vis를 통해 확인 가능) vis와 score를 갱신한다. 단, 만약 변경되는 score가 $0$ 이하라면(늑대가 양보다 많거나 같은 경우) 그 노드를 방문하지 않는다. 이렇게 구현하게 되면, 다른 곳을 탐색해서 양 개수를 늘리고 다시 방문했던 노드로 돌아오는 작업이 가능해진다. (node는 같지만, vis값이 달라졌기 때문에)
양을 몇 마리 모았는지가 최종 정답이므로(dp는 양과 늑대의 합이어서 정보를 얻을 수 없음), 따로 sheep 변수를 파라미터로 두어 dfs를 탐색하며 maximum값을 갱신했다. dp 형식을 pair<int, int>로 두어 양과 늑대의 개수를 각각 저장한다면, 이 과정이 필요 없다.
6. 파괴되지 않은 건물
Time: 41분 46초
문제를 처음 읽었을 때, 가장 먼저 $2$차원 세그먼트 트리가 생각났다. 그런데 지금까지 계속 완전탐색 구현 문제만 나오다가 갑자기 그렇게 어려운 알고리즘이 나올 것 같지는 않아서 다른 방법을 찾아보았으나 실패했다.
kakao Tech에 공식적으로 2022 온라인 코테 문제해설이 올라와 있어서 이것을 보고 풀었다. 해당 사이트에 해설이 자세하게 올라와 있고, 그대로 풀었기 때문에 추가로 여기에 해설을 적을 필요는 없을 것 같다.
이런 방법을 떠올릴 수 있으려면 어떤 방식으로 더 공부를 해야 할지가 관건인데, 그냥 문제를 많이 풀어보는 것 말고는 딱히 다른 방법이 떠오르진 않는다.
7. 사라지는 발판
Time: 61분 46초, WA: 2
백준에서 여러 돌 가져가기 문제를 풀어보았지만, 이런 복잡한 유형은 처음이었다. 맵이 $5\times 5$ 사이즈여서 작아보일 수 있으나, $0$과 $1$ 두 가지 경우가 존재하므로 $2^{25}$의 경우가 존재한다.
이 모든 맵 각각에서 플레이어의 위치(게다가 위치도 랜덤)에 따라 최적의 방법을 찾는 건 불가능할 것이라고 판단하여 완전탐색으로 구현하기로 하였다.
최적의 플레이를 한다는 것은 다음을 의미한다. (나와 상대 플레이어 모두 본인의 시점에서 동일하게 작용한다.)
- 내가 하려는 모든 행동이 결과적으로 상대방의 승리를 불러온다면, 나는 무조건 패배한다.
- 내가 하려는 행동 중 상대방의 패배를 불러오는 행동이 하나 이상 있다면, 승리를 위해 그 방법들 중 하나를 선택한다.
이때, 이길 수 있는 플레이어는 최대한 빨리 승리하도록 플레이하고, 질 수밖에 없는 플레이어는 최대한 오래 버티도록 플레이하는 것이 문제의 조건이다.
따라서, $1$처럼 무조건 패배하는 경우 move 중에 maximum을 찾고, $2$처럼 이길 방법이 존재하는 경우 move 중에 minimum을 찾는다. (단, $2$에서 minimum을 찾는 경우, 상대방이 패배하는 행동을 선택하기 때문에 그것들 중에서만 찾아야 한다. 상대방이 성공하는 경우까지 포함시키면 규칙에 어긋난다.)
댓글남기기