프로그래머스 문제 풀이 (2) 완주하지 못한 선수

 

" 배열 두 개 드릴테니까 거기서 다른 값 한 개 찾아내세요. " 라는 문제다.

사실 기본적인 for문을 배웠다면 누구나 풀 수는 있다. 어떤 방법을 택하냐의 문제지.

이 문제의 카테고리가 Hash인 만큼, 시간이 오래 걸리는 문제는 아니기 때문에 완전 단순한 for문과 해시를 사용한 for문 두가지로 나누어 풀고 속도를 측정해봤다.

 

* 문제를 풀고 난 뒤 다른 사례를 찾아봤는데 2중 for문을 사용하는 경우 간당간당하게 통과하거나 실패하는 사례도 있는 것 같다. 어지간하면 다 통과.

 

 

 

 

 

 

 

 

 

1. 기본 for문

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);
        // 각 배열 정렬
        
        for(int i=0; i<participant.length-1; i++) {
            if (!participant[i].equals(completion[i])) {
                return participant[i];
            }
        }
        
        return participant[participant.length-1];
        // 위에서 답을 구하지 못했다면 무조건 마지막 인덱스가 정답이 된다.
    }
}

 

본래 역할에 충실한 방법으로 작성했다.

우선 두 배열을 정렬한 뒤 서로 비교한다.

비교하는 도중 다른 값이 있으면 해당 값이 완주하지 못한 선수의 이름이다. (정렬해서 순서가 완전히 같으므로)

 

그런데 participant의 length에 맞춰서 for문을 돌려버리면 completion에서 Exception이 발생한다.

그래서 우선 completion의 크기에 맞춰서 반복문을 돌린다. 그런데 반복문을 다 돌았는데 다른 값이 없었고, 문제 조건에서 반드시 완주하지 못한 선수가 한 명 있다고 했다. 그렇다면 당연히 완주하지 못한 선수는 마지막 인덱스에 있을 것이다.

따라서 paticipant[participant.length-1]을 리턴해준다.

 

 

 

이렇게 풀어도 효율성에 만점을 준다. 

내가 사용한 Arrays.sort로 해당 배열을 정렬했을 때 시간 복잡도가 정확히 어떻게 될지는 모르겠지만 기본 내장 함수에서 카운팅 정렬 같은 특이한 걸 사용할 리는 없기 때문에 O(nlogn)일 것으로 예상된다.

그리고 배열을 순회하기 위해 O(n)의 시간 복잡도가 필요하다.

 

당연히 먼저 보여준 게 효율이 떨어지는 쪽이기 때문에 다음 코드도 확인하자.

 

 

 

 

 

 

2. HashMap을 이용한 풀이

import java.util.*;

class Solution {
    public static String solution(String[] participant, String[] completion) {
        Map<String, Integer> map = new HashMap<>();

        for (String str : participant) {
            if (map.containsKey(str)) {
                map.put(str, map.get(str) + 1);
            } else {
                map.put(str, 1);
            }
        }

        for (String str : completion) {
            map.put(str, map.get(str) - 1);
        }

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

 

배열에서 처음 만나는 문자열(선수 이름)이 있을 때 Key로 등록하고 Value로 1을 준다.

그 후 완주한 선수 목록을 순회하며 해당 문자열(선수 이름)으로 Key를 조회하고 만약 해당 Key의 Value를 1씩 빼준다.

만약 선수 이름이 중복된다면 Value이 -1이 될 것이고, 완주하지 못했다면 1인 상태로 남아있을 것이다.

따라서 get(선수이름)이 0이 아닌 경우 해당 Key(선수 이름)이 완주하지 못한 선수의 이름이다.

 

 

코드 길이만 보면 이쪽이 더 너저분해보이지만 배열을 순회할 때 필요한 시간 복도인 O(n)을 제외하면 hashMap에서 모든 키의 검색에 필요한 시간 복잡도가 O(1)인 것을 고려했을 때 위의 코드보다 훨씬 효율적이라는 것을 알 수 있다.

(아직 시간 복잡도를 합산해서 표기할 줄 모른다..)

 

최소 2배 빠른 속도로 실행되는 것을 확인할 수 있다.