[Programmers/JAVA] 01. 완주하지 못한 선수

📄  완주하지 못한 선수

https://school.programmers.co.kr/learn/courses/30/lessons/42576

 

 

문제 분석

마라톤에 참가한 선수의 이름이 담긴 배열 participant, 완주한 선수들의 이름이 담긴 배열 completion 이 주어진다.

이 때, 완주하지 못한 선수의 이름을 리턴하는 문제이다.

 

접근 방법

 완전 탐색  을 사용하여 두 배열의 값이 동일하면 공백으로 치환한다.

for 문을 사용하여 공백으로 치환 된 participant 배열의 값 중 공백이 아닌 값을 리턴한다.

 

배열의 크기를 $N$이라고 할 때, 시간 복잡도는 $O(n^{2})$이다.

$N$은 최대 $10^{5}$이므로 최대 수행 횟수는 $10^{10}$이고, 따라서 효율성 테스트에서 통과할 수 없다.

 

코드 설계

# 결과를 저장하는 문자열 result 를 선언한다.

# 이중 for 문을 사용하여 participant 와 completion 배열의 갑이 동일하면 공백으로 치환한다.

#  for 문을 사요하여 participant 배열의 값 중 공백이 아닌 값을 리턴한다.

 

코드 구현

class Solution {
    public String solution(String[] participant, String[] completion) {
        String result = "";
        
        for(int i=0; i<participant.length; i++) {
            for(int j=0; j<completion.length; j++) {
                if(participant[i].equals(completion[j])) {
                    participant[i] = "";
                    completion[j] = "";
                }
            }
        }
        
        for(int i=0; i<participant.length; i++) {
            if(!participant[i].equals("")) {
                result = participant[i];
            }
        }
        
        return result;
    }
}

 

---

 

접근 방법

 정렬  을 이용하여 participant 배열에는 존재하지만 completion 배열에는 존재하지 않는 선수를 찾을 것이다.

for 문을 한 번만 사용하기 위해서는 두 배열을 정렬한 후, 선수들의 명단을 살펴봐야 한다.

두 배열의 크기를 $N$, $M$ 이라고 하면 시간 복잡도는 $O(MN)$, 정렬의 시간 복잡도는 $O(NlogN)$이다.

따라서 정렬을 이용할 경우 총 시간 복잡도는 $O(NlogN + NM) == O(NlogN)$이다.

 

코드 설계

# 두 배열 participant 와 completion 를 정렬한다.

# for 문을 돌며 participant[i] 의 값과 completion[i] 의 값이 같으면 완주한 선수, 다르면 완주하지 못한 선수이다.

# 단, completion 배열의 길이가 participant 배열의 길이보다 짧으므로 completion 길이까지만 for 문을 수행한다.

# 모든 for 문을 수행한 뒤에도 결과가 리턴되지 않으면 paricipant 마지막 원소값이 완주하지 못한 선수이다.

 

코드 구현

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Arrays.sort(participant);
        Arrays.sort(completion);
        
        for(int i=0; i<completion.length; i++) {
            if(participant[i].equals(completion[i])) continue;
            else return participant[i];
        }
        return participant[participant.length - 1];
    }
}

 

---

 

접근 방법

 해시테이블  을 사용하여 인원수가 0이 아니거나 테이블에 저장되지 않은 값을 발견하면 완주하지 못한 선수이다.

해시테이블에 participant 배열의 선수의 이름을 key, 인원 수를 value 로 저장한다.

completion 를 순회하며 동일한 이름이 있을 때 마다 인원수를 하나씩 줄여 나간다.

 

코드 설계

# 이름을 key, 인원수를 value로 하는 해시테이블을 생성한다.

# participant 를 순회하며 해시테이블에 이름과 인원수를 저장한다.

# 테이블에 주어진 이름이 없으면 value = 0 (default) + 1, 이름이 있다면 value = value + 1 로 설정한다.

# completion 을 순회하며 해시 테이블에 이름이 있다면 해당 이름의 value 값을 감소시킨다.

 

코드 구현

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> table = new HashMap<>();
        
        for(String a : participant) {
            table.put(a, table.getOrDefault(a, 0) + 1);
        }
        
        for(String b : completion) {
            table.put(b, table.get(b) - 1);
        }
        
        for(String c : table.keySet()) {
            if(table.get(c) != 0) {
                return c;
            }
        }
        
        return null;
    }
}