[Java] 프로그래머스(level1) - 완주하지 못한 선수
입출력 예시
Input-1
participant = [“leo”, “kiki”, “eden”]
completion = [“eden”, “kiki”]
Output-1
“leo”
Input-2
participant = [“marina”, “josipa”, “nikola”, “vinko”, “filipa”]
completion = [“josipa”, “filipa”, “marina”, “nikola”]
Output-2
“vinko”
Input-3
participant = [“mislav”, “stanko”, “mislav”, “ana”]
completion = [“stanko”, “ana”, “mislav”]
Output-3
“mislav”
문제 풀이
이 문제를 배열을 정렬하여 반복문을 활용하여 풀었지만, 해시로 풀어야 좋은 성능이 나오기에 두 가지 풀이 모두 작성한다.
정렬하여 반복문을 활용한 방식
주어진 participant 배열과 completion 배열을 정렬하여 completion의 길이만큼 반복하는 것이 키포인트다.
completion의 길이만큼 순회하며 두 배열을 검증해보자.
- participant[i]의 값과 completion[i]의 값이 같다면 participant[i]는 완주한 선수다.
- participant[i]의 값과 completion[i]의 값이 다르다면 participant[i]는 완주하지 못한 선수다.
- completion의 마지막까지 찾아봐도 participant[i]가 없다면 participant[i]는 완주하지 못한 선수다.
위 조건을 토대로 코드를 작성해보자.
1
2
3
4
5
6
7
8
9
10
11
12
Arrays.sort(participant);
Arrays.sort(completion);
String answer = "";
int idx = 0;
for(int i=0; i<completion.length; i++) {
if(!participant[i].equals(completion[i])) {
answer = participant[i];
break;
}
idx = i+1;
}
answer = participant[idx];
completion 배열의 길이만큼 순회하며 같지 않을 때의 participant[i] 값을 반환할 answer에 담고 탈출하였다.
같지 않을 때 바로 탈출한 이유는?
이미 완주하지 못한 선수는 1명이고 완주하지 못한 선수를 찾은 이상 나머지 반복문을 순회할 필요가 없기 때문이다.
또한 completion의 마지막까지 돌아도 없는 값이 participant에 존재할 경우 해당 participant[i]는 완주하지 못한 선수다. 위 상황일 경우에도 인덱스를 담았다가 answer에 인덱스로 대입하여 반환하였다.
해시를 활용한 방식
해시를 이용하면 훨씬 간단하게 풀 수 있다.
hashMap의 key와 value의 특성을 활용하여 participant 배열의 원소와 갯수를 세어 hashMap에 넣는다.
그리고 completion 배열을 돌며 이전에 담았던 원소마다 갯수를 차감한다.
그러면 자연스럽게 completion 배열에 없는 값과 중복된 값을 찾아낼 수 있다.
코드로 작성해보자.
1
2
3
4
5
6
7
8
9
String answer = "";
HashMap<String, Integer> hm = new HashMap<>();
for(String p : participant) hm.put(p, hm.getOrDefault(p, 0)+1); // 1
for(String c : completion) hm.put(c, hm.getOrDefault(c, 0)-1); // 2
for(Map.Entry<String, Integer> entry : hm.entrySet()) {
if(entry.getValue() == 1) answer = entry.getKey();
}
위 1번과 2번 과정을 통해 완주하지 못한 선수를 알 수 있다.
예를 들어보자.
1
2
3
p = [B, C, A], c = [B, C] 라고 한다면
hm = [B:1, C:1, A:1] // 1
hm = [B:0, C:0, A:1] // 2
위 내용대로 A가 완주하지 못한 선수임을 알 수 있다.
중복인 상황의 예도 확인해보자.
1
2
3
p = [B, C, A, B], c = [B, C, A] 라고 한다면
hm = [B:2, C:1, A:1] // 1
hm = [B:1, C:0, A:0] // 2
B가 중복일 경우에도 1,2번 과정을 통해 또 다른 B가 완주하지 못한 선수임을 알 수 있다.
실행 시간 비교
정렬하여 반복문을 활용한 방식
해시를 활용한 방식
확실히 해시를 이용했을 때 실행시간이 더욱 빠르다는 것을 알 수 있다.
작성 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.*;
class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] participant = {"leo", "kiki", "eden"};
String[] completion = {"kiki", "eden"};
// String[] participant = {"marina", "josipa", "nikola", "vinko", "filipa"};
// String[] completion = {"josipa", "filipa", "marina", "nikola"};
// String[] participant = {"B", "A", "B", "C"};
// String[] completion = {"B", "A", "C"};
long start = System.currentTimeMillis();
solution2(participant, completion);
long end = System.currentTimeMillis();
System.out.println("\n수행시간 = " + (end-start));
}
// 배열을 오름차순 정렬하여 반복문을 활용한 방식
public static String solution(String[] participant, String[] completion) {
Arrays.sort(participant);
Arrays.sort(completion);
String answer = "";
int idx = 0;
for(int i=0; i<completion.length; i++) {
if(!participant[i].equals(completion[i])) {
answer = participant[i];
break;
}
idx = i+1;
}
answer = participant[idx];
return answer;
}
// 해시를 활용한 방식
public static String solution2(String[] participant, String[] completion) {
String answer = "";
HashMap<String, Integer> hm = new HashMap<>();
for(String p : participant) hm.put(p, hm.getOrDefault(p, 0)+1);
for(String c : completion) hm.put(c, hm.getOrDefault(c, 0)-1);
for(Map.Entry<String, Integer> entry : hm.entrySet()) {
if(entry.getValue() == 1) answer = entry.getKey();
}
return answer;
}
}
회고
- 이 문제의 효율성을 따졌을 때 두 배열을 정렬하여 반복문을 적게 사용하는 것이 시간복잡도를 줄이는데 중요하다고 느꼈다.
- Hash를 활용하며 찾는 키가 존재한다면 찾는 키의 값을 반환하고 없다면 기본 값을 반환하는 getOrDefault() 메서드를 알게되었다.