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

문제 풀면서 작성한 메모

풀이 과정

---

문제 설명

 

문제는 생각보다 쉬웠다. 특히 완주하지 못한 선수가 항상 1명이라는 점이 이 문제를 더 쉽게 만든 것 같다. 매개변수와 반환 값에 대한 설명에서 participant는 참여한 선수들을 담은 배열이고, completion은 완주한 선수들을 담은 배열이라는 것을 파악하고 간단하게 메모했다. 완주하지 못한 선수 return해야 하는 것도 메모했으면 좋을 것 같다.

 

지난 실수들을 생각하면서 이 문제에서 어떤 알고리즘 개념을 요구하는지 생각해보았다. 배열 요소 하나하나를 for문으로 탐색해야 한다는 점에서 탐색 알고리즘, 길 찾기 알고리즘이 생각나서 메모했다. 지금 검색해보니 탐색 알고리즘과 길 찾기 알고리즘은 완전히 다른 거고(^^) 탐색 알고리즘은 사실 처음 봤다. 학교에서 들은 <자료구조> 수업에서는 배우지 않았던 내용이었다. 아무튼 알고리즘도 모르는데 어떻게 사용하겠냐! 그래서 이번 문제에서는 알고리즘을 적용하지 못했다. 문제 풀고 찾아보려 했는데 생각해보니 내가 시험 치는 것이 아니라 연습하고 있는 거니까 앞으로는 문제 풀면서도 알고리즘을 찾아봐야겠다.

 

 

def solution(participant, completion):
    answer = participant - completion
    return answer[0]

 

오류

 

처음에는 리스트끼리 더할 수 있다는 생각이 나서 리스트끼리 빼보았다. 하지만 역시나 리스트끼리 빼기는 지원하지 않았고(만들어주라주) 튜플끼리는 될까 싶어서 리스트를 튜플로 바꿔서 빼보았으나 튜플끼리도 빼기를 지원하지 않았다. mutable한 객체가 안되면 immutable한 객체는 혹시 될까 싶어 해 본 건데 지금 보니 말도 안 되는 생각이었다^^~!

 

def solution(participant, completion):
    participant_dict = dict.fromkeys(participant, 0)
    completion_dict = dict.fromkeys(participant, 0)
    for p in participant:
        participant_dict[p] += 1
    for c in completion:
        completion_dict[c] += 1
    for key, value in completion_dict.items():
        if completion_dict[key] != participant_dict[key]:
            answer = key
            return answer

 

동명이인이 문제가 된다면 이름을 key로, 그 이름이 몇번 나왔는지를 value로 하는 딕셔너리를 만들어 비교하면 어떨까 하는 생각이 들었다. participant가 completion보다 1명 더 많은 배열이므로 우선 2-3번째 줄에서 participant 배열에 있는 이름을 key로 갖고 초깃값으로 0을 value로 가진 딕셔너리 두 개를 생성했다.(participant 딕셔너리와 completion 딕셔너리를 비교할 예정) 그리고 participant 배열에 있는 선수의 이름을 하나하나 돌면서 그 선수 이름이 몇 번 나왔는지를 카운트했다. 마찬가지로 completion 배열도 똑같이 카운트했다. 그러면 participant 딕셔너리와 completion 딕셔너리는 서로 key값은 동일하나 단 하나의 key값에서 value가 다를 것이다. 이제 그걸 찾으면 된다.

 

그런데 만들고 보니 너무 비효율적이라는 생각이 들었다. 어차피 딕셔너리끼리 뺄 수 있는 것도 아닌데 뭣하러 같은 일을 이중 삼중으로 하는거지?ㅎㅎ 일단 이왕 시작한 거 끝은 내려고 끝까지 만들었다. 참고로 딕셔너리 함수는 아래 링크에서 도움을 받았다.

파이썬 코딩 도장: 25.1 딕셔너리 조작하기

 

엥

결과는 성공이었다. 일단 효율성에서 통과한게 놀라웠다. 그렇지만 비효율적인 코드라는 생각이 지워지지 않았다.

 

def solution(participant, completion):
    for c in completion:
        if c in participant:
            participant.remove(c)
    answer = participant[0]
    return answer

 

좀 더 쉽게 풀 수 있는 방법이 없을까 하다가 이름이 같으면 삭제하는 방법을 생각해냈다. 그러면 결국 완주하지 못한 선수 한 명만 남을 테고 그걸 return하면 된다!

 

엥?

뭐지?ㅋㅋㅋㅋ 이게 훨씬 효율적이고 직관적이고 간결한 코드라 생각했는데 효율성에서 시간 초과로 실패가 나왔다. 다시 생각해보니 제한 사항에서 마라톤 경기에 참여한 선수의 수가 1명이상 100,000명 이하라고 했는데 여기서 효율성 문제가 생기는 것 같다. 아니 근데 아무리 생각해도 앞선 코드는 어떻게 효율성을 통과한 거지? 딕셔너리가 시간적인 면에서 그렇게 빠른가?

다른 사람의 풀이

---

collection 라이브러리에서 Counter 함수 사용

좋아요를 가장 많이 받은 풀이인데 너무 간결해서 놀랐고 collections라는 라이브러리를 처음 봤다. Counter 객체를 사용하면 딕셔너리도 뺄 수 있다는 점!!! 미쳤다. 이건 꼭 기억해놔야겠다. 검색해보니 교집합과 합집합도 구할 수 있고 난리난다. 밑의 링크를 참고하세요!

[파이썬 기초] Counter를 이용한 항목 계산

hash 함수 사용

이 풀이는 좀 창의적이다. 해시 개념과 hash 함수를 처음 알게 되었는데 개념 설명은 뒤에서 하기로 하고, hash 함수를 이용하면 같은 이름의 선수라도 hash값이 다르다. 이 hash값을 key로, 원래 이름을 value로 하는 딕셔너리를 만들었다. 여기서 내가 창의적이라고 말한 부분은 7번째, 9번째 줄이다. participant 배열을 돌면서 hash값을 temp에 다 더하고 completion 배열을 돌면서 hash값을 다 뺀다. participant 배열이 completion 배열보다 1개가 모자라니 temp에는 완주하지 못한 선수의 hash값만 남는 것이다! 생각지 못한 풀이에 놀랐다. 하지만 hash 충돌에 주의해야 한다. 참고로 hash 함수에 대한 설명은 아래 링크에 잘 나와있다.

17. 해싱(hashing), 파이썬

 

정렬을 이용한 방법

가장 직관적이고 쉬운코드였다. 정렬을 왜 생각하지 못했을까? 정렬해놓고 배열 원소 하나하나 돌면서 값이 다르다면 return하는 것이다. 그런데 7번째 줄이 잘 이해가지 않았다. DawonChoi님의 댓글을 보고 알게 된 것인데, 동명이인의 참가자가 정렬되었을 때 마지막에 위치하면 completion의 길이가 participant의 길이보다 1이 작기 때문에 for문에서 선별이 안된다고 한다. 그래서 for문을 돌고도 선별이 안되었을 때 participant의 마지막 index에 있는 선수를 return하는 것이다. 예를 들어 정렬 후 pariticipant가 [a, b, c, c]이고 completion이 [a, b, c]라고 하자. for문은 completion 배열의 길이로 돌기 때문에 participant에 마지막 index에 있는 c는 보지 못하는 것이다. 그래서 이 경우 따로 return문을 더해주었다.

개념 정리

---

해시(Hash)

input data를 고정된 길이의 숫자열로 변환한 결과물

ex) "leo"라는 input data를 hash 함수에 넣어주면 hash("leo")의 결과는 -7735645008981088471

해시 테이블(Hash Table)

출처: https://en.wikipedia.org/wiki/Hash_table

키(Key)에 데이터(Value)를 저장하는 데이터 구조

ex) 파이썬에서 딕셔너리 타입이 해시 테이블의 예

해시 충돌(Hash Collision)

input data를 hash 값으로 바꿔주는 과정에서 두 데이터가 다른 문자열임에도 불구하고 같은 hash 값으로 변환되는 경우로, 해시 충돌을 해결하는 방법에는 오픈 해싱, 클로즈 해싱이 있다.

1. 오픈 해싱(Open Hashing), 분리된 체인(Separate Chaining)

출처: https://en.wikipedia.org/wiki/Hash_table

먼저 저장된 데이터에 linked list를 이용하여 중복되는 hash 값 연결

2. 클로즈 해싱(Close Hashing), Linear Probing, Open Addressing

출처: https://en.wikipedia.org/wiki/Hash_table

해시 중복이 발생하면 해당 해시 값부터 순차적으로 빈공간을 찾아 가장 처음 찾는 빈 공간에 key와 value를 저장

탐색 알고리즘 (Search Algorithm)

1. 순차 탐색(Sequential Search), 선형 탐색(Linear Search)

앞에서부터 순서대로 하나씩 확인하면서 결과를 찾을 때까지 탐색하는 방법

- 시간 복잡도: $O(N)$

- 장점: 단순하고 이해하기 쉽고 구현하기 쉬움

- 단점: 효율은 좋지 않음

2. 이진 탐색(Binary Search)

※미리 오름차순이나 내림차순으로 정렬되어 있는 경우 사용 가능

탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

- 시간 복잡도: $O(logN)$

- 장점: 평균적으로 이진 탐색이 선형 탐색보다 빠름

 

출처: https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

3. 해시 탐색(Hash Search)

데이터의 '내용'과 저장한 곳의 'index'를 미리 연결해 줌으로써 탐색할 자료를 짧은 시간 안에 탐색

ex) 36인 데이터는 index 36에, 48인 데이터는 index 48에 두는 식

- 시간 복잡도: $O(1)$

- 장점: 원하는 데이터 index로 접근하여 바로 찾을 수 O

- 단점: 위의 예시의 경우 2개의 데이터만 저장해도 49개의 index를 가진 배열이 있어야 하므로 공간 낭비가 심한 편, 이를 해결하기 위해 나누기, 나머지 연산을 이용해 저장하는 방법이 있음

 

해시 문제였다!

문제 풀 때는 해시를 몰랐다. 그래서 해시라고 적힌 것을 보고 그냥 넘어갔다.. OTL 그리고 크레인 인형뽑기 게임 때만 해도 저 "해시" 자리에 "2019 카카오 개발자 겨울 인턴십"이라 적혀서 주최사 이름인가도 했다(^^)

 

def solution(participant, completion):
    answer = ''
    temp = 0
    dic = {}
    for part in participant:
        dic[hash(part)] = part
        temp += int(hash(part))
    for com in completion:
        temp -= hash(com)
    answer = dic[temp]

    return answer

 

해시 개념도 배웠고 해시 탐색도 배웠으니 위에서 본 다른 사람의 풀이 중 hash 함수 사용을 다시 보자. 이 예제가 해시를 가장 잘 사용한 풀이이다. 여기서는 data가 숫자형이 아닌 문자열이다. hash 함수를 이용해 참가 선수의 이름을 고유한 hash값으로 만들어줘야 한다. 이 hash값이 key이고, 원래 이름은 value에 저장하면 해시 테이블이 완성된다. 여기서 문제가 하나 있는데, 동명이인의 경우 hash 함수를 적용해도 같은 hash값이 만들어진다. 따라서 동명이인 중 한명이 완주하지 못했을 때 어떻게 찾아낼지는 위의 예시처럼 hash 값을 다 더하고 빼는 방법을 쓰면 된다.

코드

---

GitHub - leeejihyun/algorithm: 알고리즘 문제 풀이

출처

---

프로그래머스 코딩 테스트 연습 https://programmers.co.kr/learn/challenges

탐색 알고리즘 https://velog.io/@dlrmsghks7/탐색-알고리즘을-알아봅시다

순차 탐색 https://www.fun-coding.org/Chapter16-seqsearch.html

이진 탐색 https://www.fun-coding.org/Chapter16-binarysearch.html

해시 탐색 https://excelsior-cjh.tistory.com/125

해시 테이블 https://jinyes-tistory.tistory.com/10

해시 https://www.fun-coding.org/Chapter09-hashtable.html

hash 함수 https://lsjsj92.tistory.com/160