citizen   1년 전

arr의 제일 뒤에서 한단계 전 부분부터 시작해서

해당 위치 뒤쪽에 있는 숫자중 현재자리값보다 작은 값을 가진 자리가 있으면

두 개의 값을 바꿔준뒤 현재 자리 뒤쪽부터 내림차순으로 정렬을 시켰습니다.

글로는 어려우니 예시를 들자면

5 3 4 1 2 5 라는 배열이 있을 때

제일 뒤쪽에서부터 시작하여 자기보다 뒤에 있는 수가 

자신보다 작은 경우가 최초로 발견되는 경우는 4입니다.(1, 2, 5는 그렇지 않으니까요)

특히 작은 숫자들 중에서도 제일 뒤쪽에 위치한 수는 '2'이므로

2와 4를 서로 바꾸어 5 3 2 1 4 5 라는 배열을 만들고

4가 발견된 자리가 index상으로는 2번이니 3번자리부터 끝부붙까지만 내림차순으로 정렬하면

5 3 2 5 4 1이 됩니다.


이 방법을 역으로 이용하여 10972번인 '다음수열' 문제는 해결했는데요.

이 문제는 잘 넘어가질 않더군요..

어디가 문제일까요?

zlzmsrhak   1년 전

반례입니다. 분석해보세요.

citizen   1년 전

단순 알고리즘 오류였더군요

제가 설명해놓고 그대로 소스를 짜지 않았다니..

아무튼 도움주신 덕분에 해결됬습니다.

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