학습 주제
해시 (Hash)

학습 내용

문제를 분석하고, 어떤 알고리즘을 선택하는 것이 좋을지,
그리고 코드는 어떻게 짜야하는지 알아본다

문제를 잘 읽어보고, 문제의 크기는 무엇에 지배되는지, 제한사항은 무엇인지,
어떤 조건이 주어지는지 지문으로 부터 명확히 알아야 한다.

문제

문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예

입출력 예 설명
예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

제한사항 분석

• 한명만 완주를 하지 못하였음

• 100,000 명이다 보니 대략 nlogn의 복잡도를 가진 연산을 생각해봐야함.

• 동명이인이 있을 수 있다보니, 차집합을 구할 수 없음.

• 마지막 예제 처럼 참여자 명단에 2명이 있지만, 완주자엔 한명 밖에 없어 한명은 완주하지 못한 것 처럼 다소 복잡한 경우가 됨.

• 이름이 주어지면 몇번이나 등장했는지 저장할 수 있어야함. (Hash와 연관)

자료구조와 알고리즘의 선택

• 만약 이름 대신 번호가 주어졌다면?
  • 선형 배열 (linear array)

해시(Hash)

문자열로 찾아갈 수 있는 방법

키 (key) 접근 할 인덱스 같은 존재
서로 다른 칸에 각각 value를 접근 할 수 있음
키가 몇번째 해시 테이블에 들어가는 지 결정하는 것은 hash function 을 가짐

value를 담는 각각의 칸을 해시 버킷이라고 함. 해시 버킷이 많을 수록 서로 다른 키가 서로 다른 버킷에 사상될 수 있는 가능성이 높아짐.

• 만일 다른 키가 같은 버킷에 사상되는 경우가 있는데 이를 충돌 (collision) 이라고 불리며 해결해야 될 문제이다.

해결 방법으로 해당 버킷 옆으로 버킷을 이어서 저장하는 방법 등이 있다.

이번 강의에선 hash function 은 다루지 않는다.

문제의 풀이 - 예제

mislav 참가자는2명, 완주자는1명.

mislav 1 을 대응하는 해시테이블에 기록
stanko 1 을 대응

mislav 2 대응
ana 1 값 대응

completion 배열도 찾아봄

stanko -1 감소 대응
ana 1 -> 0 감소 대응
mislav 2 - > 1 감소 대응

유일하게 mislav 선수만 0이 아닌 값을 가지고, 이는 완주하지 못한 인원이 있다는 말.

이를 코드로 구현할 수 있어야 한다.