fhskf94kr   2년 전

일반 버블소트를 사용하면 시간초과가 발생하여 

mergeSort를 사용하여 알고리즘을 구현했습니다.

mergeSort는 절반으로 나누는 작업을, sort는 정렬하는 부분을 구현한 것입니다.

여러가지 테스트 케이스를 확인해 보고, 정렬되는 과정 밑 swap 함수를 체크하는것 까지 확인해 봤는데 

잘못된 부분을 알 수 없었습니다.

자료형 문제인가 싶어서 확인해 보았는데,

첫째 줄에 N(1≤N≤500,000)이 주어진다. 

A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다.

이 두가지 범위를 봐서는 int형 범위도 벗어나지 않고, 혹시나 싶어서 배열도 long타입으로 선언하여 사용해 보았지만 똑같이 틀리네요.

+- 1,000,000,000의 범위는 모두 int 형 타입으로 사용 가능하고, N은 배열의 크기이기 때문에 상관 없을 것으로 생각됩니다.

배열에 저장된 값을 사용하여 연산하는 작업은 하나도 없고, +- 연산이 되는거는 배열의 index 부분이기 때문에 자료형 문제는 아니라고 생각하고 있습니다.

어느 부분이 틀렸는지 도움이 필요합니다.

rhs0266   2년 전

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

fhskf94kr   2년 전

@rhs0266

답변 감사합니다.

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

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

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

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


fhskf94kr   2년 전

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

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

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

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


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

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

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

rhs0266   2년 전

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

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

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

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

fhskf94kr   2년 전

@rhs0266

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

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

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

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

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

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

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