호텔 대실

2024. 6. 10. 16:15· 알고리즘/프로그래머스
728x90
 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

풀이 1

def test(arr):
    new_arr = []
    
    for i in range(2):
        time = arr[i]
        hour, minute = time.split(":")
        new_time = int(hour) * 60 + int(minute)
        
        # 대실 종료시각의 경우 청소시간을 포함해서 10분을 추가
        if i == 1:
            new_time += 10
        
        # 대실 종료시각이 23:50 이상이라면, 청소시간을 포함해서 23:59로 바꿔버림
        if i == 1 and new_time >= 1350:
            new_time = 1359
        
        new_arr.append(new_time)
        
    return new_arr


def solution(book_time):
    answer = 0
    
    # 대실 시작시간, 대실 종료시간을 분으로 저장
    # 대실 종료시간에는 청소시간 10분을 추가해서 저장
    book_minute = list(map(test, book_time))
    
    book_minute.sort(key=lambda x: x[0]) # 대실시작시간 기준으로 정렬
    n = len(book_minute)
    
    for i in range(n):
        current = book_minute[i] # 현재 확인할 손님
        temp = 1 # 현재 확인할 손님이 입실했을 때, 필요한 방의 수(최소 1개)
        # 0 ~ i-1번째 손님이 현재 방에 있는지 확인
        for j in range(i):
            # 만약 현재 입실할 손님의 입실 시간이 지금 입실 중인 손님의 퇴실 시간 이전이라면
            if current[0] < book_minute[j][1]:
                temp += 1 # 방을 1개 더 추가
        
        # 방의 최댓값을 갱신
        answer = max(temp, answer)
        
        
    return answer

 

내가 생각해낸 풀이

이 풀이는 이중반복문을 돈다.

그래서 답은 맞추지만 시간 복잡도가 별로임

 


풀이 2

def test(arr):
    new_arr = []
    
    for i in range(2):
        time = arr[i]
        hour, minute = time.split(":")
        new_time = int(hour) * 60 + int(minute)
        
        # 대실 종료시각의 경우 청소시간을 포함해서 10분을 추가
        if i == 1:
            new_time += 10
        
        # 대실 종료시각이 23:50 이상이라면, 청소시간을 포함해서 23:59로 바꿔버림
        if i == 1 and new_time >= 1350:
            new_time = 1359
        
        new_arr.append(new_time)
        
    return new_arr


def solution(book_time):
    answer = 0
    
    # 대실 시작시간, 대실 종료시간을 분으로 저장
    # 대실 종료시간에는 청소시간 10분을 추가해서 저장
    book_minute = list(map(test, book_time))
    
    # 시작, 종료 대실 시간에 따른 방 수를 저장하는 리스트
    check_time = [0 for _ in range(60 * 24 + 10)]
    
    # 대실 시작시간의 경우 + 1, 대실 종료시간의 경우 - 1
    for start, end in book_minute:
        check_time[start] += 1
        check_time[end] -= 1
        
    # 현재 필요한 방 개수
    room_cnt = 0
    
    # 00:00 ~ 23:59까지 반복문을 돈다.
    # 반복문을 돌면서 입실하는 경우 + 1, 퇴실하는 경우 -1을 통해 해당 시간에 필요한 방 수를 저장, 갱신
    for i in range(len(check_time)):
        room_cnt += check_time[i]
        check_time[i] = room_cnt
    
    # check_time의 최댓값이 필요한 최소 객실 수
    answer = max(check_time)
    
    return answer

 

구글링을 통해 시간복잡도를 개선한 풀이

반복문을 한 번만 돌고도 풀 수 있다.

 

핵심 로직은 각 입실시간, 퇴실 시간에서 입실 시간은 +1, 퇴실 시간은 -1을 해줌으로써 특정 시간의 방 수를 갱신, 저장한다는 것이다. 

728x90

'알고리즘 > 프로그래머스' 카테고리의 다른 글

숫자 카드 나누기  (1) 2024.06.14
메뉴 리뉴얼  (0) 2024.06.13
전력망을 둘로 나누기  (1) 2024.06.06
연속된 부분 수열의 합  (1) 2024.06.06
124 나라의 숫자  (0) 2024.05.20
'알고리즘/프로그래머스' 카테고리의 다른 글
  • 숫자 카드 나누기
  • 메뉴 리뉴얼
  • 전력망을 둘로 나누기
  • 연속된 부분 수열의 합
happenundo
happenundo
happenundo
2023~ 개발블로그
happenundo
전체
오늘
어제
  • 분류 전체보기 (207)
    • TIL (3)
    • 알고리즘 (188)
      • 프로그래머스 (47)
      • 백준 (69)
      • 파이썬 문법 (11)
      • 이것이 코딩테스트다 (46)
      • 알고리즘 노트 (6)
      • SQL (8)
    • Spring (4)
      • Spring 입문 (2)
      • 개인 프로젝트 (1)
      • 인텔리제이 (1)
    • CS (8)
      • DB (2)
      • 네트워크 (1)
      • 그외 (5)
    • ~2022 (1)
    • etc (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 다이나믹프로그래밍
  • 이진탐색
  • 정렬
  • 재귀
  • 괄호변환
  • BinarySearch
  • DP
  • 이코테
  • 동적프로그래밍
  • 플로이드워셜
  • 백준
  • 완전탐색
  • CS
  • dfs
  • 그리디
  • 백트래킹
  • 프로그래머스
  • 우선순위큐
  • 큐
  • 구현
  • 파이썬
  • sql
  • 스택
  • 최단거리
  • BFS
  • 알고리즘
  • deepcopy
  • 다익스트라
  • 이것이코딩테스트다
  • distinct

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
happenundo
호텔 대실
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.