[PG] 완주하지 못한 선수 JAVA

programmers.co.kr/learn/courses/30/lessons/42576

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

 

참가자 배열 String[] participant, 완주자 배열 String[] completion이 주어진다.

참가자들 중 완주하지 못한 선수가 1명 존재할 때 이 선수의 이름을 반환하는 문제.

해시 태그로 분류되었지만 정렬만으로도 풀 수 있다.

 

풀이 1. 

import java.util.*;

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

        for(int i = 0; i < completion.length; i++) {
            if(!participant[i].equals(completion[i])) {
                answer = participant[i];
                break;
            }
            
            // completion의 마지막까지 전부 같다면 남은 한 명이 정답
            if(i == completion.length - 1) {
                answer = participant[i + 1];
            }
        }
        return answer;
    }
}

Arrays.sort()를 사용해 두 배열을 모두 정렬한 후 원소들을 차례로 비교한다.

다른 원소가 등장하는 순간 그 놈이 정답. 반복 종료.

마지막 원소까지 모두 같다면 participant에 남은 마지막 원소가 정답.

 

 

풀이 2.

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        Map<String, Integer> hm = new HashMap<String, Integer>();

        // 참가자 수만큼 value 증가
        for(String p : participant) {
            // 동명이인을 고려해야한다
            if(hm.get(p) == null) {
                hm.put(p, 1);
            }else {
                hm.put(p, hm.get(p) + 1);
            }
        }

        // 완주자 수만큼 value 감소
        for(String c : completion) {
            hm.put(c, hm.get(c) - 1);
        }

        // value가 1인 key가 정답
        for(String key : hm.keySet()) {
            if(hm.get(key) == 1) {
                answer = key;
                break;
            }
        }
        return answer;
    }
}

HashMap 사용한 풀이.

참가자 수만큼 Map.entry의 value를 1씩 증가시킨다. 이때 동명이인 존재하는 경우까지 고려해야한다.

그 후 완주자 수만큼 value를 1씩 뺀다.

value가 1인 key가 완주하지 못한 선수.