[Java] 완주하지 못한 선수

- 프로그래머스 / 해시 / 완주하지 못한 선수 -

 

 

 

# 문제설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다.

단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 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 (이중 for 문을 이용한 풀이) --> 정확성 통과, 효율성 실패

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

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

        for (int i = 0; i < participant.length; i++) {
            map.put(i, participant[i]);
        }

        for (String p : completion) {
            for (int i = 0; i < participant.length; i++) {
                if (p.equals(map.get(i))) {
                    map.remove(i);
                    break;
                }
            }
        }

        for (int i = 0; i < participant.length; i++) {
            if (map.containsKey(i)) {
                answer = map.get(i);
            }
        }
        System.out.println(answer);
        return answer;
    }
}

풀이 방법

    1. Map 을 이용해 참가자들마다 고유의 Key 값 설정

    2. 완주자 명단에 있는 참가자는 Map 에서 삭제

    3. 완주하지 못한 참가자는 무조건 1명이 있기에 삭제되지 않은 참가자가 answer

 

 

회고

• 위 풀이 방법은 굳이 Map 을 쓸 필요가 없어보임.
• 이중 for 문을 활용했기에 시간복잡도 증가 -> 효율성 테스트에서 실패 된 것으로 보임.

 

 

 

# 풀이과정 2 (Arrays 정렬 이용, Hash 이용 X) --> 정확성 통과, 효율성 통과

class Solution2 {
    public String solution(String[] participant, String[] completion) {

        Arrays.sort(participant);
        Arrays.sort(completion);

        int idx = 0;
        while (true) {
            if (idx == participant.length - 1) {
                return participant[idx];
            }
            if (!participant[idx].equals(completion[idx])) {
                return participant[idx];
            }
            idx++;
        }
    }
}

풀이 방법

    1. Arrays 의 정렬을 활용하여 참가자 배열, 완주자 배열 정렬

    2. 인덱스가 참가자 배열의 마지막 원소를 지정하게 될 경우, 마지막 원소 출력

    3. 정렬된 순서가 다른 경우 해당 원소 출력

 

 

회고

• Hash 를 이용하지 않았기에 해당 문제를 푸는 관점이 벗어남.
• 참가자와 완주자의 배열 길이가 길어지게 되면 정렬하는데 시간이 대폭증가 될 것으로 예상됨.

 

 

 

# 풀이과정 3 (HashMap 이용, 구글링한 코드) --> 정확성 통과, 효율성 통과

class Solution3 {
    public String solution(String[] participant, String[] completion) {

        String answer = "";

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

        // participant 를 map 에 담을 건데 완주 처리하기 전
        // --> key : playerName, value : 경기중인 참가자 수  -->  (ex. 완주한 사람 = 0, 완주 전 = 1, 동명이인 = 2)
        for (String p : participant) {
            if (!map.containsKey(p)) {
                map.put(p, 1);
            }
            // 중복 처리
            else {
                map.put(p, map.get(p) + 1);
            }
        }

		// 완주 시 value 값 = 0
        for (String p : completion) {
            map.put(p, map.get(p) - 1);
        }

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                answer = entry.getKey();
                break;
            }
        }
        
        return answer;
    }
}

풀이 방법

    1. Map 생성 (Key : 참가자 이름, Value : 경기 진행중인 Key에 해당하는 참가자의 수)

    2. 완주자 배열을 통해 완주자에 해당하는 Value 값에 -1

    3. Map 에서 Value 값이 0이 아닌 (완주를 하지 못한) 선수가 answer

 

 

회고

• 동명이인의 가능성으로 Key 값을 참가자 이름으로 하는 것을 배제했는데 중복 Key 발생 시 Value 값을 변경해주면 되는 좋은 방법을 알음.
• 세상에 똑똑한 사람은 많다.

 

 

 

# 풀이과정 4 (HashCode 이용, 친구가 푼 코드) --> 정확성 통과, 효율성 통과

class Solution4 {
    public String solution(String[] participant, String[] completion) {

        String answer = "";

        int hashValue1 = 0;
        int hashValue2 = 0;

        for (int i = 0; i < participant.length; i++) {
            hashValue1 += participant[i].hashCode();
        }

        for (int i = 0; i < completion.length; i++) {
            hashValue2 += completion[i].hashCode();
        }

        for (int i = 0; i < participant.length; i++) {
            if (hashValue1 == participant[i].hashCode() + hashValue2) {
                answer = participant[i];
                System.out.println(answer);
                return answer;
            }
        }
        System.out.println(answer);
        return answer;
    }
}

풀이 방법

    1. 참가자, 완주자 배열의 hashcode 총합을 구함

    2. 각 배열의 hashcode 의 차를 이용하여 완주하지 못한 선수를 출력

  

 

회고

• 같은 문자열이면 같은 hashcode 를 갖는 성질을 이용
• 내 친구는 천재다. 어떻게 이런 생각을...

 

코드 실행 결과

 

 

 

 

- Just Do It -