[프로그래머스] 완주하지 못한 선수

이 글에서는 프로그래머스 - 완주하지 못한 선수 문제에 대해 다뤄보겠습니다. 문제 풀이는 C++로 이루어져 있고 함께 들어가 있는 개념들도 간단히 정리 해보는 형식으로 작성되었으므로 오타등의 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요?

 

Level 1 에 있던 문제라고 쉽게 생각했던 것인지 문제를 열어보고 읽었을 땐 아주 잠깐 물음표가 머릿속을 떠나지 못했습니다. 못풀겠어서가 아니라 문제의 분류가 Hash에 되어있었기 때문이죠. 문제를 간단히 살펴볼까요?

 

두개의 배열 participant(마라톤에 참여한 선수들의 이름)와 completion(완주한 선수들의 이름)이 주어집니다. 단 한 명의 선수를 제외하고 모든 선수가 마라톤을 완주하였을 때 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성하세요.

---

사실 문제를 보고 나서 바로 "sorting 해서 for문으로 1:1 비교해보면 되는거 아니야?" 이런 생각이 든건 저만은 아니..겠죠? 보자마자 "아 hash 문제네~" 하시는 분들.. 계셨나요? 일단은 가장 직관적이고 이렇게 풀어도 통과는 되는 방식으로 먼저 풀어보겠습니다.

풀이 1

 

(워낙 최근까지 있었던 교환학교 난양공대에서 well commented code를 선호해서 그런지 저런 간단한 반복문에도 한줄 한줄 주석 달고 있는게 신기합니다. 습관이란 증멜...ㄷㄷ)

 

풀이를 대충 풀어보면 아래와 같이 그려질 수 있을 것 같습니다. 완주하지 못한 선수가 1명이라서 아마 Level 1으로 분류된 것 같은데 어쨌든  5명의 참가자가 있다고 한다면 완주한 선수는 무조건 4명이 됩니다. 이름 순으로 정렬을 하고 동일 인덱스에 동일 인물이 있다면 지나가고, 다른 인물이 있다면 Participant의 인덱스에 해당하는 사람이 완주하지 못한 인물이 되겠습니다. 

채점 결과  : 정확성 테스트(50.0) + 효율성 테스트(50.0) = 100.0

---

풀이 2

저는 c++ 경험이 많지 않고 깊게 파보지 않아서(이제 파야죠 이제 파봐야지...) 많은 분들이 map과 unordered_map으로 풀이하는 것이라고 설명을 해 놓으셨더라구요. 처음 보는 것이라서 일단 제가 개인적으로 좋아하는 블로거인 '소년코딩'님 코드를 가져와 보았습니다.

출처 : https://boycoding.tistory.com/226

---

풀이 3

그리고 list를 써서 hash table과 collision handling 방식을 separate chaining으로 만들어서도 구현할 수 있죠.ㅋㅋㅋ 굳이? 라고 여쭤보신다면 네, 저 이런거 좋아해요ㅋㅋㅋ 솔직히 말하면 좋은 방법은 아닙니다. sorting 없이는 시간초과가 나기 때문에 더 쉽게 풀이1 번으로 풀 수 있는 것을 굳이굳이 길게길게 풀이3으로 풀 필요가 없으니까요ㅋㅋ

 

이 코드가 생각난 배경을 말하자면 사실 Hash라는 말을 보자마자 hash table과 linked list로 구현하는 chaining이 제일 먼저 생각이 났습니다. c++의 list의 경우 doubly linked list와 같이 구현이 되어 있으므로 "아 얘 써서 만들면 되겠다" 싶었던 것입니다.

list<string> table[26]은 각 table[i]는 이름의 시작 알파벳이 같은 완주자들을 모아 놓게 됩니다. 가령 "beth", "bobby", "ben"은 모두 table[1]에 linked list로 주루루륵 연결이 되어 있게 됩니다. 그리고 나서 비교를 하는 셈입니다. //search 라는 주석 밑에 있는 코드 중 it = table[index].erase(it)가 있는 이유는 동명이인 때문에 구현된 부분입니다. 한 번 비교한 인물은 지워버리는 것이죠.

 

채점 결과  : 정확성 테스트(50.0) + 효율성 테스트(50.0) = 100.0