-
14. 완주하지 못한 선수코딩 테스트/Level 1 2019. 10. 12. 23:00반응형
https://programmers.co.kr/learn/courses/30/lessons/42576
문제 자체는 어렵지 않습니다만...
알고리듬에 따라 효율성이 꽤 차이 날 수 있습니다.
효율성에 제한을 건다면 해시와 시간 복잡도에 대한 개념이 필요한 문제가 될 수 있습니다.파이썬
1명을 제외하고 전부 완주했다고 했으니까...
참가자와 완주자를 소팅 후 비교해서 이름이 다른 첫 번째 참가자가 불참자가 됩니다.소트 알고리듬에 따라 효율성이 좌우가 됩니다.
언어에 내장된 소팅 알고리듬은 보통 O(n log n) 정도의 시간 복잡도를 가지죠...def solution(participant, completion): participant.sort() completion.sort() for i in range(len(completion)): if participant[i] != completion[i]: return participant[i] return participant[i + 1] """ 효율성 테스트 테스트 1 〉 통과 (37.77ms, 86.6MB) 테스트 2 〉 통과 (63.73ms, 126MB) 테스트 3 〉 통과 (81.25ms, 153MB) 테스트 4 〉 통과 (83.34ms, 168MB) 테스트 5 〉 통과 (100.06ms, 168MB) """
리턴문에서 i를 이용하는 꼼수를 ... 파이썬의 변수 영역은 조금 묘하죠.
그럼 소팅을 하지 않고 비교하는 방법은 뭐가 있을까요?
해시 문제니까해시를 쓰면 O(n)에 근접하게 풀 수 있습니다.
https://wiki.python.org/moin/TimeComplexity딕셔너리는 해시 테이블로 작동됩니다.
딕셔너리를 이용해서 카운트할 수 있습니다.해싱에 대해서는 제 블로그에도 설명을 해 두었습니다.
https://comdoc.tistory.com/entry/17-%ED%95%B4%EC%8B%B1hashing-%ED%8C%8C%EC%9D%B4%EC%8D%ACdef solution(participant, completion): runners = {} for each in participant: runners.setdefault(each, 0) runners[each] += 1 for each in completion: runners[each] -= 1 for runner, num in runners.items(): if num == 1: return runner """ 효율성 테스트 테스트 1 〉 통과 (23.73ms, 21.7MB) 테스트 2 〉 통과 (42.01ms, 25.2MB) 테스트 3 〉 통과 (45.73ms, 27.6MB) 테스트 4 〉 통과 (53.38ms, 34MB) 테스트 5 〉 통과 (52.97ms, 33.9MB) """
setdefault도 알아두시면 편합니다.
https://www.daleseo.com/python-collections-defaultdict/딕셔너리의 get을 이용해도 소중한 한 줄을 줄일 수 있습니다.
https://wikidocs.net/16#key-valuegetdef solution(participant, completion): runners = {} for each in participant: runners[each] = runners.get(each, 0) + 1 for each in completion: runners[each] -= 1 for runner, num in runners.items(): if num == 1: return runner
테스트 1 〉 통과 (21.84ms, 21.7MB) 테스트 2 〉 통과 (36.46ms, 25.2MB) 테스트 3 〉 통과 (41.04ms, 27.5MB) 테스트 4 〉 통과 (52.24ms, 34MB) 테스트 5 〉 통과 (44.36ms, 33.9MB)
zip을 활용하여 한번의 순회를 줄일 수 있습니다.
def solution(participants, completions): runners = {} completions.append('') for participant, completion in zip(participants, completions): runners[participant] = runners.get(participant, 0) + 1 runners[completion] = runners.get(completion, 0) - 1 for runner, num in runners.items(): if num == 1: return runner
꽤 빨라야할 것 같은데 현실은 다르네요.
테스트 1 〉 통과 (27.79ms, 21.7MB) 테스트 2 〉 통과 (41.80ms, 25.1MB) 테스트 3 〉 통과 (53.02ms, 27.5MB) 테스트 4 〉 통과 (56.33ms, 33.9MB) 테스트 5 〉 통과 (55.53ms, 33.9MB)
딕셔너리를 이용해 카운트를 간편하게 해주는 collections.Counter 도 있습니다.
https://excelsior-cjh.tistory.com/94한줄의 로망 하지만 빠르지 않다..def solution(participant, completion): from collections import Counter return tuple((Counter(participant) - Counter(completion)).keys())[0] """ 테스트 1 〉 통과 (30.52ms, 24.3MB) 테스트 2 〉 통과 (47.04ms, 27.9MB) 테스트 3 〉 통과 (58.07ms, 30.1MB) 테스트 4 〉 통과 (77.71ms, 39MB) 테스트 5 〉 통과 (74.51ms, 39MB) """
Counter는
a = a.subtrack(b) 형식으로 사용할 수 없습니다.
a.subtrack(b) 형식으로 사용하셔야 합니다.
a = a - b는 가능하지만 음수 출력이 안됩니다.
미묘하지만 차이가 있습니다.
자세한 것은 위 링크를 보세요.자바스크립트
자바스크립트로도 속도 차이를 알아보겠습니다.
function solution(participant, completion) { participant.sort(); completion.sort(); for (let i = 0; i < participant.length; i++) { if (participant[i] != completion[i]) { return participant[i] } } } """ 효율성 테스트 테스트 1 〉 통과 (88.45ms, 53.3MB) 테스트 2 〉 통과 (131.06ms, 60.8MB) 테스트 3 〉 통과 (155.29ms, 67.9MB) 테스트 4 〉 통과 (176.68ms, 69.5MB) 테스트 5 〉 통과 (168.57ms, 70.4MB) """
자바스크립트의 for in 문은
배열일 경우 인덱스를
연상 배열(객체) 일 때는 키를 돌려줍니다.
배열의 경우 다른 언어와 스펙이 다르기 때문에 혼란스럽습니다.
function solution(participant, completion) { var temp = {} for (let i in participant) { if (participant[i] in temp) { temp[participant[i]]++ } else { temp[participant[i]] = 1 } } for (let i in completion) { if (completion[i] in temp) { temp[completion[i]]-- } } for (let i in temp) { if (temp[i] == 1) { return i } } } """ 효율성 테스트 테스트 1 〉 통과 (41.36ms, 56.9MB) 테스트 2 〉 통과 (50.03ms, 61.6MB) 테스트 3 〉 통과 (63.24ms, 67.7MB) 테스트 4 〉 통과 (73.68ms, 74.5MB) 테스트 5 〉 통과 (78.15ms, 74.2MB) """
게다가 자바스크립트에서 for in은 for문 보다 속도도 느립니다.
배열의 경우 장점이 전혀 없습니다. 배열의 경우 쓰지 않는 것을 추천합니다.
(자바에선 for in과 for의 속도가 비슷합니다. 좀 헛갈립니다. ㅠ,.ㅠ )
function solution(participant, completion) { var temp = {} for (let i = 0; i < participant.length; i++) { if (participant[i] in temp) { temp[participant[i]]++ } else { temp[participant[i]] = 1 } } for (let i = 0; i < completion.length; i++) { if (completion[i] in temp) { temp[completion[i]]-- } } for (let i in temp) { if (temp[i] == 1) { return i } } } """ 효율성 테스트 테스트 1 〉 통과 (24.53ms, 53.3MB) 테스트 2 〉 통과 (35.41ms, 61MB) 테스트 3 〉 통과 (41.14ms, 67.8MB) 테스트 4 〉 통과 (52.60ms, 70.1MB) 테스트 5 〉 통과 (52.72ms, 70.1MB) """
자바
import java.util.*; class Solution { public String solution(String[] participant, String[] completion) { HashMap<String, Integer> runner = new HashMap<>(); for (String each : participant) runner.put(each, runner.getOrDefault(each, 0) + 1); for (String each : completion) runner.put(each, runner.get(each) - 1); for (Map.Entry<String, Integer> each : runner.entrySet()) if (each.getValue() == 1) return each.getKey(); return null; } } """ 효율성 테스트 테스트 1 〉 통과 (37.77ms, 92.3MB) 테스트 2 〉 통과 (63.16ms, 98MB) 테스트 3 〉 통과 (73.96ms, 104MB) 테스트 4 〉 통과 (70.09ms, 106MB) 테스트 5 〉 통과 (62.75ms, 103MB) """
golang
func solution(participant, completion []string) string { runners := make(map[string]int) for _, s := range participant { runners[s]++ } for _, s := range completion { runners[s]-- } for runner := range runners { if runners[runner] == 1 { return runner } } return "" }
반응형