일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- androidstudio
- WebOS
- SWEA
- 자바
- 대학원
- py
- SQL
- 안드로이드스튜디오
- Matrix Factorization
- LEVEL2
- level3
- build
- 내휴학생활중의아주큰일
- 프로그래머스
- level1
- 다시풀기
- Github
- 어렵다
- BFS
- 대학원일기
- 컨트리뷰톤
- 휴학
- level4
- 파이썬
- 컴퓨터비전
- java
- MSBuild
- Python
- D3
- git
Archives
- Today
- Total
bit가 눈 앞에서 왔다갔다
Py) 프로그래머스 64063 호텔 방 배정 본문
https://programmers.co.kr/learn/courses/30/lessons/64063
1. 내 접근
방번호를 인덱스로 취급해서 계산한다.
true/false로 비었는지 아닌지 여부를 판단하고,
for문 / index()를 통해 손님이 요구하는 방 번호보다 큰 번호의 방 중 최소를 찾는다.
2. 코드
2.1 효율성통과 못함
def solution(k, room_number):
answer = []
visited = [False for _ in range(k+1)]
for room in room_number:
if visited[room] == False:
visited[room] = True
answer.append(room)
else:
for i in range(room+1, len(visited)):
if visited[i] == False:
visited[i] = True
answer.append(i)
break
return answer
2.2 효율성 통과 못함22
def solution(k, room_number):
answer = []
visited = [False for _ in range(k)]
for room in room_number:
if visited[room-1] == False:
visited[room-1] = True
answer.append(room)
else:
idx = len(visited[:room]) + visited[room:len(visited)].index(False)
visited[idx] = True
answer.append(idx+1)
return answer
* index()의 시간복잡도: O(1)
3. Solution
3-1. 사용 알고리즘, 자료구조: x
3-2. 사용 자료형: dictionary
3-3. 로직
1) 딕셔너리를 사용해서 배정된 방을 관리한다.
2) 처음 선택된 방(아직 배정안된)을 딕셔너리에 넣을때, value로 해당 방의 수보다 +1보다 큰 수를 넣어준다.
3) 이미 배정된 방이라면, temp 딕셔너리에 재호명된 번호를 넣어주고, 배정된 방의 그 다음 방(value +1해서 넣었으므로)이 배정되었는지 확인한다. (이런식으로 recom을 그 다음 방으로 계속 갱신)
4) 배정되었다면 temp 딕셔너리에 넣어줘서 이후 배정안된 방을 만났을 때, 배정되지 않은 위치를 각각 설정해줄 수 있게 한다.
3-4. 코드
def solution(k, room_number):
answer = []
room = {}
for num in room_number:
recom = room.get(num, 0) # room[num]의 value (그다음 방) || 0
if recom: # 그 다음 방을 추천한다면?
tmp = [num]
while True:
idx = recom
recom = room.get(recom, 0) # 갱신
if not recom: # 추천한 방이 비었다면
room[idx]= idx+1 # 으ㅏㅇ어ㅏ앙아아ㅏㅇ나아
answer.append(idx)
for i in tmp:
room[i] = idx + 1
break
tmp.append(recom)
else:
room[num] = num+1
answer.append(num)
return answer
4. 피드백
room[idx] = idx+1을 room[idx]: idx+1이라고 함
....
반응형
'Algorithm > Prob' 카테고리의 다른 글
Py) 프로그래머스 62048 멀쩡한 사각형 (0) | 2022.03.18 |
---|---|
Py) 프로그래머스 17676 [1차] 추석 트래픽 (0) | 2022.03.16 |
Py) 프로그래머스 67259 경주로 건설 (0) | 2022.03.10 |
SQL) 95410, 95043 (0) | 2022.03.05 |
Py) 프로그래머스 67256 키패드 누르기 (0) | 2022.03.01 |
Comments