[백준 2024/02/21] 14534번 String Permutation

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

14534번: String Permutation

 

1. 접근 방법

이 문제는 DFS 로 풀면 간단할 것 같다는 생각이 들었다.

그래서 각 문자열을 받고, DFS 함수로 넘겨주었다.

def DFS(route, chars):
    if not chars:
        result.append(route)
        return
    for i in range(len(chars)):
        DFS(route + chars[i], chars[:i] + chars[i+1:])

 

route는 생성되는 문자열들을 저장하기 위한 장소이며, chars는 route에 들어간 문자들을 제외한 문자를 넣어주는 곳이다.

또한 result라는 list를 선언하여, 더 이상 chars에 남아있는 문자열이 없게 되면, result에 저장해 주었다.

이후 result가 빌 때까지 pop(0)를 해주었다.

 

이에 대한 더 자세한 설명과 유사한 문제는 아래에 있다.

https://potatoscatteringsmile.tistory.com/116

[leetcode 2024/02/15] 46. Permutations

 

해당 문제에서 아래와 같이 출력을 해주어야 하는 경우가 있었다.

Case # 1:

 

아래와 같이 코드를 작성하였다.

print('Case # {}:'.format(i+1))

.format(~~~) 는 앞의 프린트 대상에서 {} 안에 값을 넣어주는 녀석이다.

 

2. 코드

def DFS(route, chars):
    if not chars:
        result.append(route)
        return
    for i in range(len(chars)):
        DFS(route + chars[i], chars[:i] + chars[i+1:])

def print_result():
    while result:
        print(result.pop(0))

if __name__ == '__main__':
    result = []

    for i in range(int(input())):
        print('Case # {}:'.format(i+1))
        DFS('',input())
        print_result()