[프로그래머스] 코딩테스트 연습 - 해시 (Python3, 파이썬)

프로그래머스 - 해시

 

1. 완주하지 못한 선수

문제

코드

def solution(participant, completion):
    
    participant.sort()
    completion.sort()
    
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[-1]

 

참가한 선수들과 완주한 선수들이 각각 담긴 리스트가 2개 주어진다.

먼저, 두 리스트를 sort함수로 정렬해준다.

그 후 for문으로 둘을 비교하며 완주한 선수 목록에 없는 선수를 찾아줘야 한다.

for문의 반복 횟수는 완주한 선수 리스트의 길이로 한다.

참가한 선수 리스트의 길이로 할 경우 완주한 선수 리스트에는 없는 index로의 접근이 발생할 수 있다.

반복문 안의 if문으로 정렬된 두 리스트를 비교하여 서로 다를 때 참가자 리스트의 해당 index 값을 출력하고

참가자 리스트의 가장 마지막 인덱스의 값이 답일 경우를 고려해 인덱스가 -1인 값을 리턴해주는 코드도 추가했다.

 

참고 : https://coding-grandpa.tistory.com/85

 

2. 전화번호 목록

문제

코드

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
    
    return answer

전화번호부 목록 중 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 출력해야 한다.

일단 phone_book 리스트에 번호들이 정렬되어 있지 않으므로 sort 함수로 정렬한다.

정렬을 했으므로 길이가 짧은 전화번호가 앞쪽 index에 위치하고 연속된 index의 관계에서 다른 번호의 접두어인 경우를 발견할 것이라고 예측 가능하다.

for문을 phone_book 리스트의 길이 -1 만큼 반복하고 if문을 넣어 다음 인덱스의 값 접두어가 해당 인덱스의 값인지 비교해준다.

이 때 startswith을 썼다.

이 함수는 문자열이 특정문자로 시작하는지 여부를 true, false로 반환해준다.

인자에 string값과 tuple만 올 수 있다.

if문이 true일 경우 answer 값을 false로 바꿔주고 break문을 써줬다.

 

참고 : 너무 다양한 블로그를 봤는데 링크를 복사 안 해둬서 다시 찾으면 적겠다.

 

3. 위장

문제

코드

def solution(clothes):
    dic = {}
    for name, kind in clothes:
        if kind not in dic:
            dic[kind]=1
        else:
            dic[kind]+=1
    answer = 1
    for i in dic.values():
        answer*=(i+1)
    return answer-1

clothes라는 2차원 배열이 주어진다. 2열에는 의상의 종류가 1열에는 의상의 이름이 들어가는 2열 n행 배열입니다.

같은 종류인 의상은 하나만 입을 수 있다는 사실을 기억하며 딕셔너리를 활용해줍시다.

딕셔너리 하나를 생성합니다. for문과 if문으로 딕셔너리에 의상의 종류마다 옷이 몇 개 있는지 저장해줍니다.

결과를 출력할 때 모두 입지 않는 경우를 빼줍니다.

 

참고 : https://it-garden.tistory.com/388

 

 

4. 베스트앨범

문제

코드

from collections import defaultdict

def solution(genres, plays):
    answer = []
    
    dic = defaultdict(int)
    result = defaultdict(list)
    
    i=0
    for g,p in zip(genres,plays):
        dic[g] += p
        result[g].append((i,p))
        i += 1
        
    dic = sorted(dic.items(), key= lambda x:x[1], reverse = True)
    
    for b in dic:
        result_1 = sorted(result[b[0]], key=lambda x:x[1], reverse = True)
        
        answer.append(result_1[0][0])
        
        if len(result_1) > 1:
            answer.append(result_1[1][0])
                
    return answer

defaultdict를 활용해줍니다. defaultdict는 딕셔너리의 초기값을 생성해줍니다.

장르와 플레이 수를 반복문으로 zip으로 묶어 반복하면서 딕셔너리 두 개에 각각 값을 추가해줍니다.

dic 이라는 이름의 딕셔너리는 어떤 장르가 플레이 수가 가장 많은지 장르끼리 비교하기 위해 사용합니다.

result라는 이름의 딕셔너리는 장르 안에서의 각 음악 index와 플레이 수를 저장해주기 위해 사용합니다.

반복문을 한 번 돌린 후 dic 딕셔너리를 내림차순으로 정렬해줍니다.

두 번째 반복문은 베스트 앨범에 최종으로 값을 넣어주기 위해 내림차순으로 result의 값을 정렬합니다.

또 안의 if문을 통해 플레이 수가 같을 경우 고유 번호가 낮은 값을 append 해줍니다. 

 

 

참고 : https://soohyun6879.tistory.com/113