35. Special Sort(구글 인터뷰)

it 취업을 위한 알고리즘문제풀이(with C/C++) : 코딩테스트 대비

문제

코드1

코드2

문제해결과정1

• 입력받은 배열에서 조건문으로 음수체크 후 새로운 배열에 입력 다음 체크를 위해 음수가 나온 인덱스 값 다음 인덱스 저장
• 음수가 나온 다음 값부터 다시 음수 체크 새로운 배열에 입력
• 위 정을 반복함
• 입력받은 배열에서 조건문으로 양수체크 후 새로운 배열에 입력 다음 체크를 위해 양수가 나온 인덱스 값 다음 인덱스 저장
• 양수가 나온 다음 값부터 다시 음수 체크 후 새로운 배열에 입력
• 위 정을 반복함

위 과정은 선택정렬처럼 멀리떨어진 값들을 선택해서 순서에 맞게 바꾸기 때문에 문제의 원하는 순서와 뒤바뀔 가능성이 많다. 이 오류를 해결하기 위해 새로운 배열을 하나 더 생성해서 문제를 해결했다. 그러나 새로운 메모리 공간을 확보해야하는 메모리 낭비의 문제가 발생한다. 기존의 정렬을 유지하면서 문제 조건에 맞는 정렬을 해야할 경우 바로 옆에 위치한 값과 비교해서 값들을 정렬하는 버블정렬 알고리즘을 사용하는 것이 옳다.

문제해결과정2

• 버블정렬 알고리즘을 이용해 좌측 값이 양수이고 우측 값이 음수이면 교환