godqhrals   1년 전

안녕하세요. 2750번 문제를 합병정렬을 이용해서 구현했는데, 채점을 진행하면 99%까지 갔다가 "틀렸습니다."로 나옵니다. 
질문게시판의 반례들을 모두 넣어봤을 때는 정상적으로 잘 출력되지만 채점 때 틀린 것으로 나오는데, 어디가 문제인지 정확히 잘 모르겠어서 힌트를 여쭤보고자 올렸습니다! 

알려주시면 감사하겠습니다. 좋은 하루 되세요:)

yup0927   1년 전

N = 1일 때 동작하지 않습니다,

merge_sort(arr, sorted, 0, 0)이 호출되는데 left < right이 false라서 sorted에 아무 작업을 하지 않고 함수가 반환됩니다.

godqhrals   1년 전

N = 1일 때는 간과하고 있었는데 알려주셔서 감사합니다!

말씀해주신 점을 참고해서 merge_sort 함수 안에 아래 소스 코드의 3,4번째 코드를 추가해보았는데, 혹시 이렇게 직접 sorted[0] = arr[0]이라고 대입해줘도 괜찮을까요?

직접 N=1일 경우를 다뤄주고 난 후에는 정답으로 나오긴 했는데, 

제가 혹시 대충 해결한건가 싶어서 더 좋은 방법이 있을지 궁금합니다. 알려주시면 감사하겠습니다!

yup0927   1년 전

left == right가 N = 1일 때만 발생하지는 않습니다,

사실은 모든 N에 대해서 분할하면서 내려가면 발생할 수밖에 없는 케이스입니다.

N > 1인 경우에는 병합이 이루어지면서 정렬이 이루어지기에 sorted에 대입해주는 것 자체는 별 의미가 없는 구문이라고 할 수 있겠습니다.

조금 더 깔끔하게 짜고 싶으시다면 N > 1일 때만 merge_sort를 호출해주시거나 (N = 1이면 정렬 자체가 필요 없음),

sorted 배열 관리 자체를 merge 과정에서만 하고, merge가 끝난 이후 arr에 다시 대입해주는 방법 등이 있을 것 같습니다.

godqhrals   1년 전

자세히 알려주셔서 정말 감사합니다! 덕분에 잘 이해되었고 많이 배워갑니다! 

말씀해주신 방법 토대로 수정해보겠습니다!

좋은 하루 되시길 바랍니다!:)

yup0927   1년 전

적고 나니 살짝 빠뜨린 내용이 있어 남깁니다.

좀 전 글에 적은 N > 1일 때만 호출하라는 말의 의도는 N = 1일 때 sorted[0] = arr[0]을 하고 그렇지 않을 때 merge_sort를 호출하면 된다는 뜻이었습니다.

sorted의 관리에 관한 얘기는 merge에서만 sorted 배열을 관리하고 반환 전에 arr에 그 내용을 복사해 준 다음 출력 자체를 arr로 하라는 의미였습니다. 이 경우에는 N = 1 일 때 별도 처리가 필요없습니다.

둘 중 하나만 하시더라도 정상 동작 할 겁니다.

godqhrals   1년 전

네! 덕분에 잘 해결했습니다. 정말 감사합니다!

댓글을 작성하려면 로그인해야 합니다.