문제 링크: 2023 KAKAO BLIND RECRUITMENT
1. 개인정보 수집 유효기간
그냥 날짜를 수로 바꿔서 비교하면 됐다.
2. 택배 배달과 수거하기
마땅한 BFS DFS, DP, 브루트포스 등의 알고리즘 활용방법이 보이지 않았고 그리디로 접근하는게 맞다고 생각했다.
첫번째로 접근했던 방법은 택배를 가득 싣고 가서 제일 먼 집부터 택배를 최대로 줘서 cap을 최대로 늘리고 남는 cap공간에 수거를 최대로 채우는 형식이었다. (오답)
그 다음으로 시도한 방법은 수거할 물품이 있다면 “택배를 버리기” 였다. 택배를 버리는건 원래 안들고 왔었을때처럼 상황을 바꾸는 것으로 “더 먼집의 수거를 못마쳐서 다시 가는 일”을 막으려 했던 시도였다.
하지만 이런 방법은 “택배를 가는 길에 줘서 cap을 미리 늘려놓는 경우”가 존재하기에 실패했다.
즉, 택배를 버릴게 아니라 “현재 택배를 줘야하는 제일 먼 집”에 먼저 줬었다면 그 집의 택배 배송도 가능했던 상황이었던 것.
그렇다고 어디서부터 택배를 줘야 가장 먼 집의 택배를 최우선적으로 준 것과 같은 결과를 얻을 수 있는지 알 수 없기에 실패했다.
두번째 풀이는 해답을 읽고 작성했다.
스택을 활용하여 “제일 먼 집에 가는 길에” 가면서 택배를 다 주고
돌아오면서 수거를 전부다 하는 방식이었다.
제일 먼 집은 배달/수거 중 하나라도 남아있는 가장 먼 집
제일 먼 집부터 확인하니 “가장 먼 집”이 택배만 남아있는 집이라면 에 최우선적으로 택배를 배송할 수 있고
가장 먼 집이 수거만 남아있는 집이더라도 가는길에 택배만 남아있는 집 중 제일 먼 집에 택배를 다 준 뒤
수거를 해오는 것과 같은 결과를 보여주는 방법이었다.
이런 접근으로 코드를 짰는데도 실패했었는데
택배, 수거 중 하나라도 남아있는 경우에 while문을 계속 실행해야 했지만
둘 다 남아있는 경우에만 실행하도록 잘못 작성했었기 때문이다.
n이 1인 케이스를 테스트 해봤으면 쉽게 알아챌 수 있었는데 엣지케이스 테스트를 너무 늦게했다.
스택, 큐, 힙 등의 기본적인 자료구조를 단순히 알고만 있는게 아니라 어떻게 응용하는지에 대해 연습을 통해 알고 있었어야 풀 수 있는 문제였다.
밑의 글은 다른 방법으로 소개되어있는 방법인데
지금 내 실력으로는 절대 시간안에 떠올릴 수 있는 방법이 아니기에 읽어만 보기로 했다.
그리디 전략을 쓰지만 스택을 사용하지 않는 풀이 방법도 있습니다. 가장 먼 집부터 배달 상자 수와 수거 상자 수를 각각 누적 합을 구한 후, 둘 중에 하나가 cap을 넘는다면 누적한 배달 상자 수와 수거 상자 수를 각각 cap만큼 비우면서 이동한 거리를 answer에 더하는 방법입니다. 여기서 이동한 거리를 구하기 위해 상자가 비워질 때의 위치를 저장해 둡니다. cap만큼 비우면서 누적 배달 상자 수 또는 수거 상자 수가 음수가 될 수 있습니다. 누적 상자 수가 cap만큼 덜 채워졌을 경우로, 다음 집의 상자를 미리 배달하거나 수거하는 효과를 가져서 음수가 되어도 괜찮습니다.
3. 이모티콘 할인행사
브루트포스를 써야하는 문제라는건 쉽게 알 수 있었고, 이모티콘 할인율 순열이 필요했는데
1
2
3
4
let format = "%0" + String(emoticons.count) + "d"
// ...
let discountPercentArr = Array(String(format: format, Int(String(i, radix: 5))!))
.map { Int(String($0))! * 10 }
위의 방법으로 어렵지 않게 구할 수 있었다. (경우의수를 n진수(i)로 환산해서 모든 케이스를 커버)
이모티콘을 전부 둘러보기에 큰 문제가 없었지만 n개를 뽑는 경우를 대비하기 위해 순열과 조합을 만드는 코드도 공부해야겠다.
4. 표현 가능한 이진트리
“포화 이진트리”를 만드는 방법을 잘못 이해했다.
문제에서 포화 이진트리를 만들때 “루트 노드”는 그대로 둔 채 나머지 노드를 모두 더미노드 (0)으로 채우라고 했었는데
이 뜻은 어떤 포화트리의 특정 서브트리가 모두 더미노드로 이루어져있더라도 상관이 없다는 의미였다.
하지만 나는 leaf 노드가 아닌 노드가 0이면 무조건 valid하지 않다! 라고 접근해버렸고 계속해서 틀렸다.
만약 내가 세운 가설이 맞았더라면 단순히 홀수번째 index가 모두 1인지를 확인해서 답을 내도 맞았어야 했는데 (실제로 처음에는 이런 코드를 제출했었다.) 그러지 않았을 시점에 "가설" 자체가 잘못된 것이 아닌가를 의심했어야 했다.
5. 표 병합
root 노드로 Merge 상태를 관리하는 아이디어는 잘 세웠다.
표의 사이즈가 50x50이니 매 command마다 순회해도 상수시간으로 취급할 수 있단걸 파악한 것도 좋았다.
다만 Merge가 무조건 a -> b 가 아닌 a와 b 중 “값이 있는 쪽”으로 합쳐진다는 점을 50점을 받고 나서 문제를 다시 읽으며 확인했다. (둘 다 있으면 a로 합쳐짐)
Array의 repeating, count init을 통해 배열을 초기화하면 내부의 값들이 모두 같은 주소값을 지니게 되는걸 오랜만에 다시 보았다. (cow)
확실하게 하기 위해서 for문으로 초기화시켜주는게 혼란 방지에 좋을 것 같다.
6. 미로 탈출 명령어
앞선 문제들과 다르게 최적화를 통해 시간초과를 해결하는게 주가 된 문제였다.
첫번째로 시간초과를 받고 해결한 문제는 결과값들을 sorting하는 부분이었다.
dfs를 통해 문제를 해결하니 애초에 알파벳순으로 이동하면 (d l r u) 처음 나온 답이 정답이었다.
두번째로 고친 부분은 “목적지”에 도달했다가 나갈 수 있는 부분이었다. k번의 move를 통해 목적지에 가있는 것이 목표이기 때문에 목적지에 도달했다고 return하면 안됐었다.
이렇게 해도 시간초과가 떠서 더 최적화 할 수 있는 방안을 고민하다가 찾은 것이 “유망하지 않으면 더이상 진행하지 않기” 였다.
현재 위치로부터 목적지까지의 최소 이동거리는 단순히 현재 x,y좌표 - 목적지 x,y 좌표이므로
남은 이동횟수가 남은 최소 이동거리보다 크다면 절대 도달할 수 없는 것이므로 바로 return을 해주었다. (정답)
7. 1,2,3 떨어트리기
한 3시간 주고 이거만 풀게 했으면 풀었을지도 모르겠다.
일단 노드가 모두 들어가긴 하는지 체크하기, 들어간 노드가 maximum을 초과하지 않는지 체크하기
이 두 체크를 하는건 잘 했다.
하지만 이 뒤에 이제 어떻게 그리디하게 1,2,3 중 하나를 넣을 것인가에 대한건
곁에 딸린 또 다른 문제를 풀어야 하는 느낌이라 아마 시간 내에는 못풀었지 싶다.
접근 자체는 괜찮았던 것 같아서 다행이다.
