2가지 모드로 나누어서 생각하기(코딩테스트 복기)

1. 문제

 

각 층마다 w개의 방으로 구성되고 전체 층은 h개로 구성된 호텔이 있다

 

사람들은 오전 11시에 체크아웃을 하고 오후 2시에 체크인을 한다

 

각 예약마다 k개의 연속된 방을 사람들이 체크인 날짜와 체크아웃 날짜에 맞춰서 예약을 한다

 

이 때 방을 나눠주는 규칙은 반드시 k개의 연속된 방으로 최대한 낮은 층, 최대한 낮은 번호의 방을 줘야한다.

 

주어지는 예약 리스트에서 예약을 받으면 1, 예약을 거절하면 0으로 하는 리스트를 출력해라

 

2. 나의 풀이

 

w개의 방과 h개의 층으로 구성된 호텔을 리스트로 구성함

 

def solution(w,h,reserves):
    
    hotel = [[0 for range(w)] for range(h)]

 

예를 들어 5개의 방에 2층으로 구성된 호텔을 생각해보고

 

k / 체크인/ 체크아웃

 

2 / 1 / 3

 

3/ 1 / 2

 

4/ 1 / 4

 

2/ 2 / 5

 

2/ 3 / 4

 

5개의 예약을 생각을 해보자

 

체크인 1일째에

 

 

위와 같이 예약이 찰 것이고

 

2일째에 2번째 예약한 팀이 나가고 4번째 팀이 들어올거

 

 

그리고 3일째에는 첫번째 팀이 나가고 5번째 팀이 들어올거임

 

 

그래서 이 문제가 상당히 어려운 점이 각 팀이 어디 위치에 들어가있는지 미리 정보를 다 받아놔야함

 

def solution(w,h,reserves):
    
    answer = []
    
    hotel = [[0 for range(w)] for range(h)]
    
    reserve_dict = {}

 

그래서 예약이 되면 1, 아니면 0을 넣을 answer와 reserve_dict라는 체크인시 어디 방에 들어갈지 정보를 담을 사전 구성

 

갑자기 이 이상이 생각이 안나서 대충 내가 썼던 코드 한번 생각나는대로 일단 써봄

 

정답이 중요한것보다 여기서 썼던 기술들을 한번 복기해보는게 중요해서

 

def solution(w,h,reserves):
    
    answer = []
    
    hotel = [[0 for range(w)] for range(h)]
    
    reserve_dict = {}
    
    now = 1
    
    checkin = True
    
    while len(answer) != len(reserves):
    
        if checkin:
    
            for ind,(k,checkin,_) in enumerate(reserves[len(answer):]):
            
                reserve = False
            
                if now == checkin:

                    for a,rooms in enumerate(hotel):
                    
                        for i in range(k): ##이게 맞던가?? 생각이 안남

                            if 1 in rooms[i:k+i]:

                                pass

                            else:

                                rooms[i:k+i] = [1] * k

                                reserve_dict[ind] = (a,list(range(i,k+i))

                                answer.append(1)

                                reserve = True

                                break

                    if reserve == False:

                        answer.append(0)
                
                else:
                    
                    now = checkin
                    
                    checkin = False
                    
                    break
                        
        else:
            
            for ind,(k,_,checkout) in enumerate(reserves):
                
                if now == checkout:
                    
                    try:
                        
                        a,b = reserve_dict[ind]
                        
                        for num in b:
                            
                            hotel[a][num] = 0
                    
                    except:
                    
                        continue
            
            checkin = True
        
    return answer

 

뭔가 코드 중간중간 빠진게 있을 수 있는데

 

중요한 기술은 다 담겨있는것 같으니까

 

-------------------------------------------------------------------------------------------------------

 

일단은 checkin 모드와 checkout 모드로 나눠서 생각해야한다는 점이 중요하다

 

2 / 1 / 3

 

3/ 1 / 2

 

4/ 1 / 4

 

2/ 2 / 5

 

2/ 3 / 4

 

위에 예시 예약표 생각해보면

 

1일차에 checkin을 먼저 다 하고

 

4번째 예약 들어갈때는 2일차인데

 

문제는 2번째 예약이 2일차에 checkout을 한다는 점이다

 

현재 날짜인 now=1로 초기화하고

 

if now == checkin이면 예약을 시작을 하는 것이다

 

이렇게 하면 사실 now=1부터 1씩 증가시켜나가서 생각할 필요가 없어진다

 

왜냐하면 for문을 돌면 now와 checkin이 다른 순간이 나올 것이다

 

그러면 현재 now에 지금 나온 checkin날짜를 저장시키고 (now=checkin)

 

checkin=False로 주어서 break후에 다음 while문을 돌게하여 checkout 모드로 들어가게 만든다

 

-------------------------------------------------------------------------------------------------------

 

두번째로는 매우 사소한거긴한데 enumerate unpacking을 할때

 

index, (unpacking할 item은 튜플로)

 

for ind,(k,checkin,_) in enumerate(reserves[len(answer):] 이런식으로 가능

 

-------------------------------------------------------------------------------------------------------------

 

세번째로는 hotel방에 사람 채울때

 

hotel 리스트를 전부 불러올 필요 없이 부분 채우기로

 

rooms[i:k+i] = [1] * k 이렇게만 하면 

 

hotel 리스트 내에 a층의 i번째부터 k+i-1번째가 자동으로 [1,1,1,...]로 바뀐다는 점

 

-------------------------------------------------------------------------------------------------------------

 

네번째로는 예약을 성공하면 answer에 1을 넣고 reserve=True로 바꾼다음에 내부 for문은 바로 빠져 나와야겠지

 

내부 for문을 다 돌고 나서라도 reserve=False이면 예약이 실패한거니까 answer에 0을 넣어주었던./.

 

이거는 초보적인거라

 

-------------------------------------------------------------------------------------------------------------

 

다섯번째로는 상당히 어려운 부분이었는데

 

어디부분에 예약이 되었는지 예약된 정보 reserve_dict를 구성한다는 점

 

예약번호를 key로 (층수, 방번호 index리스트)를 value로

 

 reserve_dict[ind] = (a,list(range(i,k+i)) 이거는 의외로 쉬웠다면

 

그리고 checkout모드에서 reserve_dict를 바탕으로 

 

for ind,(k,_,checkout) in enumerate(reserves):
                
    if now == checkout:

        try:

            a,b = reserve_dict[ind]

            for num in b:

                hotel[a][num] = 0

        except:

            continue

 

이게 좀 어려울 수 있는데

 

일단 현재 now는 예를 들어 1일차 checkin을 다 주고 2일차 checkin을 넣어야하는데 

 

1일차 checkin 넣은 것중에 2일차에 checkout할 수 있기 때문에 now=2로 넣고 checkout 할 얘들을 검사하는 과정

 

그래서 예약 리스트중에 checkout과 now가 맞다면

 

reserve_dict에서 예약번호를 넣어서 어디에 예약 되었는지 (층수, 방번호 리스트)를 a,b로 가져온건데

 

try ~except로 하는 이유는

 

now=checkout이 맞지만 그 예약이 거절된 경우 reserve_dict에 저장이 안되어 있어서 reserve_dict[ind]하면 에러날 수 있어서 그래

 

-------------------------------------------------------------------------------------------------------------

 

마지막 디테일은 사실

 

처음 체크인모드에서

 

for ind,(k,checkin,_) in enumerate(reserves[len(answer):]): 이 부분인데

 

reserves[len(answer):] 이렇게 안하고 그냥 reserves를 하면 사실 문제 되는 부분이

 

이미 체크인모드로 체크인 시키고 나서

 

체크아웃모드로 체크아웃한다음에

 

다시 체크인 모드 들어갈 때 처음에 체크인 모드로 체크인 시킨 예약이 또 한번 체크인 되는 중복과정이 생겨서 그렇다

 

이미 예약을 하면 answer에 1이나 0이 들어가기 때문에 len(answer)부터 시작하면 중복을 제거할 수 있다

 

-------------------------------------------------------------------------------------------------------------

 

 

문제도 기억 안나고

 

코드도 기억 안나는데

 

90%정도로는 복원시킨것 같고

 

기억할만한 기술은 전부 복기한것 같으니까 일단 만족

 

차근차근 구현하면 되는 문제지만 생각할 부분이 많아서 어려운 문제였는데 풀었다는게 대단하다

 

내공이 많이 쌓였다는 뜻이겠지