백준 알고리즘 10974번 (모든 순열)

모든 순열 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

8000

4458

3291

56.839%

문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다. 

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

 

예제입력	예제출력
3	1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

 

[ 문제풀이 ]

 

 

[ 문제설명 ]

배열 변수는 총 3개가 필요합니다. 

1. input 받은 N값의 정수 개수가 포함된 배열 - input[]

2. 1번의 배열의 값을  추출하여 저장할 배열 - array[]

3. 2번의 추출과정 중 1번에 접근유무를 체크할 배열 (boolean type) - access[]

 

위의 3가지 배열 변수와 몇번째 index을 참조할지 정하는 depth 변수 그리고 input받은 N의 값 변수를 재귀함수로 전달하여 처리하면 됩니다.

재귀함수는 아래와 같은 방법으로 동작을 합니다.

1. n > depth 가 맞으면 로직이 수행되고 그렇지않으면 input받은 N값 많큼 셋팅이 완료 된 것이기에 출력

2. 1번의 조건이 참일 경우 for문을 N만큼 수행시킨다.

3. for문 안에 접근유무 확인하는 access[] 배열을 통해 접근유무 체크하여 접근을 안했을때 array[depth]배열에 input[i]의 값을 넣는다

   -> array[depth] 인덱스로 설정하는것이 중요하다. 

   -> 재귀함수로 동작을 하기에 for문이 겹겹이 수행된다. 이때 depth를 통해 기준index를 고정시킨 후 for문을 수행하여 순차적으로 값을 증가시켜 경우의 수를 만들기 위해서 이다.

4. 다시 재귀메서드를 호출시키고 이때 depth를 1 증가시켜 array[]배열에 다음 index를 바라보게 한다.

5. 재귀메서드 수행이 n > depth 까지 수행완료되면 call stack 영역에서 하나씩 제거가되며  그 후에 access[] 배열에 true로 설정한 값을 false로 초기화 시킨다.

   -> false로 초기화 시켜야 다음 수행 시 접근을 할 수 있다.

 

 

알고리즘 문제풀이 소스는 깃헙에 모을예정입니다. (필요하시다면 fork 하셔도 괜찮습니다.)

GitHub -> https://github.com/sksggg123/algorithm

sksggg123/algorithm