728x90
풀이
def solution(participant, completion):
answer = ''
cDic = {}
for i in completion:
if i in cDic:
cDic[i] += 1
else:
cDic[i] = 1
for i in participant:
if i in cDic:
cDic[i] -= 1
if cDic[i] == 0:
del cDic[i]
else:
answer = i
break
return answer
배열로 풀었다가 효율성 테스트 때문에 애먹은 문제.
- 딕셔너리를 사용해서 풀었다. 딕셔너리는 해시를 사용하기 때문에 검색 시간복잡도가 O(1)이다.
- 딕셔너리는 d1 = {} 또는 d1 = dict() 으로 선언한다.
- 우선 completion 리스트의 각 값을 key로 해서 딕셔너리를 생성했다. 이때 value는 completion 안에 key 값이 몇 개있는지를 적었다.
- 그리고 participant를 반복문을 돌면서 딕셔너리 안에 있는지 확인하고, 없으면 그게 정답이다.
- 딕셔너리 안에 있다면 value 값을 -1해주고, 만약 0이되면 더이상 없다는 뜻이므로 딕셔너리에서 삭제한다.
Python Dictionary 기능 정리
- 선언
- dict1 = {}
- dict1 = dict()
- 접근
- dict1[key] # value 접근, 키 값 없으면 오류남
- dict1.get(key) # value 접근 키 값 없어도 오류 안남
- dict1.keys() #딕셔너리 내 모든 key를 반환
- dict1.values() #딕셔너리 내 모든 value를 반환
- dict1.items() #딕서너리 내 모든 key와 value 쌍을 반환 (반환 값은 리스트나 튜플이 아님)
- 삭제
- del dict1[key]
- dict1.pop(key) #value를 반환하면서 삭제
- 삽입
- dict1[key] = value
- dict1.update(dict2)
- dict1.setdefault(key, value)
- dict1 = dict.fromkeys([key1, key2, key3, ...], defalut) #key 리스트에 default값을 value로 짝지어서 딕셔너리를 생성
반응형
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 코딩테스트 고득점 Kit / 해시] 전화번호 목록 (python) (1) | 2024.01.10 |
---|---|
[프로그래머스 코딩테스트 고득점 Kit / 해시] 폰켓몬 (python) (0) | 2024.01.10 |
[프로그래머스 코딩테스트 고득점 Kit / 스택/큐] 주식가격 (python) (0) | 2024.01.07 |
[프로그래머스 코딩테스트 고득점 Kit / 스택/큐] 다리를 지나는 트럭 (python) (0) | 2024.01.06 |
[프로그래머스 코딩테스트 고득점 Kit / 스택/큐] 프로세스 (python) (2) | 2024.01.05 |