1. 완주하지 못한 선수

문제 설명

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

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

제한사항

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

입출력 예

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

for문으로 풀기

def solution(participant, completion):
    for i in completion:
        if i not in participant:
            return i
        participant.remove(i)
    return participant[0]

이렇게 풀면 모든 배열을 조회하면서 하나씩 빼면서 계산할 수 있지만

$O(n^2)$ 이다 (completion 조회 * remove함수)

해시로 풀기

def solution(participant, completion):
    dict = {}
    for i in participant:
        if dict.get(i) == None:
            dict[i] = 1
        else:
            dict[i] += 1
    
    for j in completion:
        dict[j] -= 1
        if dict[j] == 0:
            del dict[j]

    ans = list(dict.keys())

    return ans[0]

dictionary는 왠만한 시간복잡도가 다 $O(1)$이기 때문에 쉽게 풀 수 있다.

participant를 순회하며 key값을 선수 이름으로, value를 등장횟수로 하며 dictionary를 만들고

completion을 돌면서 각 등장횟수를 차감하면 동명이인이 있든 없든 등장횟수가 1인 선수 한 명만 남게 된다.

전화번호 목록

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

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

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

제한 사항

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

입출력 예제

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

문제 접근

문자열의 전화번호가 있는 배열이 주어지기 때문에 문자열 정렬을 하면 자연스레 인접한 요소끼리 접두사 관계가 생기게 된다.

ex) “12”, “123”, “13”, “134”

배열로 풀기

def solution(phone_book):
    book_array = sorted(phone_book)
    for num in range(len(book_array)-1):
        if book_array[num] == book_array[num+1][:len(book_array[num])]:
            return False
    return True

간단하게 문자열을 정렬하고 인접한 요소끼리 비교하면 된다.

해시로 풀기

def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer

이 코드는 해당 코드의 모범 답안 중 하나이다.

해시맵의 key로 모든 전화번호 값을 넣고, 한 문자열마다 한 자리씩 임시문자열에 추가함으로서 임시문자열이 해시맵에 포함되어 있는지 탐색( $O(n)$ )한다.

기억할 점

문자열 정렬은 사전순이다… 숫자도 동일하게…

베스트앨범

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

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

입출력 예

genres	plays	return
["classic", "pop", "classic", "classic", "pop"]	[500, 600, 150, 800, 2500]	[4, 1, 3, 0]

해시로 풀기

def solution(genres, plays):
    # 각 장르별 play 리스트와 총 play 수를 구한다
    play_hash = {}
    total_hash = {}
    for num, (genre, play) in enumerate(zip(genres, plays)):
        if genre not in play_hash:
            play_hash[genre] = []
        if genre not in total_hash:
            total_hash[genre] = 0
        (play_hash[genre]).append([play, num])
        total_hash[genre] += play

    # 장르 1, 2위를 알아낸다
    total_array = list(total_hash.items())
    total_array = sorted(total_array, key=lambda x: -x[1])

    picked_genre = []
    for pick in total_array:
        picked_genre.append(pick[0])

    # 그 장르 1, 2위의 play 리스트를 꺼낸다
    picked_array = []
    for genre in picked_genre:
        picked_array.append(sorted(list(play_hash[genre]), key=lambda x: (-x[0], x[1])))

    # 각 장르의 1, 2위 노래를 꺼낸다
    answer = []
    for pick in picked_array:
        if len(pick) >= 2:
            answer.append(pick[0][1])
            answer.append(pick[1][1])
        else:
            answer.append(pick[0][1])
    
    return answer

주석으로 대부분 설명했지만 이 문제는 최댓값이 아닌 1, 2위를 가져와서 띄우는 문제다.

단, 장르나 플레이리스트의 종류나 길이가 반드시 2 이상일 보장은 없기 때문에 길이가 1일 때도 처리를 해야한다.

람다를 이용해서 정렬하고 변수를 잘 활용해야 하는 것이 특징이다.