프로그래머스/해시/완주하지 못한 선수

https://programmers.co.kr/learn/courses/30/lessons/42576

 

강의 듣기 전 풀이

- Java로 풀이

- 꼴찌는 완주에서 제외

- 동명이인 존재 가능

- 완주하지 못한 선수의 이름 return

 

1) string, int 해시맵을 작성

2) 완주한 선수 이름이 call될 때마다 해시값에 +1

3) 참가자 선수 이름으로 반복, 해시값에 -1

4) -1을 수행할 때, 해시값이 0보다 크지 않다면 해당 이름 리턴

 

class Solution {
    public String solution(String[] participant, String[] completion) {
        
        String answer = "";
        
        //해시맵 작성
        java.util.HashMap<String, Integer> hash = new java.util.HashMap<String, Integer>();
        
        //완주한 선수 이름이 불릴 때마다 해시값에 +1
        for (String e : completion){
            if(hash.containsKey(e)) hash.put(e, hash.get(e) + 1);
            else hash.put(e, 1);
        }
        
        //참가자 선수 이름으로 반복하여, 해시값에 -1
        for (String e : participant){
            
            //해시값이 0보다 커야 -1을 할 수 있음
            if(hash.containsKey(e) && hash.get(e) > 0){
                hash.put(e, hash.get(e) - 1);
            }
            else {
                answer = e;
                break;
            }
        }

        return answer;
    }
}

 

결과 

정확성 : 50.0 / 효율성 : 50.0 / 통과

 

강의 요약

- 강의는 C++이므로 C++로 진행 (본인 C++ 개초보)

- 해시테이블을 구현할 수 있는 map, unordered_map의 두 가지 STL이 존재

 

- key에 의한 접근 시간 차이

종류	실행시간	라이브러리 내부 구현
map	O(logN)	(주로) binary search tree
unordered_map	O(1)	hash table

 

- 배열 이터레이션 auto&

for (auto& e : array) 처럼 두면, 컴파일러가 알아서 추론함. C#의 var와 역할은 동일하다.

 

강의 풀이

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {

    string answer = "";

    unordered_map<string, int> hash;
    for (auto& i : participant) hash[i]++;
    for (auto& i : completion) hash[i]--;

    for (auto& i : hash) {
        if (i.second > 0) {
            answer = i.first;
            break;
        }
    }

    return answer;  
}

 

피드백

C++에서는 containsKey같은 검사 로직이 필요 없다는 것을 보고 충격먹었다.

없던 키에 접근하면 해시값이 기본값으로 생성된다니. 으음...