문제 22, 파일 조각, File Fragmentation, PC/UVa ID : 110306/10132

PC/UVa ID : 110306/10132

이 포스트를 만든 목적

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

이 포스트의 준비물

• firefox4 b8
  
• eclipse 3.6.1 + vrapper
  
• lua 5.1.4

참조 문헌

• 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
  Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 22, File Fragmentation, page 104)
  

참고 링크

• http://www.lua.org/manual/5.1/manual.html  - 루아 메뉴얼, 스트링 찾을려고
  
• http://online-judge.uva.es/p/v101/10132.html - 원문
  

이야기

연구소에서 컴퓨터 파일이 담긴 쟁반을 들고 가다가 쟁반을 떨구었다. 파일은 모두 조각 났다. 조각난 모든 파일을 주웠다. 파일들을 자세히 보니, 모든 파일은 정확히 두 조각으로 부서졌고, 모든 파일은 같은 파일이였다. 하지만 조각난 지점이 제각기였다. 이 이 파일들은 ASCII 1 과 0 으로 이루어져 있다. 당신에게 이 파일을 복구해달라고 요청해 왔다.

프로그램의 입/출력

1. 프로그램은 첫번째로 테스트 케이스 갯수를 양의 정수로 입력 받는다.
   
2. 1번을 입력 받으면 빈줄로 개행한다.
   
   
3. 2번까지 끝났다면, 한줄에 하나씩 조각난 파일을 입력한다.
   - 이 때, 조각난 파일의 갯수는 짝수여야 한다.
   
   
4. 파일 종료 문자 or 빈 줄이 입력 되면, 조각난 파일을 원상복구 시키고, 이 파일을 출력한다.
   - 만약 원상복구 될 파일이 여러개 일 수 있다면, 이 중 아무거나 출력 한다.
   
   
5. 모든 테스트 케이스가 끝날 때까지 3 ~ 4 번을 반복한다.
   

맛보기 코드
-- file fragmentation -- PC/UVa : 110306/10132 -- http://ikpil.com -- 2011.01.06 function fn_file_fragmentation_defragment(tb_bit, file_len) local tb_candidates = {} for i = 1, #tb_bit do local llen = string.len(tb_bit[i]) for ii = 1, #tb_bit do if i ~= ii then local rlen = string.len(tb_bit[ii]) if file_len == (llen + rlen) then local candidate = tb_bit[i] .. tb_bit[ii] tb_candidates[candidate] = tb_candidates[candidate] or 0 tb_candidates[candidate] = tb_candidates[candidate] + 1 end end end end local max = 0 local candidate for k, v in pairs(tb_candidates) do if max < v then max = v; candidate = k end end return candidate end function fn_file_fragmentation_test_case() local tb_bit, min, max = {}, 256, 0 while true do local bit = io.read("*line") if "" == bit then break end local len = string.len(bit) min, max = min > len and len or min, max < len and len or max tb_bit[#tb_bit + 1] = bit end return fn_file_fragmentation_defragment(tb_bit, min + max) end function main() local case_count = io.read("*line") if "0" == case_count or "" == case_count then return end case_count = case_count + 0 for i = 1, case_count do print(); io.flush() local file_txt = fn_file_fragmentation_test_case() if nil ~= file_txt then print(file_txt) end print(); io.flush() end end main()

맛보기 사진

여담

• 이 문제를 풀 때, 조각난 파일을 합칠수 있는 경우에 대해서 생각하고, 다음의 결론을 내렸다.
  - 파일의 길이는 조각난 파일중 제일 작은 파일 길이, 제일 큰 파일 길이의 합과 같다.
  - 합처진 파일의 갯수는 조각난 파일들 수의 1/2 이다.
  
  
• 위의 경우가 왜 그런지만 안다면, 문제는 무척 쉽게 풀린다.
  
  
• 버그가 있어, 수정해서 다시 코드 올렸다. 그래서 코드와 맛보기 사진이 다르다.
  

:wq