[프로그래머스] 완주하지 못한 선수 - 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"

---

나의 풀이

 

• Hash를 사용하지 않고 무작정 생각나는 대로 풀어본 코드 첫번째

public static String solution(String[] participant, String[] completion) {
        String answer = "";
        for(int i = 0 ; i < completion.length;i++){
            for(int j = 0 ; j < participant.length;j++){
                if(participant[j].equals(completion[i])){
                    participant[j] = "";
                    break;
                }
            }
        }
        for(int i = 0 ; i < participant.length;i++){
            if(participant[i].length()>0){
                answer = participant[i];
            }

        }
        return answer;
    }

풀이설명

1. 마라톤을 완주한 선수를 참가자와 하나씩 다 비교한다.

2. 같은 이름이 존재한다면 참가자 이름을 ""값으로 바꿔준다.

3. 참가자 이름 중 ""값이 아닌 값을 return한다.

 

📝 테스트는 통과했지만 효율성에서 다 틀렸습니다를 받았던 코드,,^_ㅠ ,,,내가 풀었지만 정말 효율성 하나도 없이 풀었던 것 같다... 그래서 고민고민 끝에 다시 생각해보았다. (Hash는 사용하지 않았다.)

---

• Hash를 사용하지 않고 무작정 생각나는 대로 풀어본 코드 두번째

    public static String solution2(String[] participant, String[] completion) {
        String answer = "";
        String result = "";
        /*
         문제 풀이 방식
         1. Arrays.sort()를 통해 정렬한다.
         2. 반복문을 실행하여 participant와 completion 다른 값을 return한다.
         */

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

        System.out.println(Arrays.toString(participant));
        System.out.println(Arrays.toString(completion));

        for (int i = 0 ; i<completion.length;i++) {
            if (!completion[i].equals(participant[i])) {
                answer = participant[i];
                break;
            }
        }

        if(answer.equals("")){
            answer = participant[participant.length - 1];
        }
        return answer;
    }

 

풀이 설명

1. Arrays.sort()를 이용하여 참가자와 완주자 정렬

2. 참가자[i] , 완주자[i]의 값을 비교한다.

3. 값이 다를 경우 answer에 참가자[i]값을 담아준다. 그리고 반복문 종료

4. 완주자 수 만큼 반복이 끝났는데 값이 모두 같을 경우 -> 참가자의 마지막 선수가 완주를 못함

5. 참가자 배열의 마지막 선수 이름을 answer에 넣어준다.

 

📝 이렇게 풀이하니 답과 효율성은 통과를 했지만 Hash문제인데 Hash를 사용하지 않았다... 다른사람들은 어떻게 풀이했는지 봐야겠다

---

• Hash를 사용한 다른사람 풀이

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> hm = new HashMap<>();
        for (String player : participant) hm.put(player, hm.getOrDefault(player, 0) + 1);
        for (String player : completion) hm.put(player, hm.get(player) - 1);

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