프로그래머스 달리기 경주 테스트 9, 10, 11, 12, 13번
에서 시간초과가 발생해 68.8점으로 실패했다.
뭐가 문제인지 몰랐는데, 같이 스터디하는 분 덕분에 알게되어 정리해보았다.
문제 설명
얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열
players
와 해설진이 부른 이름을 담은 문자열 배열callings
가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요.
제한 사항
- 5 ≤
players
의 길이 ≤ 50,000
players[i]
는 i번째 선수의 이름을 의미합니다.
players
의 원소들은 알파벳 소문자로만 이루어져 있습니다.
players
에는 중복된 값이 들어가 있지 않습니다.
3 ≤players[i]
의 길이 ≤ 10- 2 ≤
callings
의 길이 ≤ 1,000,000
callings
는players
의 원소들로만 이루어져 있습니다.
경주 진행중 1등인 선수의 이름은 불리지 않습니다.
class Solution {
public String[] solution(String[] players, String[] callings) {
List<String> list = new ArrayList<>(Arrays.asList(players));
// 모든 플레이어의 이름을 arrayList에 저장
for (int i = 0; i < callings.length; i++) {
// callings 배열을 돌면서 list에 이름이 있는지 확인 후
// 있으면 list에서 순서 교환
String name = callings[i];
int idx = list.indexOf(name);
String person = list.get(idx - 1);
list.set(idx, person);
list.set(idx - 1, name);
}
return list.toArray(new String[0]);
}
}
이유는 arrayList의 indexOf()
때문이었다.
ArrayList.indexOf
은 리스트를 순환하면서 그 값을 가져온다. 즉, 항목의 수에 따라 시간복잡도가 결정되므로 O(n)
의 시간복잡도를 가진다.
그래서 겉으로 보기엔 for문
1개만 사용했지만, 내부적으로는 2중for문
을 사용한 것이 되어서 시간초과가 발생한 것이었다.
다른 코드를 참고해보니 HashMap을 이용해서 문제를 푼 경우가 많았다.
그래서 HashMap의 get()에 대해 알아보았다.
전달된 키 객체를 hascode를 적용하고 table에서 해당 인덱스값을 가져와 그 값을 반환하고, 못 찾는다면 null을 반환한다.
아래 코드를 살펴보면 HashMap의 검색 알고리즘이 O(1) 인 것을 확인할 수 있다.
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashcode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next){
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
Reference
https://llnote.tistory.com/725
유익한 자료 감사합니다.