[알고리즘/Programmers] LV1. 완주하지 못한 선수

Programmers LV1.완주하지 못한 선수

 

문제 설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 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"

 

사용 언어

Java

 

해결 방법

참가자를 ArrayList에 담고 완주자를 참가자에서 하나씩 빼도록 하는 알고리즘을 짰다. 정확성은 통과하였으나 효율성에서 실패하였다. 다른 풀이를 참고하여 해결하였다.

 

1. ArrayList 이용 -> 정확성 통과, 효율성 실패

2. 정렬된 참가자, 완주자 배열의 인덱스 위치 기준으로 동일하지 않을 경우 반환 -> 모두 통과

3. HashMap 이용 -> 모두 통과

 

알게된 것

• asList 로 나온 List에 데이터를 줄이거나 늘리는 행위 할 경우 에러 주의할 것
  
  • 에러
    List<String> list = Arrays.asList(participant);
    UnsupportedOperationException
  • 정상
    List<String> list = new ArrayList<Sting>();
    list.addAll(Arrays.asList(participant));
• Hash 관련 Collection
  • HashMap : Key-Value 로 중복 허용하지 않음. Key는 참가자 이름, Value는 카운트갯수를 넣어서 활용할 수 있다.
    (중복 허용안된다고 생각하여 시도를 안했는데 카운트를 세서 판단할 수 있었다.)
  • HashSet : 값만 넣음. 중복 허용하지 않음.
• HashMap API
  • map.getOrDefault(player, 0)
    : map에 해당 key 값이 없으면 초기화 값을 지정할 수 있다.
  • map.keySet()
    : key Set 을 가져와서 for문으로 돌릴 수 있다.

 

코드

no_solution() : 내가 짠 실패한 코드 (ArrayList)
solution1() : 2번 방법
solution2() : 3번 방법

public class test_42576 {
    public static void main(String[] args) {
        String[] participant = {"mislav", "stanko", "mislav", "ana"};
        String[] completion = {"stanko", "ana", "mislav"};

        System.out.println(solution2(participant, completion));
    }

    public static String no_solution(String[] participant, String[] completion) {
        String answer = "";

        List<String> parList = new ArrayList<>();
        parList.addAll(Arrays.asList(participant));

        // 완주자를 순회한다
        for(String c : completion) {
            int size = parList.size();
            int i = 0;
            while(i < size) {
                // 참가자에 존재하면 해당 참가자 제거
                if(parList.get(i).equals(c)) {
                    parList.remove(i);
                    break;
                }
                i++;
            }

        }
        answer = parList.get(0);
        return answer;
    }

    public static String solution1(String[] participant, String[] completion) {
        String answer = "";
        String temp = "";

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

        int i = 0;

        while(i < completion.length) {
            if(!completion[i].equals(participant[i])) {
                temp = participant[i];
                break;
            }
            i++;
        }

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

        return answer;
    }

    public static String solution2(String[] participant, String[] completion) {
        String answer = "";
        Map<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);

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

---

문제 보고 아 쉽네! 생각하고 후딱 풀 수 있을 줄 알았는데 완전 실패였다. 당연히 리스트에서 제거하면서 남은 것을 리턴하면 될 줄 알았다. 그렇게 쉬운 문제일리 없지,, 효율성 테스트에서 실패하고 결국 다른 풀이를 보았다. 배열을 정렬해서 인덱스 비교하며 코드 간결하게 답을 쫙 내는 코드를 보고 깜짝 놀랐다. hashMap 으로 쓸 생각도 안했는데 처음 보는 getOrDefault 메서드를 사용해서 풀 수 있었다. 몰랐던 것들을 다시 짚어보게 되었다! 잊지 말아야지 ㅠ-ㅠ