[PCCP] Lv1: 완주하지 못한 선수(42576) 해설

문제

- 문제 링크: 완주하지 못한 선수

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

- N: participant의 길이

- K: completion의 길이

- 참가자의 이름을 해시 테이블에 추가하는 시간 복잡도: O(N)

- 완주한 선수들의 이름을 해시 테이블에서 제외하는 연산의 시간 복잡도: O(K)

- completion의 최대 길이는 N - 1이므로 K 대신 N - 1로 대체한다면 시간 복잡도는 O(2*(N - 1))

- 최종 시간 복잡도: O(N)

#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    unordered_map<string, int> ph; // participant를 나타낼 해시 테이블
    
    // 각 참가자를 해시테이블에 추가(키는 이름, 값은 해당 이름의 명수)
    for (int i = 0; i < participant.size(); ++i)
        ph[participant[i]]++;
        
    // 참가자 정보가 저장된 해시 테이블에서 완주한 선수들 제외
    for (int i = 0; i < completion.size(); ++i) {
        ph[completion[i]]--;
        // 해시 테이블에 특정 이름이 0명이면 삭제
        if (ph[completion[i]] == 0) 
            ph.erase(ph.find(completion[i]));
    }
    
    // 마지막 남은 한 선수의 이름 반환
    return ph.begin()->first;
}

solution 2)

- N: participant의 길이

- K: completion의 길이

- participant와 completion을 정렬: O(NlogN + KlogK)

- 이후 반복문의 시간 복잡도는 최대 K번 실행하므로 O(K)

- 최종 시간 복잡도: O(NlogN)

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

using namespace std;

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

solution 3)

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

using namespace std;

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

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: participant의 길이

- K: completion의 길이

- 완주한 선수들의 이름을 해시맵에 추가하는 연산: O(K)

- 참가자의 이름을 해시맵에서 제외하는 연산: O(N)

- 추가로 completion의 최대 길이는 N - 1이므로 K 대신 N- 1로 대체하면 시간 복잡도는 O(2*(N-1))

- 최종 시간 복잡도: O(N)

import java.util.HashMap;

public class Solution {

    public String solution(String[] participant, String[] completion) {
        // 해시맵 생성
        HashMap<String, Integer> hashMap = new HashMap<>();
        // 완주한 선수들의 이름을 해시맵에 저장
        for (String string : completion) {
            hashMap.put(string, hashMap.getOrDefault(string, 0) + 1);
        }

        // 참가한 선수들의 이름을 키로 하는 값을 1씩 감소
        for (String string : participant) {
            // 완주하지 못한 선수를 찾으면 반환
            if (hashMap.getOrDefault(string, 0) == 0) {
                return string;
            }
            hashMap.put(string, hashMap.get(string) - 1);
        }

        return null;
    }

}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: participant의 길이

- K: completion의 길이

- 참가자의 이름을 해시 테이블에 추가하는 연산: O(N)

- 완주한 선수들의 이름을 해시테이블에서 제외하는 연산: O(K)

- 추가로 completion의 최대 길이는 N - 1이므로 K 대신 N - 1로 대체시 O(2*(N - 1))

- 최종 시간 복잡도: O(N)

def solution(participant, completion):
    # 해시 테이블 생성
    dic = {}
    
    # 참가자들의 이름을 해시 테이블에 추가
    for p in participant:
        if p in dic:
            dic[p] += 1
        else:
            dic[p] = 1
            
    # 완주한 선수들의 이름을 키로 하는 값을 1씩 감소
    for c in completion:
        dic[c] -= 1
    
    # 해시테이블에 남아있는 선수가 완주하지 못한 선수
    for key in dic.keys():
        if dic[key] > 0:
            return key

solution 2)

def solution(participant, completion):
    answer = ''
    members = {}
    for mem in participant:
        if members.get(mem) is not None:
            members[mem] += 1
        else:
            members[mem] = 1
    for mem in completion:
        if members.get(mem) != 0:
            members[mem] -= 1
    for k, v in members.items():
        if v != 0:
            answer = k
    return answer

solution 3)

import

 

(JavaScript)

solution 1)

- N: participant의 길이

- K: completion의 길이

- 참가자의 이름을 해시 테이블에 추가하는 연산: O(N)

- 완주한 선수들의 이름을 해시 테이블에서 제외하는 연산의 시간 복잡도: O(K)

- 추가로 completion의 최대 길이는 N - 1이므로 K 대신 N-1로 대체할 경우: O(2*(N-1))

- 최종 시간 복잡도: O(N)

function solution(participant, completion) {
    // 해시 테이블 생성
    const obj = {};
    
    // 참가자들의 이름을 해시 테이블에 추가
    for (const p of participant) {
        if (obj[p]) {
            obj[p] += 1;
        } else {
            obj[p] = 1;
        }
    }
    
    // 완주한 선수들의 이름을 키로 하는 값을 1씩 감소
    for (const c of completion) {
        obj[c] -= 1;
    }
    
    // 해시 테이블에 남아 있는 선수가 완주하지 못한 선수
    for (const key in obj) {
        if (obj[key] > 0) {
            return key;
        }
    }
}

solution 2)

import

solution 3)

import