링크

제한 사항

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

문제 접근

  • (1) 번 조건 → $O(n)$ 또는 $O(nlogn)$ 알고리즘일 가능성이 높다.
  • (2) 번 조건 → 완주하지 못한 참가자는 단 한명이다.
  • (3), (4)번 조건 → 선형 배열로 해결하기 어렵다. → 해시 알고리즘

알고리즘 분석

  • 해시 알고리즘($O(1)$)을 이용한 카운팅 → 복잡도 $O(n)$ (n은 참가자 수)

문제 설계

  1. 참가자 명단을 loop하여 이름(name)의 수를 세어 해시 테이블에 저장한다.
  2. 완주자 명단을 loop하여 이름(name)을 키로하여 해시 테이블에서 1씩 빼준다.
  3. 해시 테이블의 값이 0이 아닌 이름(name)을 리턴한다.

문제 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(participant, completion):
    count_name = {}

    # count(name in P)
    for name in participant:
        if not name in count_name:
            count_name[name] = 1
        else:
            count_name[name] += 1

    # count(name in P) - count(name in C)
    for name in completion:
        count_name[name] -= 1

    # find answer
    for name, count in count_name.items():
        if count > 0:
            return name
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
정확성  테스트
테스트 1 〉 통과 (0.01ms, 10.2MB)
테스트 2 〉 통과 (0.01ms, 10.2MB)
테스트 3 〉 통과 (0.15ms, 10.3MB)
테스트 4 〉 통과 (0.26ms, 10.4MB)
테스트 5 〉 통과 (0.25ms, 10.4MB)
효율성  테스트
테스트 1 〉 통과 (19.82ms, 21.9MB)
테스트 2 〉 통과 (32.16ms, 25.2MB)
테스트 3 〉 통과 (35.41ms, 27.5MB)
테스트 4 〉 통과 (45.18ms, 34MB)
테스트 5 〉 통과 (41.51ms, 34MB)
채점 결과
정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0

강사님의 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
def solution(participant, completion):
  d = {}

  for x in participant:
    d[x] = d.get(x, 0) + 1

  for x in completion:
    d[x] -= 1

  dnf = [k for k, v in d.items() if v > 0]

  answer = dnf[0]
  return answer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
정확성  테스트
테스트 1 〉 통과 (0.01ms, 10.3MB)
테스트 2 〉 통과 (0.01ms, 10.2MB)
테스트 3 〉 통과 (0.20ms, 10.2MB)
테스트 4 〉 통과 (0.66ms, 10.4MB)
테스트 5 〉 통과 (0.32ms, 10.4MB)
효율성  테스트
테스트 1 〉 통과 (24.72ms, 21.9MB)
테스트 2 〉 통과 (32.99ms, 25.2MB)
테스트 3 〉 통과 (46.51ms, 27.6MB)
테스트 4 〉 통과 (47.82ms, 34MB)
테스트 5 〉 통과 (53.67ms, 33.9MB)
채점 결과
정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0

코드 최적화

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(participant, completion):
    d = {}

    # count(name in P)
    for x in participant:
        d[x] = d.get(x, 0) + 1

    # count(name in P) - count(name in C)
    for x in completion:
        d[x] -= 1

    # find answer
    for k, v in d.items():
        if v > 0:
            return k
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
정확성  테스트
테스트 1 〉 통과 (0.01ms, 10.2MB)
테스트 2 〉 통과 (0.01ms, 10.2MB)
테스트 3 〉 통과 (0.14ms, 10.3MB)
테스트 4 〉 통과 (0.48ms, 10.5MB)
테스트 5 〉 통과 (0.28ms, 10.4MB)
효율성  테스트
테스트 1 〉 통과 (21.24ms, 21.8MB)
테스트 2 〉 통과 (31.74ms, 25.2MB)
테스트 3 〉 통과 (40.50ms, 27.6MB)
테스트 4 〉 통과 (51.58ms, 34.1MB)
테스트 5 〉 통과 (44.60ms, 34MB)
채점 결과
정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0

다른 풀이(정렬)

1
2
3
4
5
6
7
8
9
def solution(participant, completion):
  participant.sort()
  completion.sort()

  for i in range(len(completion)):
    if participant[i] != completion[i]:
      return participant[i]

  return participant[len(participant)-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
정확성  테스트
테스트 1 〉 통과 (0.03ms, 10.2MB)
테스트 2 〉 통과 (0.01ms, 10.2MB)
테스트 3 〉 통과 (0.29ms, 10.3MB)
테스트 4 〉 통과 (0.54ms, 10.3MB)
테스트 5 〉 통과 (0.41ms, 10.4MB)
효율성  테스트
테스트 1 〉 통과 (42.23ms, 17.9MB)
테스트 2 〉 통과 (56.55ms, 22.1MB)
테스트 3 〉 통과 (77.17ms, 24.8MB)
테스트 4 〉 통과 (83.35ms, 26.4MB)
테스트 5 〉 통과 (72.46ms, 26.3MB)
채점 결과
정확성: 50.0
효율성: 50.0
합계: 100.0 / 100.0

(2)번 조건에 의해 가능한 풀이

사전식으로 정렬하고 앞에서부터 순회하면 일치하지 않는 부분이 반드시 발생한다.

sort() 알고리즘 때문에 $O(nlogn)$ 만큼 복잡도를 가진다. (따라서, 최적의 풀이가 아님)

평가

dictionary.get(key[, value]) 메서드를 알게되었다.

코드가 훨씬 간결해진다.

사용했을때랑 하지 않았을때랑 속도 차이가 무의미하다.

따라서, get()를 사용하는게 현명하다.

리스트 컴프리헨션을 사용하지 않는건 확실하게 속도면에서 이점이 있다.

(단, 미완주자가 한명이라는 조건에서만 차이가 유의미하다.)