프로그래머스 완주하지 못한 선수 [Java]
문제출처
https://programmers.co.kr/learn/courses/30/lessons/42576
먼저 효율성 검사에서 빵점을 맞은 코드
import java.util.*;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
List<String> completion_list = new ArrayList<String>(Arrays.<String>asList(completion));
for(String p : participant){
int idx = completion_list.indexOf(p);
if(idx < 0){
answer += p;
break;
}
completion_list.remove(idx);
}
return answer;
}
}
그래 명색이 대놓고 해시 문제인데 이건 아니겠지... 싶긴했다. (그래도 for문이 단 하나인데 설마 하는 기대를 쪼금 했다)
해시로 푼 코드 적기 전에 이것의 문제점을 적어놔야겠다 싶어서 블로그를 켰다.
우선 for문 안에서 사용되는 indexOf()함수의 시간 복잡도는 O(n)
list의 remove() 이것또한 시간복잡도가 O(n)이다. 그럼 여기서 또 list만큼 n번이 곱해지면 ....
그것도 for문은 participant 개수 만큼 돌기 때문에 이게 최대값인 10만이라면 정말 어마어마하게 오래걸릴것이다.
그렇다면 해시는?
해시를 사용해서 푼 코드
import java.util.*;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
HashMap<String, Integer> table = new HashMap<String, Integer>();
for(String p : participant){
if(table.containsKey(p)){
table.put(p, table.get(p) + 1);
}
else{
table.put(p, 1);
}
}
for(String c : completion){
table.put(c, table.get(c) - 1);
}
for(String key : table.keySet()){
if(table.get(key) != 0){
answer += key;
break;
}
}
return answer;
}
}
해시의 경우에는 대부분 시간복잡도가 O(1)이다.
containsKey(), get() 등등...
따라서 시간이 굉장히 줄어드는걸 확인할 수 있다.
이는 해시에 대해서 다시 공부한 글을 첨부하겠다.
'문제풀이 > 코딩테스트' 카테고리의 다른 글
프로그래머스 모의고사 [Java] (0) | 2022.02.24 |
---|---|
프로그래머스 K번째수 [Java] (0) | 2022.02.23 |
프로그래머스 소수 만들기 [Java] (0) | 2022.02.20 |
프로그래머스 크레인 인형뽑기 게임 [Java] (0) | 2022.02.18 |
프로그래머스 키패드 누르기 [Java] (0) | 2022.02.15 |