순열(백준 알고리즘 10973번)

♣ 순열(permutation)

순열은 서로 다른 n개의 대상에서 r개를 뽑아 일렬로 배열한 것을 말한다. 이때 나올 수 있는 경우의 수를 수학식으로 아래와 같이 표현한다. 이때 배열의 순서를 고려해야 한다. 순서가 다르면 서로 다른 순열이다. 

만약 [1, 2, 3, 4]  중 3개를 뽑아 배열하는 경우의 수를 구한다면 아래와 같다. 

 

이와 같이 여러 수의 순서를 고려하여 배열하는 '순열'을 파이썬 코드로 만들 수 있다. 

 

♣ 백준 알고리즘 문제 이해

 

 

 

1부터 N까지의 수로 이루어진 순열이 있고, 입력에서 주어진 특정한 수열의 바로 전 순열을 출력한다. 

예를 들어 1부터 5까지의 수가 있고, 특정한 순열 5 4 3 2 1 의 바로 앞에 있는 순열은 5 4 3 1 2 이다. 

 

 

♣ 문제풀이 방법1(순열 정의하기)

첫 번째로는 파이썬으로 순열을 정의한 후 주어진 입력으로 만들 수 있는 모든 순열을 구하려고 했다. 

파이썬으로 구현한 순열 코드는 아래와 같다. 

 

 

입력 1 2 3 4 를 n에 넣어 순열을 만드는 데 사용할 숫자들을 리스트로 만든다. 

입력 3을 r에 넣는다. 즉 1 2 3 4 중 3개의 수만 뽑아서 모든 순열을 구하는 것이다. 

 

밑에 permutation(n, r, [ ]) 에서 빈 리스트는 순열을 만들기 위해 선택된 숫자들을 넣는 리스트이다. 

permutation 함수에는 chosen으로 들어간다. 첫 번째 if문을 보면 chosen 의 길이가 r 이면 chosen을 출력하며 if문이 종료된다. 즉 순열에 들어갈 숫자를 모두 다 뽑으면 return 되는 것이다. 

 

for문을 보면 n 리스트에 있는 숫자들을 하나씩 뽑기 시작하는데, 뽑은 수를 표시하기 위해 used를 이용한다. 뽑힌 수를 chosen에 추가하고, used[i] = 1로 바꾸어서 같은 숫자를 중복해서 뽑지 않도록 하는 것이다. 

 

재귀를 이용하여 permutation 함수를 또 불러내면 앞에서 뽑은 chosen을 가지고 있는 채로 다음 숫자를 뽑게 된다. 이때 used[i] == 1인 수는 더 이상 뽑지 않는다. 

 

이렇게 숫자를 뽑아서 3개의 수를 모두 뽑고 나면, used[i] 를 다시 0으로 바꾼다. 새로운 순열을 만들어야 하기 때문이다. 그리고 chosen의 끝 수부터 pop을 이용하여 하나씩 지우고, 이 자리를 채울 숫자를 다시 뽑는다. 

 

코드가 실행되면서 used와 chosen은 아래와 같이 바뀐다. 

 

그런데 이 문제에서는 모든 순열을 구하는 것이 아니라 주어진 특정 순열의 바로 앞 순열을 출력하는 것이므로 코드에 다음과 같은 내용을 추가했다. 

 

per이라는 빈 리스트를 만들어 여기에 만들어진 순열들을 하나씩 집어넣는다. 그리고 완성된 순열이 주어진 특정 순열과 같아졌을 때, per의 길이가 1이면 -1을 출력한다. per가 1이라는 것은 주어진 순열이 첫 번째 순열이기 때문에 그 전 순열이 존재하지 않는다는 것이다. 

 

이와 달리 per의 길이가 1보다 크면 주어진 특정 순열의 전 순열을 출력해야 하므로 per[-2]를 출력한다. 

그런데 이 코드를 제출하자 시간초과가 발생하였다. 

 

 

♣ 문제풀이 방법2(숫자의 순서 바꾸기)

질문게시판을 보니, 순열을 코드로 구현하여 답을 구하지 않고, 주어진 특정 순열 안에서 수의 순서를 바꾸어 바로 앞의 순열을 구하였다. 재귀함수 때문에 시간초과가 나왔다고 판단하여 순열을 구현하지 않고, 주어진 순열에서 숫자를 바꾸는 코드를 만들어보기로 했다. 

 

 

1부터 4까지의 수가 주어지고, 특정 순열이 3 4 1 2이라고 해보자. 이 순열의 바로 앞 순열을 어떻게 구할 수 있을까? 

3 4 1 2 보다 하나 덜 내림차순인 순열이 되어야 하므로 맨 뒤에서부터 숫자를 비교하며 수가 작아지도록 해야 한다. 

 

3 4 1 2 의 끝 수부터 비교하다 보면 앞의 수가 뒤의 수보다 큰 경우가 있다. 여기서 보면 앞에 있는 수 4가 1보다 크다. 3 4 1 2 순열의 앞 순열은 이보다 덜 내림차순일 것이므로 현재 4의 위치에 4보다 작은 수가 와야 한다. 이렇게 앞의 수가 뒤의 수보다 큰 위치를 찾는다. 여기서 4는 index =1이다. 

 

이렇게 찾은 index =1 위치의 4와 3 4 1 2 의 맨 끝 수부터 비교를 시작한다. 현재 맨 끝 수는 2이다. 2가 4보다 작으므로 2와 4의 위치를 바꾼다. 그러면 3 2 1 4 가 된다. 3 2 1 4 는 3 4 1 2 보다 앞에 위치하는 순열이다. 하지만 이게 정답은 아니다. 3 4 1 2 바로 앞의 순열은 3 2 4 1 이기 때문이다. 즉, 해당 index의 숫자와 이 숫자보다 작은 수의 위치를 바꾼 후에는 그 뒤의 숫자들은 내림차순으로 만들어주어야 한다. 

 

따라서 answer[:targ+1] 에다가 reverse=True로 하여 내림차순으로 정렬한 뒷부분 answer[targ+1:] 을 붙이면 이전 순열을 구할 수 있다. 

 

 

순열을 구현하고 나서 당연히 맞을 거라고 생각했는데 시간초과의 함정이 있었다. 수학개념을 구현하는 것도 좋지만 효율성을 높일 수 있는 방향을 찾아보는 것이 중요하다는 것을 느꼈다. 

 

♣ 참고 자료

-순열과 조합:https://shoark7.github.io/programming/algorithm/Permutations-and-Combinations

조합과 순열 알고리즘, 파이썬으로 구현하기