[백준] 6443 애너그램

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

단어의 글자들의 위치를 바꿔서 나오는 단어를 구해야 하므로 순열을 사용하였습니다.

중복되는 결과를 막기 위해서 집합을 사용하였습니다.

 

초기에 단어를 정렬하여 알파벳순으로 정렬하도록 했습니다.

또한,  시간을 줄이기 위해 집합으로 각 자릿수로 사용한 단어를 계속해서 추가했습니다.

2) 알고리즘

• 순열
• 백트래킹

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

def solution(n, ans):
    if n <= 0:
        print(''.join(ans))
        return
    
    for i in range(M):
        if not selected[i]:                         # 사용하지 않은 단어 리스트
            tmp = ans + [word[i]]                   # 뒤에 사용하지 않은 단어 추가
            if tuple(tmp) not in used:              # 사용한 단어에 포함되지 않으면
                used.add(tuple(tmp))                # 사용한 단어 추가
                selected[i] = 1
                solution(n-1, ans + [word[i]])      # 다음 글자 확인
                selected[i] = 0


N = int(sys.stdin.readline())                           # 단어의 개수

for _ in range(N):
    word = sorted(list(sys.stdin.readline().strip()))   # 입력된 단어를 정렬하여 리스트로 만듦
    used = set()                                      # 중복을 피하기 위한 집합 생성

    M = len(word)               # 단어의 길이
    selected = [0] * M          # 특정 단어 사용 여부 확인을 위한 리스트

    solution(M, [])

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

초기에 시간 초과를 고려하지 못하고 일반적으로 순열을 구하는 방식을 사용하였고, 그 방법을 해결하기 위해 시간이 꽤 소요되었습니다.

2) 새롭게 학습한 내용

- 특별히 없습니다.

---

🔗 문제 링크

- https://www.acmicpc.net/problem/6443

6443번: 애너그램

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다