프로그래머스 코딩테스트 고득점 Kit의 문제입니다.
https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit
문제
https://programmers.co.kr/learn/courses/30/lessons/64063
내가 작성한 코드
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 8)
def find(room, i):
if i not in room:
room[i] = i + 1
return i
occupied = find(room, room[i])
room[i] = occupied + 1
return occupied
def solution(k, room_number):
answer = []
room = defaultdict()
for num in room_number:
answer.append(find(room, num))
return answer
- 유니온 파인드
- 원하는 방 번호에 대해, 배정이 가능한 번호를 저장
다른 사람이 작성한 코드
import sys
sys.setrecursionlimit(10000000) # 설정해주지 않으면 재귀가 많이 일어나면서 런타임에러 등이 나타날 수 있다.
def findEmptyRoom(number, rooms): # 빈방을 찾는 함수
if number not in rooms:
rooms[number] = number + 1
return number
empty = findEmptyRoom(rooms[number], rooms)
rooms[number] = empty + 1
return empty
def solution(k, room_number):
answer = []
rooms = dict() # 몇번 방이 비어있는지 체크하는 딕셔너리
for number in room_number:
emptyRoom = findEmptyRoom(number, rooms)
answer.append(emptyRoom)
return answer
- 계속 시간초과가 발생해서 위 코드를 참고했다
기억해야할 것
- 딕셔너리를 이용한 유니온 파인드
- 신기했던 게, 리스트로 똑같이 구현했는데 시간초과다
- 아무래도 k가 10^12일 경우 초기화에만 해당 크기 만큼의 시간이 필요해서 발생하는 듯 하다
'코딩테스트' 카테고리의 다른 글
[프로그래머스][위클리챌린지] 8주차 - ? (0) | 2021.09.27 |
---|---|
[프로그래머스][KAKAO_인턴][2019] 징검다리 건너기 (0) | 2021.09.08 |
[프로그래머스][KAKAO_인턴][2019] 불량 사용자 (0) | 2021.09.08 |
[프로그래머스][KAKAO_인턴][2019] 튜플 (0) | 2021.09.08 |
[프로그래머스][KAKAO_인턴][2020] 크레인 인형뽑기 게임 (0) | 2021.09.08 |