안녕하세요 기린입니다 :=)
저는 요즘 프로그래머스에서 진행하고있는
[커뮤러닝/5기/C++] 코딩테스트 실력 UP 패키지: 문제 풀이 꿀팁과 실전 모의고사 with C++
을 들으며 알고리즘 공부를 하고있는데요 내일 배움 카드로 수강하면 수강료가 3만원이고 수강 완료시 전액 환급해주는 아주 좋은 강의랍니다! 광고아님 https://programmers.co.kr/learn/courses/13557
그럼 바로시작해볼게요 :] '완주하지 못한 선수' 문제를 한번 풀어보도록 하겠습니다.
완주하지 못한 선수
문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
문제 파악을 한번 해볼게요 먼저 제한사항을 잘 확인해 보셔야합니다.
1. 마라톤 경기에 참여한 선수 = participant 은 10만 이하의 길이를 가질거고 completion의 길이는 participant의 길이보다 1작다.
2. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있다는데 이 문제에서는 큰 의미는 것 같습니다.
3. 참가자 중에는 동명이인이 있을 수 있습니다. <- 중요한 제한사항이겠죠 동명이인 처리를 꼭 해줘야할 것 같습니다.
만약 제한사항과 문제파악이 어렵다면 문제에서 제공해주는 입출력 예를 보며 확실하게 먼저 파악해주시는것이 가장 중요할것 같습니다. :)
이제 문제를 풀어봐야겠죠 먼저 동명이인이 있다고 했으니 즉 이름값을 키값으로 두고 같은 이름이 몇 명인지를 파악하여 완주한 사람의 이름과 비교해보면 완주하지 못한 참여자를 알아낼 수 있을것 같습니다.
자 그럼 자료구조(와 알고리즘)의 선택을 해야겠죠
만약 이름 대신 번호가 주어졌다면 ? 선형 배열 (linear array)에 데이터를 저장할 수 있을겁니다. 하지만 저희는 참여자의 이름(문자열)로 접근할 수 있는 자료구조를 찾아야 합니다.
그래서 해시(Hash)를 이용하여 처리할 수 있습니다.
해시는 키값에 따라 해시 테이블에 데이터 값들을 저장하는 구조입니다. 딱 저희가 원하는 자료구조인것 같죠 ?
위 그림과 같이 "leo"키의 데이터 값을 해시 테이블안 어떤 위치에 저장될지는 hash function을 통해 수행되며 이 저장 칸 하나를 해시 버킷(hash bucket)이라고 합니다. 다만, 여기서는 hash function를 어떻게 만드는지 대해서는 다루지 않도록 하겠습니다.
그럼 이 해시를 이용해서 어떻게 풀것인지 알아보겠습니다. 먼저, 입출력 예를 하나들어 풀어보겠습니다.
가장 먼저 participant의 mislav 라는 문자열에 1을 대응시키는 관계를 해시테이블에 등록합니다. 두 번째 stanko 에도 마찬가지로 등록합니다. 그 다음 mislav 참가자가 한번더 나왔을 경우 해시 테이블에 mislav에 대응되는 값 1을 2로 변경하여 등록합니다.
마지막 ana라는 문자열에 1을 대응시키는 관계를 해시 테이블에 등록하게 됩니다.
다음으로 completion에서 완주자 stanko 문자열에 대응하는 값 1을 완주했으니 0으로 변경해주고 ana도 완주했기에 1에서 0으로 감소합니다. 마지막으로 mislav 선수도 완주했기에 mislav에 대응하는 2를 1로 감소시켜줍니다.
따라서 mislav라는 문자열에 대응하는 값이 1이기에 mislav는 완주하지 못했으므로 mislav 문자열을 반환하면 정답이 되겠습니다. 이런 흐름을 그대로 코드로 옮겨 보겠습니다 : )
C++ 에서는 키와 밸류의 쌍을 나타낼 수 있는 데이터 타입이 존재하지 않습니다. 그러나 C++STL (Standard Template Library) 를 통해 가능하게끔 제공하고 있습니다. 키와 밸류를 쌍으로 나타낼 수 있는 데이터 타입중 std::map 과 std::onordered_map이 있습니다. 둘의 차이는 key에 의한 접근 시간의 차이가 있습니다. map의 경우 O(logN)의 시간이 걸리고 unordered_map의 경우 O(1)의 시간이 걸립니다. 이렇게 시간차이가 나는 이유는 unordered_map에서는 hash table 을 이용하여 key 값에 접근하는데 상수 시간이 걸리고 map의 경우는 주로binary serarch tree를 사용하기에 차이가 납니다.
자 그럼 저희는 unordered_map를 사용하면 hash table을 이용하는 거겠죠 ? 먼저 unordered_map을 사용하기 위해 아래와 같이 라이브러를 포함시키고 d라는 unordered_map 타입의 변수를 선언할 수 있습니다.
여기서 unordered_map<key, value> 로 구성한다는걸 알 수 있겠죠 ?
#include <unordered_map>
std::unordered_map<string, int> d;d라는 변수를 선언 후에
cout << d["leo"] << endl;
d["leo"] = 3;
cout << d["leo"] << endl;위와같이 실행한다면 첫번째 출력은 int 기본값인 0이 출력되고 두번째 행에서 3값을 입력하면 세 번째 행에서는 3이 출력되는걸 확인하실 수 있습니다. 이렇게 unordered_map은 어떠한 값을 처리할 때 상수시간만큼 접근이 가능하다는것이 즉, 속도가 빠른것이 특징입니다.
또 다른 특징으로 unordered_map에서 key 값과 value값을 얻기 위한 용어가 존재하는데 아래와 같습니다.
for (auto& i: d)
cout << i.first << "-" << i.second << endl;i.first는 key값을 i.second는 value값을 나타낼 수 있죠. 이 정도는 기억하시는게 코딩하는데 도움이 되실 것 같습니다.
이제 시간복잡도를 생각해보겠습니다 이 알고리즘의 시간 복잡도를 한번 살펴보겠습니다. 11행의 루프에서는 participant의 길이만큼 수행을하고 12행 루프에서는 participant의 길이보다 -1적게 수행을 하겠네요. 그리고 마지막 13행 루프에선 hash table을 사용하므로 i.second 와 i.first 를 찾는 과정을 포함하여 d의 길이 * 상수시간 이 되겠습니다. 이렇게 해서 제출하면 만점을 받으실 수 있습니다.
여기서 끝난게 아닙니다!!
# 만약 unordered_map을 사용하지않고 정렬을 이용한다면 ?
우리는 완주하지 못한 참여자가 단 한명이라는 조건을 가지고 있으므로 participant 와 completion vector를 정렬한 후 루프문을 돌려 해당 키값이 서로 같지않다면 그 참가자는 완주하지 못했다고 생각할 수 있겠죠 ?
위와 같이 코딩했을 경우의 시간복잡도를 살펴보겠습니다. 일단 배열을 정렬할 때는 O(NlogN)보다 더 낮은 복잡도를 가지는 알고리즘은 없습니다. 그러기 때문에 해당 알고리즘은 테스트는 통과하지만 효율성면으로 봤을때 Hash 구조를 이용한다면 복잡도가 상수시간만큼 된다는 것을 이용해 리니어 타임 알고리즘을 작성할 수 있으므로 onordered_map를 이용, 즉 hash 를 이용하는 것이 효율적이라는것만 알고가시면 될 것 같습니다 :)
자 그럼 즐거운 코딩하세요 :]
