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)

참고 링크

이야기

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

프로그램의 입/출력

  1. 프로그램은 첫번째로 테스트 케이스 갯수를 양의 정수로 입력 받는다.
  2. 1번을 입력 받으면 빈줄로 개행한다.

  3. 2번까지 끝났다면, 한줄에 하나씩 조각난 파일을 입력한다.
    - 이 때, 조각난 파일의 갯수는 짝수여야 한다.

  4. 파일 종료 문자 or 빈 줄이 입력 되면, 조각난 파일을 원상복구 시키고, 이 파일을 출력한다.
    - 만약 원상복구 될 파일이 여러개 일 수 있다면, 이 중 아무거나 출력 한다.

  5. 모든 테스트 케이스가 끝날 때까지 3 ~ 4 번을 반복한다.

맛보기 코드

맛보기 사진

여담

  • 이 문제를 풀 때, 조각난 파일을 합칠수 있는 경우에 대해서 생각하고, 다음의 결론을 내렸다.
    - 파일의 길이는 조각난 파일중 제일 작은 파일 길이, 제일 큰 파일 길이의 합과 같다.
    - 합처진 파일의 갯수는 조각난 파일들 수의 1/2 이다.

  • 위의 경우가 왜 그런지만 안다면, 문제는 무척 쉽게 풀린다.

  • 버그가 있어, 수정해서 다시 코드 올렸다. 그래서 코드와 맛보기 사진이 다르다.

:wq

posted by 농사를 짓는 게임 프로그래머 최익필

댓글을 달아 주세요

  1. Favicon of https://www.ikpil.com 농사를 짓는 게임 프로그래머 최익필 2011.01.08 17:21 신고  Addr  Edit/Del  Reply

    23번 문제 풀려고 했더니, 막혔네.
    깔끔한게 안보인다. :) 잠시 쉬었다가 다시 봐야지.