프로그래머스 : 완주하지 못한 선수 [Java]

이동엽·2022년 11월 3일

Java hash 백준 알고리즘 코딩테스트 코테 프로그래머스 해시 해시맵

코딩테스트

목록 보기

8/9

프로그래머스를 통해 해시 알고리즘 문제 중 완주하지 못한 선수를 푼 과정을 기록합니다.

💡 첫번째 시도

→ 문제에서 주어진 배열 값 중, 참가자 목록에는 있지만 완주자 목록에는 없는 사람을 리턴하자!

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

        forP:
        for (String p : participant) { // p 하나 뽑기
            isChecked = false; //초기 설정은 발견 못함
            forC:
            for (String c : completion) { // c 하나 뽑기
                //같은게 있다면? 완주자! -> 따라서 다음 반복문으로.
                if (p.equals(c)) {
                    isChecked = true; //발견했으니 값 바꾸기
                    continue;
                }
            }

            if (!isChecked) { //completion을 순환했을때, 발견하지 못했으면?
                answer = p;   //p가 완주하지 못한 참가자이므로 리턴!
            }
        }

        return answer;
    }
}

위 풀이의 결과

참가자 중 동명이인이 없는 경우에만 올바른 결과를 리턴한다.
최악의 경우, 시간 복잡도가 어마어마하게 커진다.

💡 두번째 시도

→ Arrays클래스의 내장 메소드를 이용해 비교 전, 정렬을 하자.
→ 정렬 결과는 완주를 했다면 인덱스마다 같은 값일 것이다.
→ 두 배열에서 값이 다르다면? 해당 인덱스의 참가자가 완주하지 못한 선수이다!!

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

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

        for(int i=0; i<participant.length; i++) { 
            if(i == completion.length) {
            	//가장 마지막까지 비교할 경우, completion은 더 이상 비교할 값이 없음.
            	//따라서 participant[i]가 완주하지 못한 선수이다.	
                answer = participant[i];
                break;
            }
            if(!participant[i].equals(completion[i])) { 
            	//값이 다를 경우엔 참가자가 완주하지 못한 선수
                answer = participant[i];
                break;
            }
        }

        return answer;
    }
}

위 문제의 결과

→ 정확성과 효율성 테스트는 통과하여 제출이 가능했지만, 해시 문제인데 해시를 사용하지 않았다.

💡 해시를 이용한 풀이

→ HashMap을 만들어, Key에는 participants를 넣고 Value에는 완주자를 구분하기 위한 1을 넣는다.
→ 이후, HashMap에서 completion을 찾으면, 해당 데이터의 Value를 0으로 바꾼다.
→ HashMap에서 Value가 홀로 1인 데이터를 찾아 Key를 리턴한다.

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

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

        for (String player : participant)
            map.put(player, map.getOrDefault(player, 0) + 1);
        for (String player : completion)
            map.put(player, map.get(player) - 1);

        Iterator<Map.Entry<String, Integer>> iter = map.entrySet().iterator();

        while (iter.hasNext()) {
            Map.Entry<String, Integer> entry = iter.next();
            if (entry.getValue() != 0) {
                answer = entry.getKey();
                break;
            }
        }
        return answer;
    }
}