책너두 (코딩 인터뷰 완전분석) 47일차 (17.16, 17.19)

17. 어려운 연습문제

17.16 마사지사

• 인기 있는 마사지사가 있다. 마사지 사이에 15분간 휴식이 필요하므로 마사지 예약이 연달아 들어온다면 그중에서 어떤 예약을 받을지 선택해야 한다. 연달아 들어온 마사지 예약 리스트가 주어졌을 때(모든 예약 시간은 15분의 배수이며 서로 겹치지는 않고 한번 예약이 되면 변경이 불가능하다), 총 예약 시간이 가장 긴 최적의 마사지 예약 순서를 찾으라.

17.19 빠진 숫자 찾기

• 1부터 N까지 숫자 중에서 하나를 뺸 나머지가 정확히 한 번씩 등장하는 배열이 있다. 빠진 숫자를 O(N) 시간과 O(1) 공간에 찾을 수 있겠는가? 만약 숫자 두 개가 빠져 있다면 어떻게 찾겠는가?