본문 바로가기

별걸다하는 IT/알고리즘 문제풀이

[프로그래머스 알고리즘 문제 1단계] 완주하지 못한 선수 풀이 및 설명 (해시 알고리즘)

[Level 1] 완주하지 못한 선수 

 

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 단긴 배열 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"

기본 제공 틀:

[C++]

string solution(vector<string> participant, vector<string> completion){
    string answer ="";
    //기본 제공 틀
    //블라블라 코드 작성 
    return answer;
}

[Java]

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        return answer;
    }
}

풀이

완주한사람이 참가자보다 하나 작다는 것은 완주하지 못한 사람은 단 한명뿐이라는거네요!

 

아마 제일 먼저 생각나는 해답은 participant와 completoin의 값들을 반복문을 이용해서 일일이 비교하는 것일 텐데요.

제출해보면 알겠지만 시간초과 오류가 뜹니다! 시간복잡도를 생각해줘야 해요 ㅎㅎ

 

[C++]

맨 처음에 코드를 이렇게 해줬더니, 

string solution(vector<string> participant, vector<string> completion){
    string answer ="";
    for(vector<string>::iterator it_c= completion.begin(); it_c != completion.end(); ++it_c){
        for(vector<string>::iterator it_p = participant.begin(); it_p != participant.end(); ++it_p){
            if(*(it_c) == *(it_p)){
                participant.erase(it_p);
                break;
            }
        }
    }
    answer = participant.front();
    return answer;
}

 

시간 초과가 나왔습니다. ㅎㅎ 

빅오가 n^2이므로 어찌보면 당연한 결과인데 생각없이 풀었다는...

 

당연히!! 시간을 줄이려면 정렬을 해줘야겠죠! 

사실 이 문제는 정렬만 추가해주면 간단하게 끝나는 문제입니다. sort 함수를 사용할거니 algorithm 헤더 추가해주기~

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

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

 

반복문이 하나밖에 없으므로 최대 걸리는 시간은 빅오가 N이 되겠죠?! ㅎㅎ

여기서는 완주하지 못한 사람은 참가자 중에 한 명밖에 없다는 것이 힌트예요. ㅎㅎ 아마 이 부분때문에 level 1이 되지않았을 까 싶습니다. 

이름순대로 정렬을 해놓으면 매칭이 되다가 완주하지 못한 사람이 나오는 순간 매칭이 깨질거예요 ㅎㅎ 출력해줍시다. 

 

[C++]

사이트를 보면 이 문제는 해시 문제로 분류되어있어요. 해시맵을 사용해서 문제를 다른 방식으로 또 풀어볼게요.

그런데! C++ 스탠다드 라이브러리에는 hash table이 없었어요. hash_map을 생각하실지 모르겠는데 hash_map은 표준이 아닙니다. 그러다가 C++11부터 해시 테이블이 standard library에 추가되었습니다. 하지만 기존에 있던 hash map과 충돌을 방지하기 위해서 unorderd_map으로 이름을 지었답니다. 즉, unordered_map은 hash_map과 유사한 성능을 내는 표준 자료구조입니다. 그러므로 unordered_map을 사용해서 풀어볼게요 

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

string solution(vector<string> participant, vector<string> completion){
    unordered_map<string, int> prtcpt_map;
    for( string name: participant){
        prtcpt_map[name]++;
    }
    for( string name: completion){
        prtcpt_map[name]--;
    }
    for(auto pair: prtcpt_map){
        if (pair.second>0){    
            return pair.first;
        }
    }
}

[Java]

다음은 자바로 넘어가봅시다. 사실 언어는 거기서 거기라 알고리즘만 이해하고 있음 쉽게 적용가능하지만 하나의 언어만 사용하는 사람도 있으니까 ㅎㅎ

C 파트 첫번째에서 했던 것처럼 정렬을 이용해 시간복잡도를 줄여 결과를 도출해봅시다. 

import java.util.Arrays;
class Solution{
    public String solution(String[] participant, String[] completion){
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        int index=0;
        for(String c: completion){
            if(!c.equals(participant[index]))
                return participant[index];
            index++;
        }
        return participant[participant.length-1];
    }
}

자꾸 컴파일 오류가 나서 오류날게 없는데 뭐가 오류지했는데 가장 기본적인 import를 안해줬다는...

맨날 자동 import를 하다가 수동으로 일일이 쓰려니까 이런점이 불편하네요. 괜히 ide가 편한게 아니야 ㅠㅠ

프로그래머스와 같은 여타 사이트들에 이런 기능이 하루빨리 추가되었으면 하는~~~

 

[Java]

자바 컬렉션 프레임워크에는 HashMap이 있습니다. 해시 문제이니 해시맵을 사용해서 풀어볼게요

마찬가지로 java.util.HashMap을 임포트해줍시다.

동명이인이 있을 수 있다는 조건이 있으므로 값은 Boolean이 아니라 Integer로 해줘야 해요 ㅎㅎ

동명이인 참가자가 두 명일 때 

동명이인 참가자가 세 명일 때

등등 늘어날 수 있기 때문이죠 ㅎㅎ

import java.util.Arrays;
class Solution{
    public String solution(String[] participant, String[] completion){
        String answer ="";
        HashMap<String, Integer> prtcpt_map = new HashMap<>();
        for(String name: participant){
            prtcpt_map.put(name, prtcpt_map.getOrDefault(name, 0)+1);
        }    
        for(String name: completion){    
            prtcpt_map.put(name, prtcpt_map.get(name)-1);
        }
        for(String name: prtcpt_map.keySet()){
            if(prtcpt_map(name) !=0){
                answer = name;
                break;
            }
        }
        return answer;
    }
}

C와 다른 점은, C는 []가 오버로딩 되어있어서 prtcpt_map[name]++;

이렇게 접근 가능하지만 자바는 []를 사용할 수 없어요 

따라서 동명이인이 들어올때마다 value값을 늘려주는 부문에 값이 없으면 0으로 초기화해주고 값이 있으면 해당 값을 가지고 오는 getOrDefault를 써준다는 정도?ㅎㅎ

로직은 똑같습니다.

 

더 좋은 풀이가 있다면 알려주세요 :) 오타나 지적 환영합니다.