[프로그래머스 코테] 해시, 정렬 전문항 해설

해시

폰켓몬

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 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 함수를 완성해주세요.

 
N/2 종류 이상이 있으면, 종당 1마리씩 해서 N/2마리를 모두 데려올 수 있다. 그러나, N/2 종류보다 적으면 그 종류 수가 데려올 수 있는 최댓값이다. 따라서 아래와 같이 간단히 작성할 수 있다.

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

---

완주하지 못한 선수

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 
아래 입출력 예시와 같이 참가자 중에서 동명이인이 있을 수 있다는 점이 이 문제를 어렵게 만든다. 하지만, 동명이인일 경우 리스트를 sort하면 양 옆에 인접한다는 성질을 이용할 수 있다. 따라서, participant 리스트와 completion 리스트를 각각 sorting하고, 첫 번째부터 차례로 비교하여 차이 나는 첫 번째 선수 이름이 답이다.

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

---

전화번호 목록

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421
전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 
얼핏 보면 어렵고, 웬만한 알고리즘으로는 시간 초과가 난다. 하지만 머리를 조금만 굴려 보면 위 문제와 동일한 알고리즘을 쓸 수 있는데, phone_book을 sort하면 "접두사"인 번호와 "접두사를 가지는"번호가 반드시 인접해서 나온다는 것을 알 수 있다. 따라서 sorting한 후, 완전히 포함하는 서열이 있는지를 확인하면 된다. 이때 접두사는 접두사를 가지는 번호보다 짧아야 하므로, if문으로 길이비교를 해 주었다.

def solution(phone_book):
    sort_book = sorted(phone_book)
    for i in range(len(sort_book)-1):
        if len(sort_book[i])<len(sort_book[i+1]):
            if sort_book[i] == sort_book[i+1][:len(sort_book[i])]:
                return False

 
나중에 알게 된 메소드로, string에 쓸 수 있는 .startswith()는 해당 문자열로 시작하는지에 따라 True 혹은 False를 리턴하는데, 이를 사용해도 된다.

---

의상

 

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.
예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.

1) 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
2) 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
3) 코니는 하루에 최소 한 개의 의상은 입습니다.

코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

 
이 문제는 해시 테이블인 딕셔너리를 이용해서 풀었다. closet에 해당하는 딕셔너리(key: 카테고리, value: 옷 이름)를 잡고, 만약 해당 종류의 의상이 없었다면 새로운 key로 추가하고, 있었다면 value의 리스트에 append한다. 그리고 옷의 조합의 수는 곱의 법칙에 의해 간단히 처리할 수 있다.

def solution(clothes):
    closet = dict()
    for item in clothes:
        if item[1] in closet.keys():
            closet[item[1]]+=1
        else:
            closet[item[1]]=1
    temp =1
    for value in closet.values():
        temp*=value+1
    return temp-1

---

베스트앨범

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.
1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항
- genres[i]는 고유번호가 i인 노래의 장르입니다.
- plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
- genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
- 장르 종류는 100개 미만입니다.장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.모든 장르는 재생된 횟수가 다릅니다.

 
해시 파트에서 최종 보스(?) 격에 해당하는 유일한 3레벨 문제이다. 처음에 문제를 보고, 딕셔너리를 써야 할 것 같다는 생각이 들긴 했으나 노래의 인덱스를 가지고 genres와 plays를 계속 반복해서 호출하면 엄청난 시간 손실을 볼 것 같았다. 그래서 생각한 것이, 딕셔너리 안의 딕셔너리 구조이다. 해시 테이블로 된 딕셔너리 data를 잡고, keys를 장르 이름으로 설정한 다음 value로 새로운 해시 테이블을 만들어 {index : play 횟수} 형식으로 데이터를 저장하는 것이다. 이때 data를 전역변수로 잡았는데, 장르를 넣으면 총 재생횟수를 리턴하는 정렬함수 genre_total_plays를 별도의 다른 함수로 구현하기 위함이다. (원래 data까지 이 함수의 인자로 넣으려고 했으나, sorting의 key로 쓸 함수라면 인자를 하나만 받는 편으로 구현하는 게 좋을 것 같았다!!) 아래와 같이 코드를 작성하였다.

data = dict()
def genre_total_plays(genre):
    sum=0
    for play in data[genre].values():
        sum+=play
    return sum
    
def solution(genres, plays):

    for idx, genre in enumerate(genres):

        if genre in data.keys():
            data[genre].update({idx : plays[idx]})
        else:
            data[genre] = {idx : plays[idx]}
            
    genre_order = sorted(data, key = genre_total_plays, reverse = True)
    answer = []
    for genre in genre_order:
        lst = list(data[genre].keys())
        if(len(lst) == 1):
            answer.append(lst[0])
        else:
            lst.sort(key = lambda x:data[genre][x], reverse = True)
            answer.append(lst[0])
            answer.append(lst[1])
    
    return answer

 

---

정렬

K번째 수

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다.
예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면

1) array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다.
2) 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다.
3) 2에서 나온 배열의 3번째 숫자는 5입니다.

배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 
Array를 직접 슬라이싱하고 sorting하는 것이 최선의 알고리즘인 간단한 문제이다.

def solution(array, commands):
    return list(map(lambda a : sorted(array[a[0]-1:a[1]]) [a[2]-1], commands))

---

가장 큰 수

0 또는 양의 정수(0~1000)가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.
예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.
0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

 
상당히 애를 많이 먹었던 문제이다. 처음 생각한 알고리즘은 스스로 굉장히 만족했던 것이라서 빠르게 작성 후 채점 누르고 넘어가려고 했었으나, 시간 때문인지 오답 처리가 되었다. 먼저 가장 큰 자리 숫자를 비교해야 함은 당연하다. 가장 큰 자리 수가 같을 때가 문제인데, 예를 들어 3, 30, 34가 입력으로 들어오면 34330이 가장 큰 수이다. 이것을 비교하기 위해서, 나는 모든 수를 세 자리로 맞추는 방법을 생각했다. 방금의 예시에서 3이 34와 30 사이에 위치하는 이유는, 34의 일의 자리는 3보다 크고 30의 일의 자리는 3보다 작기 때문이다. 따라서, 한 자리 수라면 그 수를 세 번 반복하고(3->333), 두 자리 수라면 가장 큰 자리 수를 한번 더 적어서(30->303) 모든 수를 세 자리로 만들고 비교하고자 했다.

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers_3 = [number+number[0]*(3-len(number)) for number in numbers]    
    num_dict = dict(zip(numbers_3, numbers))
    answer = ''
    for key in sorted(num_dict, reverse = True):
        answer+=num_dict[key]
    return answer

 
그래서 위와 같이 작성했으나 보기 좋게 오류가 났다. 아래와 같이 비교 함수를 따로 작성하여 해보기도 했는데, 성공 케이스가 늘어나긴 했으나 전체적으로는 오답 처리가 되었다.

def compare(number):
    if len(number) == 1:
        return number*3
    elif len(number) == 2:
        return number + number[0]
    else:
        return number
    
def solution(numbers):
    sort_numbers = sorted(list(map(str, numbers)), key = compare, reverse = True)
    answer = ''.join(sort_numbers)
    return answer

 
이후 고민을 조금 더 해 보다가, 알고리즘적인 오류가 조금 있음을 발견했다. 예를 들어 12와 121을 비교하는 경우, 12121이 12112보다 크므로 12가 121보다 크다고 판단해야 한다. 그러나 내가 짠 코드에서는 12와 121을 같게 취급한다. 그래서 생각한 것이, 어차피 문자열이 세 자리 이상으로 길어져도, 세 자리만 유지하면 되지 않는가라는 점이다. 즉, 3, 30, 304를 비교할 때, 각각 다른 규칙을 적용해 시간을 낭비하지 말고, 일관되게 string을 세 번 반복하여 333, 303030, 304304304로 비교해도 똑같다는 것이다.12와 121의 경우에도 121212와 121121121을 비교하면 12가 더 크다. 이것으로 코드를 작성했다.

def solution(numbers):
    numbers = list(map(str, numbers))
    sort_numbers = sorted(numbers, key = lambda x:x*3, reverse = True)
    answer = ''.join(sort_numbers)
    return answer

 
어라!! 이렇게 했더니 나머지 다른 케이스는 다 통과했지만 한 케이스에서 오답이 떴다. 여기서는 정말 사소한 문제일 거라고 생각해서, 인내심을 잃고 구글링 해서 답을 찾았는데, 바로 인풋으로 0, 0, 0 이 들어오면 0이 아닌 000이 출력되어 오답처리가 된다는 것이다(...) 그래서 이 부분을 아래와 같이 수정해 주었다.

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key = lambda x:x*3, reverse = True)
    return str(int(''.join(numbers)))

 
이 문제에서 얻은 교훈은, 내 알고리즘이 모든 인풋 케이스에서 성립하려면 극단적인 인풋 케이스도 떠올리고 시뮬레이션해 보아야 한다는 점이다.

---

 

H-Index

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.
어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.
어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

 
처음에 논문의 인용수 리스트가 [3, 0, 6, 1, 5]와 같이 들어오면, 이를 sorting하고 싶다는 생각이 먼저 들어야 한다. 그러면 특정 인용수 오른쪽에 있는 논문들은 그 논문보다 인용수가 항상 같거나 크다. 따라서 해당 인용수 값과, 그 값 오른쪽에 있는 인덱스 수를 비교해주면 된다. 단!! 모든 값이 0일 때는 따로 처리해줘야 한다.

def solution(citations):
    citations.sort()
    l = len(citations)
    for i, item in enumerate(citations):
        if item>=l-i:
            return l-i
    return 0