[baekjoon] 백준 6443번(파이썬): 애너그램

문제

9081번: 단어 맞추기

알고리즘

- 이전에 비슷한 문제를 풀어서 조합 라이브러리를 통해 푸는 것은 아니라고 판단했다. (시간 복잡도 펑!)

- 단어를 하나하나 확인하면서 백 트래킹을 통해 문제를 수행했다.

- visited에 각 알파벳의 개수를 입력하고 그 알파벳들을 사용하면서 백 트래킹을 통해 모든 단어를 만든다.

- 문제를 입력받을 때 정렬하여 받았기 때문에 자동적으로 알파벳을 사용하여 단어를 만들 때 정렬된 단어가 완성된다.

코드

import sys


def back_tracking(cnt):

    # 현재 문자 길이가 입력된 문자 길이와 같다면 출력
    if cnt == len(word):
        print("".join(answer))
        return

    # 반복문을 통해 visited에 단어를 확인
    for k in visited:
        if visited[k]:
            visited[k] -= 1 # k를 사용할 것으로 -1
            answer.append(k) # answer에 더해준다.
            back_tracking(cnt + 1) # 백트래킹
            visited[k] += 1 # k를 사용안한 것으로 +1
            answer.pop() # answer에서 빼준다.


n = int(sys.stdin.readline())

for _ in range(n):
    word = sorted(list(map(str, sys.stdin.readline().strip())))
    visited = {}
    answer = []

    # 반복문을 통해 visited에 알파벳의 개수를 입력
    for i in word:
        if i in visited:
            visited[i] += 1
        else:
            visited[i] = 1

    # 백트래킹
    back_tracking(0)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법