자… 이제 마지막 문제입니다.
앞서 세 문제를 생각보다 쉽게(?) 풀어주신 덕에, 이번 문제는 『코딩 인터뷰 완전 분석』의 ‘고난이도 연습문제’에서 선택했습니다.
하지만, 공성을 위해 달려가는 오크 워리어처럼 열정 넘치게 달려들어주시길 기대하겠습니다. ^^
(아… 아이폰 출시에 묻히면 안 되는데… ㅠㅠ)
유의사항
1. 풀이과정이나 해답 등은 각자 블로그에 올리신 후, 트랙백 혹은 댓글로 알려주세요.
트랙백 주소 : http://www.insightbook.co.kr/post/3917/trackback
(트랙백은 조금 시간이 걸린 후 등록됩니다.)
2. 블로그 글 제목을 다음처럼 작성해주세요.
‘코딩 인터뷰 완전 분석 215쪽 문제 18.10 풀이’
3. (선택사항 : 글에 『코딩 인터뷰 완전 분석』 표지를 넣어주시면 감사하겠습니다. ㅎㅎ)
4. 이번 문제는 1주일간(9월 18일 화요일 자정까지) 응모받습니다.
문제
『코딩 인터뷰 완전 분석』215쪽 고난이도 연습문제 18.10
사전에 등장하고 길이가 같은 두 단어가 주어졌을 때, 한 번에 글자 하나만 바꾸어 한 단어를 다른 단어로 변환하는 프로그램을 작성하라. 변환 과정에서 만들어지는 각 단어도 사전에 있는 단어여야 한다.
[실행 예]
input : DAMP, LIKE
output: DAMP -> LAMP -> LIMP -> LIME -> LIKE
[사전 데이터]
네 글자 단어 – word4
다섯 글자 단어 – word5
[심화 문제 – 풀지 않아도 됩니다]
심화문제 1: 가장 적은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다.심화문제 2: 최대한 많은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다. 단, 변환 과정에서 같은 단어가 두 번 나오면 안됩니다.
상품
3주간 진행될 『문제로 풀어보는 알고리즘』『구글러가 전하는 IT 취업 가이드』『코딩 인터뷰 완전 분석』 발간 기념 문제 풀이 이벤트에 참여해 정답을 올리신 분 중,
한 분께는 HP 프로라이언트 마이크로서버를,
다섯 분께는 요즘 가장 핫! 한 아이템 중 하나인 Raspberry Pi를 각 하나씩 선물로 드립니다.
(Raspberry PI를 생각보다 빨리 구했습니다. 현재 출판사 사무실에서 두근거리는 마음으로 주인이 결정되기를 기다리고 있답니다. ㅎㅎ)
오…저는 3문제정도 더 남았는 줄 알았는데, 마지막이라는 왠지(?) 아쉽네요.
앞서 문제는 수정전 글을 보고 많이(?) 고생했기에 이번에는 궁금하거는 충분히 물어보고 싶네요. 그래서 아래와 같이 적어봅니다.
1. 반드시 한글자씩 변경하는 메소드를 만들어야 하나요? ( output처럼 만들기 위해서는 한글자씩 변경하는 메소드가 필요없을 수도 있을 것 같거든요… )
2. 혹여 사전에 존재하지 않는 단어가 발생했을 경우 없다고 메세지로 보여주면 되나요? 아니면 거너뛰고 두글자 이상 변경한 사전에 존재하는 단어를 보여주면 되나요? ( 예 LIME, LIKP가 존재하지 않을때 )
DAMP -> LAMP -> LIMP -> (X) -> LIKE
3. 당연하겠지만, input단어는 반드시 사전에 있는단어만 진행하면 돼죠?
아이폰에 관심은 많지만, 휴대폰 약정의 끝이 안보이는 관계로..무관심 -_-;
좋아요좋아요
저도 아쉽지만 날이 갈수록 채점의 어려움과 도전하시는 언어의 다양성 덕에, 이쯤에서 그만할까 합니다. ㅎㅎ
답변 드립니다.
1. 변경하는 과정 중에는 반드시 한글자씩 변경해야 합니다. 프로그램 내에서 함수나 자료구조는 마음대로 사용하셔도 되고요~
2. 변경 과정 중 사전에 단어가 존재하지 않는다면, LIMP에서 LIKE로 넘어갈 방법이 없는 셈이니 ‘IMPOSSIBLE’을 출력하시면 되겠습니다.
(혹은 DAMP -> LAMP -> LIMP -> IMPOSSIBLE)
3. input 단어와 output 단어가 사전에 없으면 ‘IMPOSSIBLE’을 출력하세요.
(아이폰에 관심이 없으시다니 다행(?)입니다. 저는 약정이 곧 끝나지만, 예산 절감차 눈을 감고… ㅎㅎ)
좋아요좋아요
그리고 심화문제에 보면, 단어수가 있는데…. 한번에 한글자씩 바꾸기 때문에, 길이가 4이면 4번, 5이면 5번아닌가요? 예제 혹은 부연 설명 부탁드립니다.
좋아요좋아요
네.
네 글자 단어장을 사용했을 때 가장 적은 수의 단어는, 첫 단어와 끝 단어를 포함해서 5개가 될 겁니다. 다섯 글자 단어장을 사용하면 6개가 되겠고요. ^^
가장 많은 수는… 단어장에서 있는 대로 다 찾아야겠죠? ㅎㅎ
좋아요좋아요
제가 착각했네요~ 네 글자 단어는 최소 4단계, 다섯 단어는 최소 5단계입니다. ^^
좋아요좋아요
다음과 같이 단계를 더 늘릴수 있을 것 같습니다.
DAMP – LAMP – LIMP – LIME – DIME – DIVE – LIVE – LIKE
좋아요좋아요
T_T… 이번에는 문제보다 질문이 더 많을 것 같네요.
DAMP – LAMP – LIMP – LIME – DIME – DIVE – LIVE – LIKE
5번째 단어가 “DIME”가 될 수 있는 건가요? 이미 LI?E까지 찾았는데 다시 회귀?
그리고 DIVE에서 “V”는 두 단어 중 어디도 포함되지 않았는데 나올수 있는건가요?
좋아요좋아요
최소는 DAMP -> LAMP -> LIMP -> LIME -> LIKE 어느정도 이해가 되는데, 최대도 예제를 좀 부탁드립니다.
혹은 이번에는 앞 문제처럼 검증예제 같은건 없나요 -_-;; 테스트자료 찾기가 더 힘드네요 ^^;;
좋아요좋아요
http://www.ummae.com/blog/2012/코딩-인터뷰-완전-분석-215쪽-문제-18-10-풀이
좋아요좋아요
http://daejin.blogspot.kr/2012/09/215-1810.html
일단 초판~, 문제의 궁금증이 해결되는대로 AS할예정입니다.
밀린 업무처리하러 GoGo…
좋아요좋아요
http://daejin.blogspot.kr/2012/09/215-1810.html
AS해서 올려놓았습니다.
좋아요좋아요
수동 트랙백
http://www.ummae.com/blog/2012/코딩-인터뷰-완전-분석-215쪽-문제-18-10-풀이
좋아요좋아요
앗.. 이전 것이 승인 대기 였군요.. 확인 되면 하나 삭제 부탁드릴께요~
좋아요좋아요
http://ps-go-lang.tumblr.com/post/31393359726/215-18-10
좋아요좋아요
음, 심화 2는 NP-complete이라는 것 같은데… 풀릴까요? ~_~a
좋아요좋아요
제가 잘못해석한건지 모르겠는데요~
‘모든 문자를 한번씩은 반드시 수정해야 한다’고 봐야하나요?
아니면,
input: DAMP, LAMP
이렇게 될때 output은 ‘DAMP -> LAMP’ 이렇게 되는건가요?
저는 전자로 이해하고 있습니다만 ^^;
좋아요좋아요
case1: 변환도중 정답을 찾으면 성공!!(꼭 단어길이만큼 안가봐도 됨)
ex)damp ramp
damp -> ramp
case2: 몇번째 문자를 변경해도 관계없으나(중복가능) 반드시 단어길이만큼 수정되야 성공!!
ex)damp ramp
damp -> gamp -> lamp -> samp -> ramp
case3: 모든 문자를 한번씩은 변환해야 성공!!
ex) damp like
damp -> lamp -> limp -> lime -> like
좋아요좋아요
이번은 정말 문제해석이 어렵죠 T_T
어떤 분은 거리(?)를 계산하고 푸시는 것 같고….심화문제에 최대한 많은 단어 예제만 들어주셔도 좀 이해가 될듯한데…
제가 이해한 내용은 아래와 같습니다.
1234 -> ABCD
(1,A), (2,B), (3,C), (4,D) 이 중에 하나를 선택해서 사전에 있는 단어를 찾고 찾았다면, ABCD가 될 때까지 계속 반복, 그런데 없다면 IMPOSSIBLE
코딩인터뷰 책이 없는데, 거기에 먼가 있을까요 ㅎㅎ
좋아요좋아요
@xgate 님
input: DAMP, LAMP 일 때는
DAMP -> LAMP가 맞습니다.
모든 문자를 한 번씩 변환할 필요도 없겠네요.
(제가 네 글자 단어는 네 번 변환된다고 잘못 이야기해서리… 오해를 일으켰습니다. ㅡ,.ㅡ)
@석대진 님
책의 문제 페이지에도 별 내용은 없답니다~ ^^a
좋아요좋아요
수동 트랙백입니다.
http://unzury.blogspot.kr/2012/09/215-1810.html
좋아요좋아요
많은 분들이 문제 해석에 어려움을 토로하셔서 출력 예시를 보여드립니다.
(1) 사전이 {aa, ab, ac, cc}이고, 입력이 aa -> cc일 때는 두 가지 방법이 있습니다. 둘다 맞는 방법입니다. 둘 중에 아무거나 출력해도 됩니다.
aa-ab-ac-cc
aa-ac-cc
(단, 심화문제 1에 대해서는 두 번째가 정답이고, 심화문제 2에 대해서는 첫 번째가 정답입니다.)
(2) 사전이 {aa, ab, bc, cc}이고, 입력이 aa-cc일 때 방법없음.
‘impossible’ 출력
(3) 사전이 {aa, ab, bb, bc, cc, dd}이고, 입력이 aa -> cc일 때 aa-ab-bb-bc-cc가 유일한 답입니다. 방법이 있기 때문에 ‘impossible’ 출력하면 안 됩니다.
좋아요좋아요
제가 ‘제대로’ 오해하고 있었군요 ㅜㅜ 다시 풀어야겠네요 ㅋㅋㅋ
알겠습니다. 감사합니다 🙂
좋아요좋아요
https://gist.github.com/3722184#file_p2_2.md 문제 풀이입니다.
좋아요좋아요
https://gist.github.com/3722184 문제 풀이.
좋아요좋아요
아직 늦지 않았습니다. ^^
좋아요좋아요
http://dlimpid.wordpress.com/2012/09/18/%ec%bd%94%eb%94%a9-%ec%9d%b8%ed%84%b0%eb%b7%b0-%ec%99%84%ec%a0%84-%eb%b6%84%ec%84%9d-215%ec%aa%bd-%eb%ac%b8%ec%a0%9c-18-10-%ed%92%80%ec%9d%b4/
좋아요좋아요
노파심에 수동트랙백~
http://blog.benelog.net/2965284
좋아요좋아요