2021 카카오 블라인드 코딩테스트 1차 후기
..9/17 18:00 쯤에 카카오톡이 와서 이메일을 확인해봤다.
작년에 보았을 때는 2.5솔 정도 했었는데,
이번에는 4솔로 마무리하게 되었다. (1, 2, 3, 4 풀고, 5번 푸는 도중에 테스트 종료)
내가 느낀 문제별로 필요한 지식 및 아이디어는 다음과 같다.
1번 문제 - 문자열 처리 (+ 정규식)
-> 문제에서 시키는 대로 차례대로 조건에 맞게 문자열을 필터링하였다.
2번 문제 - 적절한 자료구조 사용 능력 (완전탐색 / 해시)
-> map을 사용하여 해당 값이 들어온 횟수를 세고, 큰 순서대로 담았다.
데이터의 개수가 많지 않기 때문에, 빈틈없이 잘 처리하는게 중요한 것 같았다.
3번 문제 - 적절한 자료구조 사용 능력 + 이분 탐색 응용 (트라이?)
-> (1) 다차원 배열(마지막 차원은 동적 배열)을 사용하여 데이터를 담아 정렬한 뒤,
(2) lower_bound를 사용하여 조건에 맞는 데이터들을 가져왔다.
예를 들어서, "java, backend, junior, pizza, 100" 라는 데이터를
h[1][2][1][1].push_back(100); ~ h[0][0][0][0].push_back(100); 까지 저장했고,
"python, frontend, senior, pizza, 200" 라는 데이터는
h[2][1][2][1].push_back(200); ~ h[0][0][0][0].push_back(200); 까지 저장했다.
문제에 조건에 따라, "언어(3종류), 직무(2종류), 경력(2종류), 음식(2종류), 점수" 의
각 항목마다 정해진 개수가 있었는데,
이때, "- and - and - and - and 100" 이라는 형태로 쿼리가 들어올 수 있으므로
h의 크기를 최대 3x2x2x2xN 이 아닌 4x3x3x3xN 로 최대 크기를 정해주었다.
최악의 경우에도 주어진 시간내에 충분히 수행할 수 있는 방법이기에 사용했다.
마지막으로 잘 처리해준 데이터들을 쿼리 조건에 따라 불러올 때,
일정 점수 이상의 데이터를 빠르게 불러와야 하므로 정렬되어있다면 좋을 것이라 생각했다.
따라서 마지막 동적 배열에 해당하는 부분을 오름차순으로 정렬해주고,
lower_bound를 이용하여 해당 점수보다 같거나 큰 데이터들을 O(logn) 시간에 불러왔다.
즉, 최대 10만개의 조건 데이터에 대해서 O(n^2)이 아니라 O(nlogn)으로 처리한다.
4번 문제 - 최단 경로 알고리즘 (다익스트라 / 플로이드)
-> 정점 n의 개수가 200이여서 플로이드 와샬을 통해 풀었다.
3중 for문을 통해서 dist를 갱신시켜두고 사용했다.
핵심은 'dist[s][x] + dist[x][a] + dist[x][b]' 의 값이 최소인 것을 찾으면 되었다.
5번 문제 - 구현 능력 (+ 문자열 처리) + 누적합 (투포인터?)
-> 시간이 부족한 상태에서 만나서 체감상 쉽지 않은 문제였다.
요구하는 조건을 읽다보면 어떻게 풀면 되겠다는 어렵지 않게 알 수 있었으나
종합적으로 구현 능력도 들어가 있어서 디버깅에 시간을 쏟게 될 수도 있는 문제였다.
6번 문제(?) - 구현 능력 + 완전탐색 + 다익스트라
-> (문제가 올라오면 다시 읽고 올리겠습니다.)
7번 문제 - 트리 DP
-> 트리 DP를 이미 경험해본 사람은 오히려 어렵지 않게 풀 수 있었을 것 같다.
그러나 모르는 사람들은 건너뛰는 문제가 되었을 것 같다.
댓글
댓글 쓰기