프로그래머스: 완주하지 못한 선수 (java)

MineeHyun·2024년 7월 9일

문제 풀이

목록 보기

12/25

문제 설명

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

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.

풀어보자

participant.length -1 = completion.length
지옥의 for문을 돌려서 비교하고 없으면 return하면 되는 거 아님?
2-1. 중복되는 이름이 있을 수 있으므로 (ex: participant에 두 번 나오고 completion에 한 번 나오면 이것을 반환해야 함) 그러면 안됨
파이썬으로 풀면 dictionary를 썼을 것 같은데...
이 문제 시간 제한이 없다. (!) 지옥의 for문 ON

그렇게 나온 첫번째 코드

import java.util.Arrays;
import java.util.Collections;
class Solution {
    public String solution(String[] participant, String[] completion) {
        int[] participantCount = new int[participant.length];
        int[] participantFlag = new int [participant.length];

        for (int i=0; i<participant.length; i++){
            participantCount[i] = Collections.frequency(Arrays.asList(participant), participant[i]);
        }
        for (int i=0; i<participant.length; i++){
            for (int j=0; j<completion.length; j++){
                if (participant[i].equals(completion[j])){
                    participantFlag[i] = 1;
                    break;
                }
            }
            if (participantFlag[i] != 1)
                return participant[i];
        }
        for (int i=0; i<participantCount.length; i++){
            if (participantCount[i] != 1)
                return participant[i];
        }
        return " ";
    }
}

participantCount에다가 Array 안에 이 이름이 몇 번 등장하는지 세어 넣는다.
participant[i]와 completion[j]가 같으면 participantFlag를 1로 설정한다.
만약 inner loop를 돌고 나왔는데 participantFlag가 1이 아니면 (j를 모두 돌고도 같은 이름이 없었으면) 그 이름을 return한다.
이 for문을 다 돌고 나서... participantCount를 순회하며 Count가 1이 아니면 return한다.
=> (1) 이름이 participant에만 있고 completion에는 없는 경우를 먼저 찾고 (2) participant에 두 번 이상 나오는 경우를 찾는다.

결과
일단 개 오래 걸릴 것을 각오하고 풀긴 했지만 진짜 겁나게 오래 걸린다. ㄷㄷ

무엇이 문제일까...

일단 어마어마하게 오래 걸리는 것이 아주 문제
그리고 participant에 두 번 이상 등장하는 경우: 요것을 이상하게 짜둬서 그런 것 같다. 예를 들어 두 번 나오는 이름이 두 개 이상일 경우... 이럴 때 잘 못해주고 있다.
어떻게 해야 할까? dictionary처럼 이름으로 직접 찾는 게 편할 것 같다. index로 하기에는 participant와 completion에서 정확히 몇 번 어떻게 나오는지 찾기 어려울 것 같다.

다른 사람들의 멋진 풀이를 보고 고민해보기

파이썬: 딕셔너리로, key: 이름, value: participant에 등장한 만큼 +1, completion에 등장한 만큼 -1 => value가 1인 것이 완주하지 못한 사람
자바: 정렬하고 나면 두 Array는 하나의 요소만 빼고 완전히 같은 배열! 이 하나의 다른 요소를 찾아내면 된다.

import java.util.Arrays;
class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);
        int j;
        for (j = 0; j<completion.length; j++){
            if (!participant[j].equals(completion[j])){
                return participant[j];
            }
        }
        return participant[j];
    }
}