백준/ Silver 3 문제 , 백준 파이썬 10972 , 다음 순열

백준/ Silver 3 문제 , 백준 파이썬 10972 , 다음 순열

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

진짜...머리 싸매면서 푼 문제이다. 예시는 잘되는데 왜 런타임에러가 나는지 씩씩거리면서 풀었다. 처음에 백트래킹으로 풀었는데 예시는 잘 출력되었지만, N이 10000 까지 커지는 탓에 생각보다 시간복잡도가 커서 계속 틀렸다. 그래서 숫자 뒷자리부터 확인해가며 풀었다. 이 과정에서 시행착오를 겪었음. 그래도 결국 혼자 풀어냈다...!! 

 

<문제 출처>

 

https://www.acmicpc.net/problem/10972

10972번: 다음 순열

------------------------------------------------------------------------------------------------------------------------------

 

 

런타임에러

 

처음에 푼 방식인데, 예제는 잘 출력되지만, 코드를 돌려보면 런타임 에러가 난다.

 

 

 

 

 

 

이후, 내가 푼 아이디어는 처음에 입력받은 숫자들이 모두 내림차순인지 확인한다.

 

모두 내림차순일 경우 끝값이므로 -1을 그대로 출력하고 종료하면된다. 

 

끝 값이 아닌걸 확인한 후에는 입력받은 숫자 뒷자리부터 확인해준다. 이때 뒤에서 두번째 자리부터 확인해주면 된다.

 

두번째 자리 부터 확인하므로

 

여기서 봐야할 것은 어디까지가 내림차순인지를 확인하면된다.

 

 

 

cut 과 cut_check 변수를 통해 내림차순이 아닌 곳을 확인해준다.

 

 

 

 

예를 들어  5 3 4 2 1 을 입력 받았다고 가정했을때, 4 2 1 까지는 내림차순

 

이후 앞 3을포함하면 3 4 2 1은 내림차순이 아니다.

 

여기서 이제 나눠줘야 한다.

 

 

 

 

3을 우선 tmp 변수에 저장해두고

 

3을 기준으로 왼쪽 5는 따로  front 변수에 저장해준다.

 

 

현재 

tmp = 3

front = 5

 

 

 

이후 back 변수에 front 에 담긴 5를 제외한 값들을 정렬하여 할당한다.

 

여기서 왜 정렬을 했냐면, 이 back에는 현재 3 4 2 1 이 담겨있다.

 

여기서 한번 예상해보자. 3 4 2 1 다음 수열은 뭐가 나와야할까?

 

바로 4 1 2 3 이 나올 것이다.

 

이유는 3 4 2 1 이 앞자리가 3 인 수열의 마지막 값이기때문에 이제 앞을 4로 바꿔줘야하기 때문.

 

 

이때 순서를 4 1 2 3 으로 바꾸기 위해 3보다 큰 숫자인 4의 인덱스를 찾아내기 쉽게 하기위해서 정렬을 해준거다.

 

1 2 3 4 로 정렬하면 tmp에 저장한 3 의 값의 인덱스보다 1 커지게 하면되기때문.

 

(물론 인덱스를 찾는 더 좋은 방법이 있을 것이다. 내가 이번에 푼 방법은 이런 방식으로 풀었음.)

 

이후 3보다 큰값의 인덱스를 가지고 center라는 변수에 4를 할당한다. 

 

이후 back 에서 4를 지워준다.

 

여기까지

 

front = 5

center = 4

back = 1 2 3

 

의 값들이 할당 되어있다.

 

 

5 4 1 2 3

 

이 값은 우리가 입력한 값의 다음 수열이다.

 

그러므로 이 값들을 다 더해줘서 출력해주면 답이 나오게 된다.

 

 

이런 방식으로 접근하면 풀리는 문제이다.

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답