[Programmers] 2021 KAKAO BLIND RECRUITMENT 문제풀이

문제 모음 : https://programmers.co.kr/learn/challenges

순위 검색

Link : https://programmers.co.kr/learn/courses/30/lessons/72412

이분 탐색 문제.
각 정보들을 파싱해서 인덱스를 매긴 뒤 각 종류에 따라 분류를 해주자.
나같은 경우 점수를 제외한 각 카테고리를 a, b, c, d라 하고 점수를 score라 했을 때
p[a][b][c][d]에 score를 푸쉬해줬다. (vector<int> p[][][][])
그럼 각 카테고리별로 점수만 담기게 되는데, 이분 탐색을 이용하기 위해 모든 케이스를 오름차순 정렬해준다.
이후 쿼리도 위처럼 파싱해서 처리하고 담아준 후 쿼리별로 재귀를 돌려가며 답을 얻어오도록 했다.
“cpp”, “java”처럼 딱 정해지지 않고 “-“처럼 모든 케이스가 상관이 없는 경우 모든 케이스를 재귀로 돌면 된다.
a, b, c, d의 정보를 모두 채웠을 때를 기저 사례로 설정한 후 lower_bound()로 해당 점수 이상의 케이스가
몇 가지인지 바로 구해주면 된다.

개인적으로 이분 탐색 문제를 다른 유형에 비해 소홀했던 탓인지
이분 탐색 문제인지 알아차리기가 정말 힘들었다.
info와 query의 사이즈가 각각 약 10만이기 때문에 어떤 방법으로 풀어야 효율성을 통과할지 고민하는데
도무지 답이 나오질 않아 카카오 기술 블로그에서 도움을 얻었다.
DP로 풀 수 있을까란 의문이 첫 번째여서 건드려보려다 좀 아닌거 같아서 찾아보니 이분 탐색이더라😇

프로그래머스에서 푸는 구현 문제들은 대부분 파싱하는게 꽤 귀찮은 것 같다.
다른 사이트에서 풀었다면 종류를 간단히 숫자로 표시했을 법도 한데 string으로 종종 주어지는걸 보면
이렇게 자잘한 구현에서 빠져나오는지 여부를 테스트하는 느낌도 든다.

합승 택시 요금

Link : https://programmers.co.kr/learn/courses/30/lessons/72413

다익스트라 or 플로이드 와샬 문제.
n의 상한이 200이어서 충분히 $O(n^3)$에 돌아가므로 플로이드 와샬로 처리해도 된다.
i를 거쳐가는 지점이라 할 때,
$answer = min(answer, d[s][i] + d[i][a] + d[i][b])$

광고 삽입

Link : https://programmers.co.kr/learn/courses/30/lessons/72414

스위핑 유형.

일단 보자마자 접근한 방법은 세그먼트 트리였다.
상한이 99:59:59면 초로 바꿨을 때 359999여서 메모리 상으로도 충분할 것 같았고
구간별로 합을 한번에 구하는 자료구조를 활용한다면 00:00:00부터 play_time-adv_time까지 합을 구하는
쿼리를 돌려도 시간 초과를 받지 않을 것 같아 구현해봤고 결국 맞긴 맞았다.

개인적인 생각이지만 세그먼트 트리가 정해가 아닐 것 같은데 ..
다른 분들의 풀이는 어떤지 좀 찾아봐야겠다.
인턴 코테에서 세그먼트 트리라니 이게 정해라면 좀 끔찍하다. 구현이 어렵진 않지만😂

설명을 잘 읽고 구간에 대해 어떻게 누적 재생시간을 계산하는지 잘! 보자.
대충 읽고 덤벼들었는데 이 부분때문에 괜히 고생했다.

카드 짝 맞추기

Link : https://programmers.co.kr/learn/courses/30/lessons/72415

구현 문제.
이동하는 경우를 인접한 1칸 그리고 ctrl를 눌러서 가는 경우 2가지로 나눠서 생각해보자.
전자는 인접한 1칸으로 이동하고 키 조작이 1회 발생한다.
후자는 ctrl를 누르므로 쭉 가서 이동하되 캐릭터를 만나거나 벽을 만났을 때 위치가 된다.
이 때도 똑같이 키 조작이 1회 발생한다.
나같은 경우 BFS로 탐색을 진행했는데 무분별하게 큐로 들어가는 경우를 방지하기 위해
키 조작을 기준으로 걸러줬다. (가령, d[nx][ny] > d[x][y] + 1일 때만 진행)
BFS를 진행하기 전에는 현재 위치에서 만나려는 캐릭터 종류를 설정하고 진행했으며
이는 재귀를 통해 설정되도록 해줬다.

설명을 잘못 읽어서 며칠동안 고생했다. 솔직히 이렇게 고생할줄 알았나 싶을정도로 오래걸렸다.
여태까지 풀어왔던 구현 문제중에 가장 까다롭다고 느끼기도 했으나 실력이 많이 부족한듯 싶다.
어째 매 문제마다 고생하는 것 같다.

매출 하락 최소화는 못풀어서 쓰지 못했다😅
못 푼 문제도 걱정이지만 풀 수 있는 문제를 제 시간에 다 풀어낼 수 있는지 아는게 중요해 보인다.
평소에 문제 풀 때 실전처럼 파바박 풀어내려고 하는 스타일이 아니라 더 취약할 듯하다.
특히나 카카오 문제처럼 구현 난이도가 좀 있어 보이는 경우 주의해야겠다!
그리고 문제 똑바로 읽기!