문제 보기

[프로그래머스] 완주하지 못한 선수

참여자 participant 배열, 완주자 completion 배열이 주어질 때 완주하지 못한 선수를 출력하는 문제
문제에서는 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주했다는 조건을 걸었음
모든 선수의 이름은 알파벳 소문자로 표기됨

풀이 1 (python, c++)

participant와 completion을 알파벳 순으로 정렬한 다음에 앞에서부터 차례로 for문 돌면서 들어왔는지 비교함

마라톤 경기 참여한 선수의 수가 최대 100,000명임. 그리고 두 배열을 정렬하는데 각 각 O(N) 만큼의 시간 복잡도가 발생하고, 탐색도 마찬가지임.

꼭 다 정렬을 해야할까? 라는 생각...

python 코드

def solution(participant, completion):
    participant.sort()
    completion.sort()
    n = len(completion)
    for i in range(n):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[-1]

⚡ 아직도 헷갈리는 sort() 와 sorted()

• 리스트.sort() : 원본 리스트가 sort (default : 오름차순)
• 복사본 = sorted(원본리스트) : 원본 리스트의 복사본이 sort되고, 그걸 "복사본"이라는 이름을 가진 변수에 저장 (defualt : 오름차순)

c++ 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());
    int i = 0;
    for(; i < completion.size(); i++)
    {
        if (participant[i] != completion[i])
            return participant[i];
    }
    return participant[i];
}

⚡c++의 sort 함수
algorithm 헤더 파일에 있다.
sort(정렬할 배열의 시작, 정렬할 배열의 끝); (default : 오름차순)
vector의 마지막 원소에 접근할 때는 -1로 하면 안 되는 듯?

풀이 2 (python, c++)

해시 자료구조를 이용하면 좋지 않을까? 테이블 구조를 만들면 탐색 시간이 줄테니까! 라는 아이디어

python 풀이 & 코드

python에서는 해시를 구현하기 위해 dictionary를 제공하고 있음
1. 완주자 명단을 만든다.
2. 동명이인을 고려해서 이 사람이 몇 명 나왔는지를 체크
딕셔너리의 key는 완주자 이름, value는 해당 이름을 가진 사람이 몇 명이나 완주했는지 수
3. 참여자 한 명씩 살펴보면서
3-1. 완주자 명단에서 없으면 -> 완주 못한 사람
3-2. 완주자 명단에 있는데 동명이인이었음 (ex. eunseo라는 완주자가 4명인데, eunseo 라는 참여자가 5명임 : 그러면 eunseo 5명 중에 한 명은 완주 못한 것)

def solution(participant, completion):
    dic = {}
    
    for com in completion: #완주자 명단 
        if com not in dic:
            dic[com] = 1
        else:
            dic[com] += 1
        
    for part in participant:
        if part not in dic: #이 참여자가 완주자 명단에 없다면?
            return part #리턴
        dic[part] -= 1
        if dic[part] < 0:
            return part