프로그래머스 완주하지 못한 선수 c++,java (해시)

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

 

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

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

입출력 예 설명

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

풀이

해시 구조로 문제를 해결하는 기본적인 문제이다.

 

해시(hash)란 데이터를 다루는 기법 중에 하나로 검색과 저장이 메우 빠르게 진행된다.

해시는 기본적으로 데이터를 다루거나, 검색할 때 사용할 key와 실제 데이터 값인 value가
한 쌍으로 이루어져 있고, key값이 보통 배열의 인덱스 역할을 한다.

즉 key(string)에 따른 value(int)의 값을 다룰 때 용이하다!

 

c++에서 map은 인덱스를 문자열로 받을 수 있는 배열이라고 생각하면 된다.

 

시퀀스 컨테이너는 vector, list, deque와 같이 순서 있게 자료를 저장하고,

연관 컨테이너는 어떠한 key와 짝을 이루어 자료를 보관한다.

연관 컨테이너는 map, set, hash_map, hash_set이 있는데,

중복되는 key 값을 사용할 경우엔 앞에 'multi'를 붙여 사용한다.

ex) multi_map, multi_set, hash_multimap, hash_multiset

 

map, set은 숫자든 문자든 중복을 없애고, 삽입하는 순서에 상관없이 정렬(오름차순)돼서 저장된다.

앞에 hash가 붙은 자료구조는 정렬이 필요 없으며 빠른 검색을 할 때 사용한다.

(hash는 STL 표준은 아니지만 C++ 컴파일러에서 대부분 지원한다.)

 

해시에 대한 간단한 설명이였고, 내 풀이를 말하면,

참가자, 완주자 명단을 map의 key값으로 받아 카운트해주고,

카운트가 짝수가 아닌 경우, 즉 참가는 했지만 완주는 못한 경우를 출력해주면 된다.

문제의 조건에서 동명이인이 있을 수 있다고 했기 때문에,

count가 1인 경우를 출력하는 게 아니라 count가 짝수인 경우를 출력해야 한다.

 

java 코드에선 참가자는 카운트를 증가시키고, 완주자는 카운트를 감소시켜서
카운트가 0이 아닌 사람을 출력했다.

 

코드(c++)

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

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    map<string,int> ma;
    int i;
    for(i=0; i< completion.size();i++){
        ma[completion[i]]++;
        ma[participant[i]]++;
    }
    ma[participant[i]]++;

    for(auto o : ma){
        if(o.second%2!=0)
            answer=o.first;
    }
    return answer;
}

코드(java)

import java.util.HashMap;


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

        HashMap<String, Integer> map = new HashMap<>();

        for(String p : participant)
        {
            map.put(p, map.getOrDefault(p,0)+1);            
        }
        for(String c : completion)
        {
            map.put(c, map.get(c)-1);
        }


        for(String key : map.keySet())
        {
            if(map.get(key)!=0)
                answer = key;

        }




System.out.println(answer);
        return answer;
    }
}