[BOJ] 6443 - 애너그램

gmelan·2022년 5월 21일
0

알고리즘 트레이닝

목록 보기
7/14

풀어보기

접근

  1. 입력된 단어 W의 철자들만을 조합하여 만들 수 있는 모든 단어를 사전순으로, 중복 없이 출력하여야 한다.
  2. W의 각 철자들은 중복될 수 있다.

얼핏 보기엔 N과 M 문제와 비슷해 보이지만, 주어지는 입력의 각 요소가 서로 중복될 수 있다는 점이 가장 큰 차이라고 할 수 있다.

지금껏 풀어왔던 모든 조합을 사전순으로 출력하거나 추가적인 규칙이 붙는 문제와 큰 차이는 없을 것이라 판단하여, 일단 입력에 중복되는 철자가 없는 경우만을 대응하는 코드를 짜 보았다.

코드 1 - 중복되는 철자가 없는 경우만을 대응하는 프로그램

from sys import stdin

def search(string):
    global visited, alphabets

    if len(string) == len(alphabets):
        print(string)
        return
    
    for i in range(len(alphabets)):
        if not visited[i]:
            visited[i] = True
            search(string + alphabets[i])
            visited[i] = False

alphabets = list(stdin.readline().rstrip())
alphabets.sort()

visited = [False for _ in range(len(alphabets))]

search("")

이 코드는 중복되는 철자가 없는 입력에는 잘 대응한다. 입력을 사전순으로 정렬하고, 모든 조합을 첫 번째 문자부터 재귀적으로 탐색한다. 예를 들어 입력이 "abc"인 경우

search("")
    ↳ search("a")
        ↳ search("ab")
            ↳ search("abc") -> abc
        ↳ search("ac")
            ↳ search("acb") -> acb

    ↳ search("b")
        ↳ search("ba")
            ↳ search("bac") -> bac
        ↳ search("bc")
            ↳ search("bca") -> bca

    ↳ search("c")
        ↳ search("ca")
            ↳ search("cab") -> cab
        ↳ search("cb")
            ↳ search("cba") -> cba

이상과 같은 과정을 통해 답을 산출한다.

이 프로그램에 "aab"와 같은 중복되는 철자가 있는 입력을 넣은 경우 어떻게 동작하는지를 보자. 가독성을 위해 첫 번째 a를 a1으로, 두 번째 a를 a2로 표기하겠다.

search("")
    ↳ search("a1")
        ↳ search("a1a2")
            ↳ search("a1a2b") -> a1a2b
        ↳ search("a1b")
            ↳ search("a1ba2") -> a1ba2

    ↳ search("a2")
        ↳ search("a2a1")
            ↳ search("a2a1b") -> a2a1b
        ↳ search("a2b")
            ↳ search("a2ba1") -> a2ba1

    ↳ search("b")
        ↳ search("ba1")
            ↳ search("ba1a") -> ba1a2
        ↳ search("ba2")
            ↳ search("ba2a1") -> ba2a1

볼드 처리된 부분이 이미 출력되었던 문자열이 또 출력되는 경우인데, 이 부분을 살펴보면 바로 직전 호출과 같은 매개변수 문자열이 들어갔음을 발견할 수 있다. 따라서 나는 직전 호출과 같은 문자열이 매개변수로 들어오는 경우를 걸러냄으로써 중복을 제거하는 방법을 고안하였다.

코드 2 - 중복되는 철자가 있는 경우도 대응하는 프로그램

from sys import stdin

def search(last_str, string):
    global s, visited

    if len(string) == len(s):
        print(string)
        return

    for i in range(len(s)):
        candidate = string + s[i]

        if not visited[i] and candidate != last_str:
            visited[i] = True
            search(string, candidate)
            visited[i] = False
            last_str = candidate

n = int(stdin.readline())

while n:
    s = list(stdin.readline().rstrip())
    s.sort()
    visited = [False for _ in range(len(s))]
    search("", "")

    n -= 1

코드 1과 다른 점은 매개변수로 이전 호출때의 문자열last_str도 넘겨주고, 이를 현재 매개변수 문자열 string과 비교하는 절차가 추가된 것이다.

여기까지 한 뒤 다른 사람들은 어떻게 풀었는지 찾아보았고, 이 풀이법보다 훨씬 간단하고 직관적인 방법을 발견하였다...

정렬 및 중복 여부와 관계없이, 각 철자의 출현 횟수만을 세어 그 만큼을 기존과 같은 방법으로 조합하여 출력하면 훨씬 간결하게 정답을 구할 수 있는 것이다.

코드 3

from sys import stdin

ALPHABET_LEN = 26

def search(string):
    global alpha

    if len(string) == len_s:
            print("".join(string))
            return

    for i in range(ALPHABET_LEN):
        if alpha[i] != 0:
            alpha[i] -= 1
            search(string + [chr(i + ord('a'))])
            alpha[i] += 1

n = int(stdin.readline())

while n:
    len_s = 0
    alpha = [0 for _ in range(ALPHABET_LEN)]

    for i in stdin.readline().rstrip():
        alpha[ord(i) - ord('a')] += 1
        len_s += 1

    search([])
    n -= 1

문자열 비교 등의 고비용 연산이 빠졌지만 결국 똑같이 모든 경우를 탐색하는 코드이다보니, 주어진 범위에서의 코드 2와의 소요 시간 차이는 크지 않았다. 하지만 그것에 비해 훨씬 직관적이고 간결한 코드라고 생각된다.

0개의 댓글