프로그래머스 알고리즘 고득점 Kit - 해시(Level1 모두 Level2 하나)

푸는 과정은 일단 다 풀어보고 이해하게 된 점 정리와 사용된 자료구조를 정리하는 방식으로 진행할 것이다.

 

---

폰켓몬 문제

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
• 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

---

입출력 예numsresult

[3,1,2,3]	2
[3,3,3,2,2,4]	3
[3,3,3,2,2,2]	2

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리, 2번 폰켓몬 한 마리, 4번 폰켓몬 한 마리를 고르면 되며, 따라서 3을 return 합니다.

입출력 예 #3
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리와 2번 폰켓몬 두 마리를 고르거나, 혹은 3번 폰켓몬 두 마리와 2번 폰켓몬 한 마리를 고르면 됩니다. 따라서 최대 고를 수 있는 폰켓몬 종류의 수는 2입니다.

 

문제 풀이

풀이1

def solution(nums):
    setNums = list(set(nums))
    countMonster = len(setNums)
    
    if countMonster <= (len(nums)/2):
        return countMonster
    elif countMonster > (len(nums)/2):
        return (len(nums)/2)

 

처음에는 뽑는 경우의 수를 모두 가져오고 종류를 확인할려고 했는데, 코드를 작성하는 과정에서 너무 복잡하다는 생각에 다시 문제를 확인했다. 결론적으로 뽑을 수 있는 폰켓몬의 수는 정해져 있으므로 그 이상으로 여러 종류의 폰켓몬을 뽑을 순 없다.
따라서 뽑을 수 있는 수보다 종류가 적거나 같으면 가장 많이 뽑는 수는 뽑을 수 있는 수 그 자체가 될것이고,

뽑을 수 있는 수보다 종류가 적다면 무조건 파라미터로 받는 나열에 있는 종류의 수가 가장 많이 뽑은 종류의 수가 될것이다.

이 생각으로 위와 같이 풀었다.

 

풀이 2

근데 이는 더 간다한게 min 내장 함수를 통해 풀 수 있는데 그 풀이는 다음과 같다.

def solution(nums):
	return min( len(set(nums)), (len(nums)/2) )

 

위에서 작성한 코드와 똑같은 기능을 하지만 min을 이용에 훨씬 간결하게 짤 수 있다.

---

완주하지 못한 선수

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

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

제한사항

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

입출력 예participantcompletionreturn

["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

입출력 예 설명

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

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

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

 

문제 풀이

그 전 포스팅에서 적긴 했는데, 문제를 풀면서 느낀 것이 먼저 문제의 의도를 정확히 파악하고 머리로 알고리즘을 설계하는 것이 더 중요한 것 같다.

 

처음에는 set 함수를 이용해서 풀려고 했는데 set을 이용하면 동명이인을 잡아낼 수 없어 문제가 됐다. 그 다음에는 참여자 명단이랑 완주자 명단을 비교하며 참여자 명단에서 완주자 명단에 있는 사람을 없애려고 했는데, 이는 설정한 len(참여자명단)이 실시간으로 바뀌기 때문에 for문에서 에러가 나 실행하지 못했다.

 

그래서 hash를 이용해 풀었다.

주어지는 선수의 수는 100000이하기 때문에 O(NlogN) 이하의 시간으로 풀어야한다.

 

풀이 1

특정 문자열은 고유한 해시값으로 변환되기 때문에 이를 이용했다.

참여자 명단의 이름들을 해시로 변환해 더하고, 똑같이 완주자 명단의 이름들을 해시로 변환해 더했다.

그리고 빼면 특정 해시값이 나오고 그 해시값에 해당하는 이름을 가져오면 완주하지 못한 사람이다.

   

틀린 처음 풀이

def solution(participant, completion):
    mydict = dict()
    
    for i in participant:
        mydict[hash(i)] = i
    
    sumPartKey = sum(mydict.keys())
    sumComp = sum(map(lambda x : hash(x), completion))

    NotCompleteHash = sumPartKey - sumComp
    return mydict[NotCompleteHash]

 

이 방식은 오류가 났었다. 그 이유는 반복문으로 딕셔너리를 만들때 동명이인은 같은 키로 들어가기 때문에 위에서 만들어진 mydict은 동명이인을 받아도 하나로 넣어버린다. 그렇기 때문에 sumPartKey에서 sumComp를 빼면 해시값이 아닌 숫자가 나와 동명이인을 입력 받았을 때는 오류가 발생한다.

 

맞는 풀이

def solution(participant, completion):
    mydict = dict()
    sumPartKey = 0
    for i in participant:
        mydict[hash(i)] = i
        sumPartKey += hash(i)
        
    sumComp = sum(map(lambda x : hash(x), completion))

    NotCompleteHash = sumPartKey - sumComp
    return mydict[NotCompleteHash]

 

딕셔너리를 만들 때, 넣는 값들을 바로바로 더해줘서 위에서 있었던 문제를 해결할 수 있다.

 

풀이 2

collection 모듈의 Counter를 이용한 풀이 방식이다. Counter을 이용하면 배열에 각 원소들의 갯수가 몇개인지 뽑아주는데 참여자 명단과 완주자 명단에 적용을 하고 빼주면 완주하지 못한 참여자를 구할 수 있다. 

딕셔너리 끼리는 뺄 수 없지만 Counter를 통해 객체로 바뀌었기 때문에 빼는 것이 가능하다.

import collections

def solution(participant, completion):
	answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys()[0])

---

전화번호 목록 문제

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

입출력 예제phone_bookreturn

["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

이 문제를 풀기 위해선 문자열 비교하는 것을 알아야한다.

• 완전 일치 : == !=
• 부분 일치 : in not in
• 전방 일치 : startswith
• 후방 일치 : endswith

위와 같이 비교를 할 수 있고 전방과 후방 일치는 문자열2. startswith / endswith (문자열1) 방식으로 사용하고 문자열1일 문자열2에 있는지 찾는 것이다.

 

그리고 정렬하는 기준에 대해 알아야한다. 배열의 원소가 정수형이나 실수형이라면 정렬의 기준의 숫자의 크기이지만 문자열인 경우는 제일 앞에 있는 문자를 기준으로 정렬한다. 제일 먼저 오는 문자 순으로 정렬한 후의 그 뒤에 오는 문자를 기준으로 다시 정렬한다. 예를 들어 133이 1222보다 작지만 1 다음으로 오는 2가 3보다 작기 때문에 ['133', '1222']를 sort하면 ['1222', '133']으로 정렬된다.

 

예를 하나 더 들어서 설명하자면,

[12, 134, 34, 456]에 sort()를 해주면 [12, 34, 134, 456]으로 정렬되고,

['12', '134', '34', '456']에 sort()를 해주면 다음과 같이 정렬한다. ['12', '134', '34', '456']

 

이러한 특성을 이용해 문제를 풀 수 있다.

 

파라미터로 오는 배열을 정렬하면 문자열 a가 그 다음에 오는 문자열 b에 포함되는지만 확인하면 되니까 먼저 배열을 정렬해준 뒤, 바로 옆에 있는 문자열끼리만 비교해주면 된다.

def solution(phone_book):
	answer = True
    phone_book.sort()
    
    for i in range (len(phone_book)-1):
    	if phone_book[i+1].startswith(phone_book[i]):
        	answer = False
            break
	retrun answer

 

이렇게 작성할 수 있다