Algorithm프로그래머스

[프로그래머스] 코딩테스트 풀이 - 완주하지 못한 선수

ALGORITHM, CODING TEST, HASH, HASH TABLE, PYTHON

Reference : 프로그래머스 코딩 테스트 연습

문제 설명

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

마라톤에 참여한 선수들의 이름이 담긴 배열 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

조건 분석

  • 나와야 하는 결과

    1
    완주하지 못한 선수의 [이름]

  • 문제를 풀기위해 주어진 데이터

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # 문제 해결에 필요한 데이터

    1. 이름
      - 참여한 선수들의 이름 리스트 (completion arr)
      - 완주한 선수들의 이름 리스트 (participant arr)
    2. 완주하지 못한 인원 수 (1명)

    # 제한조건

    1. 전체 배열 갯수 (1~10만)
    2. 이름 길이 (max 20 byte)
    3. 참가자의 동명이인 여부 (Yes)

  • 간단 알고리즘

    1
    1. 완주한 선수들의 리스트 중에서 참여한 선수들을 제거하고 남은 선수를 반환한다.

풀이

사용언어 : Python 3

알고리즘은 간결하지만 2가지의 풀이방법이 있다.

  • 문자열을 직접 비교하는 방법
  • 해시 테이블을 이용한 방법

문자열을 직접 비교하면 for문을 2개 활용해서 O(n^2)의 시간복잡도로 구할 수 있다.
다만 문제자체에서 O(n)의 시간복잡도가 나오지 않으면 문제풀이로 인정해주지 않기 때문에 해쉬를 이용한다.

해쉬(Hash)에 대한 자세한 설명은 타 포스팅 참조

세부 알고리즘은

  1. 참여한 선수들의 이름을 특정 해쉬 함수를 통해 해쉬값으로 만든다.
  2. “색인을 통한 검색”을 위해 위의해쉬값을 색인(index)으로 하는 해쉬 테이블을 만든다.
  3. 완주한 선수들의 이름을 해쉬값으로 만들어서 참여한 선수들의해쉬 테이블에서 제거한다.
  4. 마지막에 남은 해쉬 테이블의 리스트를 반환한다.

파이썬에서는 딕셔너리라는 key-value 매핑구조를 지원한다.
이때 key를 해쉬함수를 통해 나온값을 색인으로 쓰는 해쉬 테이블을 만들어주므로 편하게 사용하면 되겠다.
직접 해쉬테이블을 만들고싶으면 hash()를 사용해 만들어주면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(participant, completion):
    dic = {} # 딕셔너리 선언
     
    for parName in participant:
        dic[parName] = 0 
        # key는 참여자 이름, value는 0으로 통일하는 dic 해쉬 테이블을 만든다.
             
    for comName in completion:
        if comName in dic:
            del dic[comName] 
        # 해쉬 테이블에서 완주자의 이름을 가진 key를 전부 제거
 
    return list(dic.keys())[0] # 마지막 남은 key 반환

participant = ["leo", "kiki", "eden"]
completion = ["eden", "kiki"]

print(solution(participant,completion))
1
2
실행결과
leo

가장 기본적인 문제는 해결되었으니 제한조건을 살펴볼 차례이다.
전체 배열갯수나 이름길이는 문제가 없지만 동명이인일때가 문제다.
테스트값을
participant = ["leo","leo", "kiki", "eden"]
completion = ["leo","eden", "kiki"]

이렇게 변경하면 딕셔너리 구조상 leo라는 키값이 2개가 아닌 1개로 저장된다.
이때 leo라는 키를 제거하면 결국 미완주자가 0명이 된다.

같은 key를 저장할때는 value값에 값을 누적시키는 방법으로 해결이 가능하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def solution(participant, completion):
    dic = {} 
    
    for parName in participant:
        if parName in dic: # 딕셔너리 내부에 동명이인이 있으면
            dic[parName] = dic.get(parName) + 1 # value에 1을 추가
        else:
            dic[parName] = 1 # 동명이인이 없으면 1로 통일
    
    for comName in completion:
        if comName in dic:
            dic[comName] = dic.get(comName) -1 # 완주한 사람은 value값에 -1
        if dic[comName] == 0:
            del dic[comName] # 0인 완주자는 테이블에서 제외
    
    return list(dic.keys())[0] # value값이 1인 참여자만 남아서 반환


participant = ["leo","leo", "kiki", "eden"]
completion = ["leo","eden", "kiki"]

print(solution(participant,completion))
1
2
실행결과
leo

이외에 참여자와 완주자의 리스트를 알파벳순으로 정렬해 비교하는 도중 같지않으면 반환하는 방법과 Counter 클래스를 사용하는 방법도 있다.

공유하기