알고리즘 / 자료구조’ 시리즈

[백준] 10972번 - 다음 순열

  • 0
  • 0
0
0

1. 다음 순열

A. 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

위 프로그래머스 사이트에 접속하여 문제를 확인해주세요.

B. 내 답안

a. 1차 시도 (실패)

못풀었다...

b. 2차 시도

n = int(input())  
array = list(map(int, input().split()))  
  
k = -1  
  
for i in range(len(array)-1):  
    if array[i] < array[i+1]:  
        k = i  
  
if k == -1:  
    print(-1)  
else:  
    m = 0  
    for j in range(i+1, len(array)):  
        if array[k] < array[j]:  
            m = j  
  
    array[k], array[m] = array[m], array[k]  
  
    temp = array[k+1:]  
    temp.sort()  
    array = array[:k+1] + temp[:]  
  
    print(array)
    
a. 회고

반성

  • permutation 모듈을 썻다가 메모리 초과가 발생했다.
  • 사전 순열이 발생하는 패턴을 알고 있으면, 공간복잡도와 시간복잡도의 제약에 걸리지 않고 풀 수 있던 문제였다.

결론

  • 몇번씩 반복해서 다시 도전해보자.

C. 문제 해설

이해한 내용을 바탕으로 작성했습니다.

참고문헌

10972번: 다음 순열 (acmicpc.net). Baekjoon. (accessed Sep 10, 2021)

BANANA, [백준10972번] 다음 순열 / Python3 (tistory.com), tistory, (accessed Sep 10, 2021)

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.