14. 완주하지 못한 선수

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%AC

def 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-valueget

def 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 ""
}