정답의 최대치가 얼마인 지 확인해보세요.

@rhs0266

답변 감사합니다.

정답의 최대치 문제인 것 같아서 int가 아닌 long타입으로 선언해도 똑같이 틀렸다고 나오네요.

혹시나 싶어서 배열부터 index 값을 제외한 모든 변수와 배열을 long 타입으로 선언하여 사용해봐도 똑같습니다..

애초에 정답 최대치에 대한 문제라고 하면 정답의 타입을 long 으로만 바꿔준다면 되는 문제라고 생각하는데, 그렇지가 않은것 같네요.

정답을 저장하는 변수 swap의 경우 맨 처음 변수 선언 후에 sort에서 ++ 연산밖에 하지 않고 그대로 출력하는 것이라..

변수 swap을 제외하고는 int 타입 자체를 넘어서지 않는게 아닌가 생각됩니다.

Main 함수에서는 int형 범위 이내의 값들을 입력 받기만 하며,

mergeSort 에서는 배열의 범위(1~50만)의 값을 가지고 있는 N을 사용하여 연산 후 대입을 하고,

sort 에서는 값 비교 후 배열의 범위에 해당하는 변수들과 결과 값 swap만 증감 연산을 하는 것이니 말이죠..

자료형에 대한 문제라면 swap 변수를 제외하고 발생하지 않아야 하는게 아닌가? 하고 생각이 들며,

swap 자료형을 long으로 선언함에도 불구하고 문제가 발생하는거는 어딘가 알고리즘에 오류가 있지 않을까?

라는게 현재 제 생각이고 어디가 틀렸나 찾아보고 있는데 아무리 봐도 찾을 수가 없네요..ㅠ

풀이를 알고 구현하신 점은 맞지만, swap을 현재처럼 swap++ 로 하는게 맞는지 생각해보세요.

swap을 증가시킨 이유는 오른쪽 값이 더 작기 때문인데, 이때 이 값을 insert[]에 삽입함으로써 필요한 swap 횟수는 tmp1에 남아있는 원소의 갯수가 될 것입니다. 즉, 1만큼 증가시키는게 아니라 tmp1.length-index1만큼 증가시켜야합니다.

추가적인 개선으로는 mergesort 함수 안에서 매번 tmp1, tmp2를 new를 통해 생성하는데, new 연산자는 생성자로써 메모리 관련 이슈가 있습니다. 굉장히 오랜 시간을 소요하게 될텐데, 전역변수로 바꿔서 적당한 사이즈(n이상)로 정적 선언을 해놓으신다면 해결 가능합니다.

이해가 안되는 부분이 계시다면 물어보시고 정확히 이해하는 게 좋을 것 같습니다 ㅎㅎ

@rhs0266

엄청 늦게 확인했습니다만, 정확한 조언 감사합니다.

어떠한 형식으로 풀어야하는지는 알고있기 때문에 그 부분에서 오류가 날것이라고는 생각을 못했네요.

어중간하게 알고 구현하고 그것을 믿고 있던것이 문제였던것 같습니다.

조언해주신 대로 swap 변수의 증가하는 부분을 수정해주니 무사히 통과가 되었습니다.

무엇보다, '정확히 이해하는 것'이 중요하다는 것을 다시 깨닫게 된 문제였습니다.

좋은 조언 및 질책 감사합니다 :)