문제 28, 낮잠 오래 자기, Longest Nap PC/UVa ID : 110404/10191

PC/UVa ID : 110404/10191

이 포스트를 만든 목적

• 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.
  

이 포스트의 준비물

• firefox4 beta11
  
• eclipse 3.6.1 + vrapper
  
• lua 5.1.4

참조 문헌

• 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
  Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 28 낮잠 오래 자기, Longest Nap, page 123)
  

참고 링크

• http://icpcres.ecs.baylor.edu/onlinejudge/external/101/10191.html - 원문
  
• http://cherrykyun.tistory.com/463
  
• http://tausiq.wordpress.com/2009/11/16/acm-uva-10191/ - 알고리즘 구조는 나와 똑같다.
  

이야기

교수가 낮잠 자려고 하는데, 10:00 ~ 18:00 에 스케쥴이 없을 때, 제일 긴 낮잠을 자고 싶어한다. 프로그래머인 당신에게 요구 하고 있다. 자 만들어 보실까?

프로그램의 입/출력

쓰기 귀찮다. 링크 참조 할 것,

맛보기 사진

맛보기 코드
-- PC/UVa : 110404/10191 -- http://ikpil.com -- 2011.02.08 ------------------------------------------------------------------------------- function capture_time(str) -- Minute intergation : 분으로 통합 local bh, bm, eh, em = string.match(str, "(%d+):(%d+) (%d+):(%d+)") return {bh * 60 + bm, eh * 60 + em} end function process_longest_nap(tb_schedule) local tb_capture_time = {} -- sort schedule : 스케줄을 정렬한다. tb_capture_time[#tb_capture_time + 1] = {600, 600} for k,v in pairs(tb_schedule) do tb_capture_time[#tb_capture_time + 1] = capture_time(v) end tb_capture_time[#tb_capture_time + 1] = {1080, 1080} table.sort(tb_capture_time, function (a,b) return a[2] < b[2] end) -- find longest nap time : 긴 낮잠 시간을 찾는다. local longest_nap_time = -1 local start_time = 600 for i = 1, #tb_capture_time - 1 do local nap_time = tb_capture_time[i+1][1] - tb_capture_time[i][2] if longest_nap_time < nap_time then longest_nap_time = nap_time start_time = tb_capture_time[i][2] end end -- result return {start_time, longest_nap_time} end function make_output_format(order, tb_result) local hh, mm = math.floor(tb_result[1] / 60), math.floor(tb_result[1] % 60) local hours = math.floor(tb_result[2] / 60) local minutes = tb_result[2] % 60 local oformat = string.format("Day #%d: the longest nap starts at %d:%02d ", order, hh, mm) if 0 == hours then return oformat .. string.format("and will last for %d minutes.", minutes) else return oformat .. string.format("and will last for %d hours and %d minutes.", hours, minutes) end end function main() local order = 1 while true do -- input schedule count : 스케줄 갯수를 입력 받는다. local schedule_count = io.read("*line") if "" == schedule_count or nil == schedule_count then break end schedule_count = schedule_count + 0 -- input schedule : 스케쥴을 입력 받는다. local tb_schedule = {} while #tb_schedule < schedule_count do local schedule = io.read("*line") if "" == schedule or nil == schedule then else tb_schedule[#tb_schedule + 1] = schedule end end -- find logest nap : 긴 낮잠을 찾는다. local tb_result = process_longest_nap(tb_schedule) local output_format = make_output_format(order, tb_result) order = order + 1 print(output_format) io.flush() end end main() --[[ path = package.path package.path = "C:\\Users\\ikpil\\Desktop\\programming_challenges\\?.lua" package.path = package.path .. ";" .. path require "lunit" test_case = lunit:new() test_case.case1 = "Day #1: the longest nap starts at 15:00 and will last for 30 minutes." test_case.case2 = "Day #2: the longest nap starts at 15:00 and will last for 1 hours and 45 minutes." test_case.case3 = "Day #3: the longest nap starts at 17:15 and will last for 45 minutes." test_case.case4 = "Day #4: the longest nap starts at 13:00 and will last for 5 hours and 0 minutes." function test_case:test_capture_time() local schedule_time = capture_time("10:00 12:00 dasdf") lunit:assert_true(600 == schedule_time[1] and 720 == schedule_time[2]) local schedule_time = capture_time("12:00 13:00 dasdf") lunit:assert_true(720 == schedule_time[1] and 780 == schedule_time[2]) local schedule_time = capture_time("13:00 15:50 dasdf") lunit:assert_true(780 == schedule_time[1] and 950 == schedule_time[2]) end function test_case:test_process_longest_nap1() local tb_schedule = {} tb_schedule[#tb_schedule + 1] = "10:00 12:00 Lectures" tb_schedule[#tb_schedule + 1] = "12:00 13:00 Lunch, like always" tb_schedule[#tb_schedule + 1] = "13:00 15:00 Boring lectures..." tb_schedule[#tb_schedule + 1] = "15:30 17:45 Reading" local tb_result = process_longest_nap(tb_schedule) lunit:assert_true(self.case1 == make_output_format(1, tb_result)) end function test_case:test_process_longest_nap2() local tb_schedule = {} tb_schedule[#tb_schedule + 1] = "10:00 12:00 Lectures" tb_schedule[#tb_schedule + 1] = "12:00 13:00 Lunch, jus lunch" tb_schedule[#tb_schedule + 1] = "13:00 15:00 Lectures, lectures... oh, no!" tb_schedule[#tb_schedule + 1] = "16:45 17:45 Reading (to be or not to be?)" local tb_result = process_longest_nap(tb_schedule) lunit:assert_true(self.case2 == make_output_format(2, tb_result)) end function test_case:test_process_longest_nap3() local tb_schedule = {} tb_schedule[#tb_schedule + 1] = "10:00 12:00 Lectures" tb_schedule[#tb_schedule + 1] = "12:00 13:00 Lunch, jus lunch" tb_schedule[#tb_schedule + 1] = "13:00 15:00 Lectures, lectures... oh, no!" tb_schedule[#tb_schedule + 1] = "15:30 17:15 Reading (to be or not to be?)" local tb_result = process_longest_nap(tb_schedule) lunit:assert_true(self.case3 == make_output_format(3, tb_result)) end function test_case:test_process_longest_nap4() local tb_schedule = {} tb_schedule[#tb_schedule + 1] = "12:00 13:00 I Love lunch! Have you ever?" local tb_result = process_longest_nap(tb_schedule) lunit:assert_true(self.case4 == make_output_format(4, tb_result)) end lunit:run() --]]

여담

• TDD를 이용하니, 코드가 점점 자신있어 진다.
  
  
• 시간이란 개념은 같지만, 단위가 다르므로, 분 단위로 통합하고 계산하는게 편하다.
  
• 알고리즘 중, 10:00 와 18:00 시를 삽입해 주는데, 정렬시 영향을 미치지 않도록, 처음과 끝에 추가 한다.(중요)
  
  
• 딱히 어려운건 없으나, 문자열 파싱, 문자열 결합이 귀찮을 수 있다. lua 에선 string capture 개념이 있어, 좀 편하게 했다.(책에서 찾았다.)

:wq!