이번 주 문제 나갑니다~

이벤트가 진행될수록 문제가 조금 까다로워지니,

잘 읽고 답해주세요~ ^^

(1주차 1번 문제의 해설은 제일 밑에 첨부하였습니다.

해설에는 저자이신 김용혁 교수님께서 수고해주셨답니다. ^^)

유의사항

1. 풀이과정이나 해답 등은 각자 블로그에 올리신 후, 트랙백 혹은 댓글로 알려주세요.

트랙백 주소 : http://www.insightbook.co.kr/post/3876/trackback

(트랙백은 조금 시간이 걸린 후 등록됩니다.)

2. 블로그 글 제목을 다음처럼 작성해주세요.

‘코딩 인터뷰 완전 분석 210쪽 17.3 변형 문제 풀이’

3. (선택사항 : 글에 『코딩 인터뷰 완전 분석』 표지를 넣어주시면 감사하겠습니다. ㅎㅎ)

코딩인터뷰-표지1-204x300

4. 각 문제별 응모 기한은 다음 문제가 올라오기 전까지이며, 마지막 문제는 1주일간 응모받습니다.

문제

『코딩 인터뷰 완전 분석』210쪽 17.3 변형 문제

자연수 n을 입력받고, n!의 계산 결과 중 마지막에 붙은 연속된 0의 개수와 연속된 0 바로 앞에 나오는 숫자를 구하라.

[실행 예]

input n: 15

output: 3 8

[설명]

15!은 1307674368000이므로, 마지막에 연속된 0은 3개이고, 바로 앞의 숫자는 8이다.

* 조건 *

  1. n의 범위는 1 이상, 10000 이하입니다.
  2. 테스트 입력은 다음과 같습니다.20! = 243290200817664000030! = 26525285981219105863630848000000040! = 81591528324789773434561126959611589427200000000050! = 30414093201713378043612608166064768844377641568960512000000000000

    100! = 93326215443944152681699238856266700490715968264381621468592963

    8952175999932299156089414639761565182862536979208272237582511852

    10916864000000000000000000000000

  3. 프로그래밍 언어에서 제공하는 자릿수 제한 없는 곱셈을 이용하거나, 이런 형태의 곱셈 함수를 직접 구현해도 답을 얻을 수 있지만, 문제의 의도와는 다릅니다.
  4.  정답 검토의 편의를 위해 블로그 포스팅에 2012!와 10000!의 결과를 남겨주세요.
  5. (심화 문제) 연속된 0 앞에 나오는 여러 숫자를 구하는 것도 가능하니, 심심하신 분은 도전해보세요. ^^

상품

3주간 진행될 『문제로 풀어보는 알고리즘』『구글러가 전하는 IT 취업 가이드』『코딩 인터뷰 완전 분석』 발간 기념 문제 풀이 이벤트에 참여해 정답을 올리신 분 중,

한 분께는 HP 프로라이언트 마이크로서버를,

다섯 분께는 요즘 가장 핫! 한 아이템 중 하나인 Raspberry Pi를 각 하나씩 선물로 드립니다.

(Raspberry PI는 구입하려는 사람이 많아 공급이 수요를 따라가지 못하고 있다니 저희가 주문해 입수하는 대로 보내드릴 겁니다.)

1주차 1번 문제 해설과 모범 답안 추천

총평 : 확실히 잘못 짠 정답은 하나 밖에 보이지 않을 정도로, 다들 코드를 잘 작성해 주셨습니다.

마감 시한까지 트랙백을 25개나 걸어주셨고, 프로그래밍 언어도 델파이, 루아, 자바, c/c++, 루비, 파이썬, 펄, 커피스크립트, go 등 매우 다양했습니다.

책에서는 해답을 C로 작성했기 때문에 회전 대상과 크기가 같은 임시 배열을 하나 잡아서 배열을 복사하면 됩니다. 대부분 이렇게 잘 풀어주셨습니다.

파이썬은 역시나 강력해서, 배열 중간을 잘라서 그냥 붙이면 됩니다.

문제에서 요구한 것은 아니지만, n과 k에 상관없이 항상 상수 크기의 메모리를 쓰는 방법으로 푸신 분들도 있습니다.

원래 배열이 크지 않거나 메모리가 부족하지 않은 대부분의 경우에는 별 상관없기 때문에, 이런 걸 따지는 것이 좀 옛스럽긴 합니다만…

재미있으니까 한번 생각해보시는 것도 좋습니다.

여기서는 두 가지 방법을 소개합니다.

첫 번째는 배열을 두 번 뒤집는 것입니다.

123456을 오른쪽으로 두 칸 회전시키는 것은 1234와 56을 바꾸는 것과 같습니다.

두 개의 sequence(문자열, 배열 등)를 바꿀 때 많이 쓰는, 각 부분을 뒤집은 다음 전체를 뒤집는 트릭을 여기에도 적용할 수 있습니다.

123456에서 reverse(1~4), reverse(5~6), reverse(전체)를 하는 것입니다.

이렇게 하면 배열이 123456 > 432156 > 432165 > 561234의 순서로 바뀝니다.

아래 두 포스팅을 참고하십시오.

Sunghwan 님

Abraham 님

두 번째 방법은 배열을 휘젓고 다니면서, 원소를 하나씩 적절한 위치로 옮겨주는 방법입니다.

생각하는 프로그래밍』에서는 이 방법을 ‘저글링(juggling)’이라고 부릅니다.

다음 두 분이 이렇게 풀어주셨습니다.

(이 방법으로 짜면 코드가 좀 읽기 어렵게 되는 것 같긴 합니다.)

Jin Kim 님

xgate 님

같은 원소가 두 번 옮겨지는 것을 방지하기 위해서는 고민을 좀 해야하는데, 두 분 모두 문제가 생기지 않게 잘 처리해주신 것 같습니다.

이렇게 메모리를 아끼면서 배열을 회전하는 주제에 대해서 『생각하는 프로그래밍』 컬럼2에 잘 정리되어 있습니다.

모두 수고하셨습니다. ^^