[2023 KAKAO BLIND RECRUITMENT] 1차 코딩테스트 후기

작년 공채 때 눈물의 3.5 솔을 하고 내년엔 이것보단 많이 풀어야지 했는데 진짜 그것보단 많이 풀었다. 

조금 더 욕심 부려서 다짐을 했어야 했는데.. 예를 들면 내년엔 올솔해야지 이런 거.. 아쉽네

---

1번

1번답게 단순 구현이었다.

그냥 달력이라는거 보자마자 일단위로 다 바꿔야겠다는 생각을 했다.

 

제발 제발 월마다 일수 다르다고 하지 말아줘 하면서 조건을 찾아보니까 월 28일로 고정! 예!

 

그래서 date 문자열을 파싱해서 day로 변환해주는 함수를 만들어서 빠르게 해결했다.

2번

오히려 2번이 생각보다 어려웠다.

문제를 보고 그리디라고 생각을 못했으면 되게 헤맸을것 같다는 생각이 든다.

 

n이 무척커서 O(n^2)이면 터지겠다는 생각이 들어서 무조건 O(n)으로 해결해야 하겠다 싶었다.

문제를 잘보면 결국엔 갈 때, 돌아올 때 중에 큰 수의 * 2배라는 걸 알 수 있다.

그래서 배달, 수거 두 개의 stack을 두고 0일때 pop 하고 0이 아니라면 capacity만큼 채워 넣어줬다.

 

이때 분명히 내 논리가 맞다고 생각했는데 시간 초과가 났다.

 

생각해보니까 (pop 한 item) + sum이 capacity를 넘으면 그냥 다시 그대로 push 해줬다.

넣을 수 있을 만큼 넣어도 되는데..!

그래서 capacity가 1이고 [5, 5, 5] 같은 경우는 pop 하자마자 다시 push 하게 돼서 시간 초과가 난다.

 

카카오가 예시에서도 capacity를 다 안 채우고 자기 꺼만큼만 들고 가길래 무의식적으로 똑같이 해버렸다.

3번

얘도 보자마자 제발 완탐으로 풀게 퍼센트 조건 제발 있어라 하면서 찾아봤더니 퍼센트가 10% 단위였다.

O( (4^7) * 100 )이었나? 아무튼 충분히 완탐으로 해결할 수 있는 사이즈여서 완탐으로 해결했다.

4번

이진트리라고 해서 트리로 풀어야 하는 줄 알았더니 그냥 분할 정복, 이진 탐색이었다.

 

처음에 조금 헤맸던 부분이 숫자를 이진수로 바꾸고 (2^n - 1) 만큼 padding을 넣어주어야 하는데 그냥 짝수로만 맞추려고 해서 실패했다.

그리고 child의 모든 노드가 0인 경우를 놓쳐서 실패하다가 찾아내서 해결했다.

5번

merge연산을 했을 때 부모의 좌표를 기억할 배열을 하나 더 만들어서 사용했다.

그리고 (부모 i, 부모 j)를 key로 하는 dict도 만들어서 관리하려고 했다.

그런데 생각보다 쉽지 않아서 결국 하다가 1시간 정도 넘게 남았는데 나왔다.

 

나중에 찾아보니까 유니온 파인드 알고리즘을 사용하면 쉽게 해결할 수 있다고 한다.

내가 생각했던 방식도 결국엔 유니온 파인드랑 비슷했던 것 같다.

6번, 7번

못 품

느낀 점

1번, 2번, 3번, 4번 총 4 솔을 했다.

저번 코테보단 그래도 성장한 것 같다. 부스트 캠프한다고 알고리즘 못 푼 지 3달 정도 됐는데 4솔했으면 꽤 선방했다고 생각한다.

---

결과

항상 컷이 4.5 정도였고, 4번까지 잘 풀리길래 이번 컷은 높겠거니 하고 별로 기대 안 하고 있었는데 붙었다..!!

 

2차는 생전 처음 보는 유형이던데 이제 4일 정도밖에 안 남았는데 남은 시간 동안 힘들게 준비해봐야겠다.