졍's 기술 블로그

모든 순열

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 브루트포스 알고리즘, 백트래킹

문제

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

입력

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

출력

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

예제 입출력

Algorithm

Back Tracking 이용
1. stack이 비어있으면 숫자 바로 append
2. stack이 비어있지 않으면 stack에 포함되어있지 않은 숫자 append
3. 재귀함수 호출
4. 재귀함수 return되면 pop
5. stack의 길이가 N이 되면 stack print

Code

# 입력
data = list(map(int, input().split()))

# 입력 값 Dictionary에 저장 (key: 입력 값, value: 횟수)
dict_ = {}def back_tracking():
    
    # stack의 길이가 N이 되면 print
    if len(stack) == N:
        print(' '.join(list(map(str, stack))))
    else:
        for num in range(1, N+1):
            # stack 비어있으면 바로 추가
            if not stack:
                stack.append(num)
                back_tracking()
                stack.pop()
            # stack이 비어있지 않으면 stack에 없는 숫자만 append
            elif num not in stack:
                stack.append(num)
                back_tracking()
                stack.pop()
                
N = int(input())
stack = []
back_tracking()
for i in data:
    if i not in dict_:
        dict_[i] = 1
    else:
        dict_[i] += 1

flag = False # 같은 숫자가 있는 경우 False, 모두 다른 경우 True
for key, value in dict_.items():
    if value == 3:
        print(10000 + key * 1000)
        flag = False
        break
    elif value == 2:
        print(1000 + key * 100)
        flag = False
        break
    else:
        flag = True

if flag:
    print(max(dict_.keys()) * 100)

메모리: 30864 KB
시간: 216 ms