완주하지 못한 선수

안녕하세요, 오늘은 저번 시간에 이어서 코딩 테스트 연습 문제에 대해 글을 작성하려고합니다.
이번에 풀이하는 문제 역시 프로그래머스에서 제공하는 문제이며 누구나 무료로 풀 수 있습니다.

📚 문제 설명

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

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

 

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 마라톤을 끝내 완주한 선수들의 이름이 담긴

배열 completion이 주어질 때 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주시기 바랍니다.

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

📸 제한 사항

1) 마라톤 경기에 참여한 선수의 수는 최소 1명 이상 최대 100,000명 이하입니다.

2) completion의 길이는 participant의 길이보다 1 작습니다.

3) 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.

4) 참가자 중에는 동명이인이 있을 수 있습니다.

🗣 입출력 예시

participant	completion	return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "nikola", "vinko"]	["marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav"]	["stanko", "mislav"]	"mislav"

첫 번째, 두 번째 배열에서 "leo"와 "vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다. 그러나 세 번째 배열"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한 명은 완주하지 못했습니다.

 

📨 나의 해결책 (3시간 10분 소요)

[ 전체 소스코드 ]

입출력 예시에 작성된 participant와 completion 배열을 매개변수로 전달 받습니다. 그 후 전달 받은 배열을 Arrays 클래스의 sort 메소드를 통해서 각각 정렬을 시켜줍니다. 이러한 과정을 통해서 participant와 completion 배열 속 데이터의 순서는 같아집니다.

 

그 후 반복문을 통해서 participant와 completion 배열 속 존재하는 데이터의 값을 비교합니다. 만약 participant 배열 속 존재하는 데이터가 completion 배열에 존재하지 않는다면 그 선수가 바로 마라톤에 결국 완주를 하지 못한 한 사람이 되는 것입니다.

import java.util.*;

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

        int i;

        for(i = 0; i < participant.length-1; i++) {
            if(!participant[i].equals(completion[i])) {
                return participant[i];
            }
        }
        return participant[i];
    }
}

🎨 모범 답안 (Hash)

이번 문제는 저번 문제에 비해 구조적으로 별로 어렵지 않았습니다. 그러나 저번과는 달리 정확성 테스트 뿐만이 아닌 효율성 테스트 또한 존재하여 문제에 대한 코드의 질과 성능이 일정 기준보다 높아야 문제를 해결할 수 있었습니다. 그렇기 때문에 저는 다양한 방법을 시도하여 문제를 풀어보았지만 효율성 테스트에서 모두 불합격 하였습니다. 결국 이 문제에 대한 해법은 바로 해시였습니다.

import java.util.HashMap;

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;
    }
}

👍 글을 마치며

이번 과정을 통해 문제가 한 문제더라도 다양한 정답이 나올 수 있다는 것을 알게되었습니다. 코딩 테스트 문제를 풀 때는 문제에 대한 설명과 조건들을 보고 이 문제에 어떤 자료구조 또는 알고리즘이 적합한지 떠오르는 것이 중요하고 효율적인 코드를 짤 수 있도록 노력해야합니다. 아직은 그러한 노하우와 경험들이 부족하여 힘들지만 꾸준히 노력하고 도전한다면 천천히 성장할 수 있을 것입니다.