Notion에서 작성된 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Beginner] 완주하지 못한 선수

[완주하지 못한 선수]

• 2기 2일차에 풀었던 문제이다. 해시에 대한 개념이 없던 당시의 정렬을 이용한 풀이와, 해시를 이용한 풀이를 공유하고자 한다.

Solution 1. Sort $O(n \lg n)$

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]

• participant와 completion을 각각 정렬하고 나서, 같은 인덱스에 존재하는 participant와 completion의 값이 다르다면 그 위치에 있는 참가자는 완주하지 못한 선수이다. 문제의 설명을 통해 단 한 명의 선수만 완주하지 못했다는 것을 알 수 있으므로, 바로 return한다.
  • 다섯 명의 선수 $A,B,C,D,E$가 순서대로(추월을 하지 않고) 그룹을 이루어 달리는 모습을 상상해 보자. 이 중 $A, B, D, E$가 완주했다고 하면, (코드 상) 선두부터 한 명씩 비교해 봤을 때 세 번째 위치에서 $C \neq D$로 $C$가 완주하지 못했음을 알 수 있다.
• 이 때, completion의 길이는 participant의 길이보다 1 작으므로, completion의 끝까지 비교했음에도 완주하지 못한 선수를 찾지 못했다는 것은 participant의 맨 마지막 원소가 완주하지 못한 선수이므로, 이를 return한다.
  • 위 예시에서, $A, B, C,D$가 완주했다고 하자. 이 때 완주하지 못한 선수는 $E$임을 알 수 있다.

Solution 2. Hash $O(n)$

def solution(participant, completion):
    p_dict = {}
    
    for p in participant:
        if p in p_dict:
            p_dict[p] += 1
        else:
            p_dict[p] = 1
    
    for c in completion:
        p_dict[c] -= 1
    
    return [k for k, v in p_dict.items() if v][0]

• 참가자 중에는 동명이인이 있을 수 있으므로 set을 이용하여 차집합을 return하는식으로 풀 수 없다. 동명이인 중 한 명은 완주하고, 한 명은 완주하지 못한 상황을 반영할 수 없기 때문이다.
• 이를 처리하기 위해, (참가자명):(해당 이름으로 참가한 사람 수)를 의미하는 dictionary p_dict를 만들었다.
  $p_{dict} = \begin{cases} p_{dict}[p] \text{ += } 1 & \text{if }p \in p_{dict} \\ p_{dict}[p] \text{ = } 1 & \text{if }p \notin p_{dict} \end{cases}$
• 그리고, 각각의 완주자에 대해 $p_{dict}$의 value를 빼준다.
  • 단 한 명의 선수를 제외하고 모든 선수가 마라톤을 완주하였는데 참여자 명단에는 없고, 완주자 명단에는 있는 경우는 없으므로 if c in p_dict: 로 체크해주지 않아도 된다. 이 작업을 마친 뒤 $p_{dict}$의 value가 1으로 남아 있는 선수가 완주하지 못한 선수이므로, 이를 return한다.

---

[Middler] 전화번호 목록 ★

[전화번호 목록]

• 시간복잡도를 쥐어짤만한 포인트가 정말 많은 문제였다.

Solution 1. 완전탐색 $O(n^2)$

def solution(phone_book):
    for p in phone_book:
        for h in phone_book:
            if p.startswith(h) and p != h:
                return False
    return True

• 가장 떠올리기 쉬운 방법은 역시 완전탐색이다. 각 전화번호에 대해 그 전화번호가 아닌 다른 모든 전화번호에 대해 하나하나 그 전화번호로 시작하는지 확인해 보면 된다.
• in 은 substring을 확인한다는 점에 주의하여, prefix를 확인할 수 있는 startswith()를 사용하자.
  • startswith()를 비슷하게 구현해 보면 다음과 같다.

    def is_prefix(a, b):
        return a[:len(b)] == b

Solution 2. Sort $O(n \lg n)$

def solution(phone_book):
    pb = sorted(phone_book)
    
    for i in range(len(pb)-1):
        if pb[i+1].startswith(pb[i]):
            return False
    return True

• 정렬을 활용한 방법이다. phone_book을 정렬하고 나면, 사전순으로 정렬되기 때문에 연속한 두 원소에 대해서만 확인해 주면 된다.

  • 사전순으로 뒤에 위치하는 문자열은 앞에 위치하는 문자열의 접두어가 될 수 없다는 점을 생각하며, 앞에 위치하는 문자열로 시작할 경우 return해주면 된다.

• 다른 사람의 코드를 보며 배운 부분이 있다. $O(n)$으로 순회하며 연속된 두 원소에 대해 비교할 때, zip을 이용하는 부분이었다.

  for p1, p2 in zip(pb, pb[1:]):

  • pb[1:] 로 슬라이싱하는 과정에서 $O(n)$에 가까운 시간이 추가로 소요되어 인덱스로 직접 접근하는 방법에 비해 훨씬 비효율적일 줄 알았다.
  • 하지만, zip이 C로 구현되어 매우 최적화되어있고, python interpreter가 zip을 사용한 루프를 더 잘 최적화할 수 있다고 한다. 실제로 실행 결과도, 인덱스를 이용했던 방식에서 80~90ms가 소요된 TC에서, zip을 이용한 방식은 70~80ms가 소요되었다.

Solution 3. Hash $O(n)$

def solution(phone_book):
    pb_set = set(phone_book)
    
    for pnum in phone_book:
        prefix = ''
        for p in pnum:
            prefix += p
            if prefix in pb_set and prefix != pnum:
                return False
    
    return True

• 집합을 활용한 방법이다. 먼저 phone_book 집합 pb_set을 만든 다음, 각 전화번호에 대해, 그 전화번호의 앞에서부터 한 글자씩 늘려가며 이 prefix가 전화번호부에 등록된 prefix인지 $O(1)$에 확인할 수 있다.
  • 한 글자씩 늘려가는 방식에 대해 고민해볼 필요가 있다.
    • 단순히 for i in range(1, len(pnum)): pnum[:i] 과 같이 매 반복마다 슬라이싱할 경우, 번호의 길이가 20일 때 $O(1)+ ... +O(19) = O(190)$의 시간이 소요된다.
    • 이를 Prefix Sum과 비슷한 방식으로, 각 자리를 반복마다 이어붙여주어 각 번호에 대해 최대 $O(20)$으로 확인할 수 있다.
• 이 방법은 집합으로 만드는 데 $O(n)$, 각 전화번호에 대해 prefix 생성 및 확인에 $O(n) \cdot O(20) = O(20n)$으로, 총 $O(21n)$의 시간이 소요된다.
  • 계수가 매우 높은 탓에 정렬을 이용한 방법($O(n \lg n)+O(n)$)에 비해 같은 TC에 대해 더 많은 시간이 소요되었다.

---

[Challenger] 베스트앨범

[베스트앨범]

• 글 작성에만 너무 시간이 오래 걸리는 것 같아서,,, 적당히 작성하겠다!

1. 재생 횟수를 기준으로 고유번호, 장르, 재생횟수를 묶어 내림차순으로 정렬한다(나중에 장르 내에서 많이 재생된 노래를 먼저 수록하기 위함이다).
2. 많이 재생된 노래의 장르를 알아내기 위해, dictionary를 이용하여 각 장르별 재생횟수를 센 다음 내림차순으로 정렬한다.
3. 가장 많이 재생된 장르부터 최대 두 곡씩 앨범에 고유 번호를 넣는다.
   • $m$을 장르의 종류라고 하자(제한사항에 따르면 100개 미만). $n$을 genres와 plays의 길이라 하자.
   • 이 방법은 $O(nm) \approx O(1,000,000)$으로 AC일 것이라 생각해서 일단 저렇게 나이브하게 짜놓긴 했는데, $O(n)$으로 순회하며 dictionary에 장르별로 최대 두 개씩 담아놓고, $O(m)$으로 합치는 $O(n+m)$ 방법이 생각났다. 일단 자고 일어나서 짜봐야 겠다!

Solution) $O(n \lg n)$

def solution(genres, plays):
    gp_dict = {}
    
    gp = sorted(enumerate(zip(genres, plays)), key=lambda x: -x[1][1])

    for i, song in gp:
        if song[0] in gp_dict:
            gp_dict[song[0]] += song[1]
        else:
            gp_dict[song[0]] = song[1]

    gp_total = sorted(gp_dict.keys(), key=lambda x: -gp_dict[x])

    answer = []
    for g in gp_total:
        idx = []
        for i, song in gp:
            if song[0] == g: idx.append(i)
            if len(idx) == 2: break
        answer.extend(idx)
        
    return answer

---