[C++] BOJ 6443번 : 애너그램

 

 

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

 

문제 3줄 요약

1. 씬디는 애너그램 프로그램을 만들어 줄 수 있는 남자가 좋다.

2. 애너그램은 입력받은 문자열의 단어들을 재배치한 단어들을 출력하는 것이다.

3. 재배치한 문자열의 중복은 제외하고 알파벳 순서로 출력해라.

 

---

 

예시를 보면 바로 이해가 가능하다.

 

(입력) abc → (애너그램) → (출력) abc acb bac bca cab cba

 

abc가 입력으로 주어지면

a 1개, b 1개, c 1개로 만들 수 있는 문자열들을 출력하면 된다.

 

출력할 때

알파벳 순서대로 출력해야하니 위와 같이 순서로 출력된다.

 

문자열의 최대 길이가 21이라고

문제에 조건으로 주어졌다.

 

따라서 완전 탐색은 불가능하기에

조합 함수를 사용하거나

백트래킹을 통한 탐색이 필요하겠다.

 

필자는 백트래킹을 사용하여 문제를 풀었다.

 

---

 

백트래킹은

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

을 의미한다.

 

쉽게 생각하면 재귀 함수에 들어가고 나오며

우리가 만들고자 했던 문자열을 만든다고 생각하면 된다.

 

string s;
bool visited[21];

void anagram(string word){
    if(word.length() == s.length())
    {
        cout << word << "\n";
        return;
    }

    for(int i=0; i<s.length(); i++)
    {
        if(!visited[i])
        {
            visited[i]=true;
            anagram(word+s[i]);
            visited[i]=false;
        }
    }
}

 

생각했던 내용을 c++ 코드로 작성하면 위와 같을 것이다.

 

anagram이라는 함수에 word 문자열을 인자로 넘겨주되

우리는 한글자씩 추가를 하여 넘겨줄 것이다.

 

추가할 글자는

문자열 s에 글자를 사용하되 한번씩만 사용해야하니

visited를 통해 사용 표시를 해두고

사용했던 글자는 제외할 것이다.

 

하지만 이렇게만 작성하면

문제가 발생한다..

 

aaba → aabc, aacb, ..... , cbaa, cbaa

 

 

바로 중복 문자열이 출력되는 것인데

위의 예시와 같이

들어갔던 재귀 함수 한번에서 같은 글자 a가 중복으로 사용되어 cbaa가 중복하여 출력된다.

 

따라서 우린 같은 재귀 함수내에서

같은 알파벳을 중복으로 사용하지 않게 체크해줘야한다.

 

완성된 코드는 아래와 같이 작성할 수 있다.

---

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string s;
bool visited[21];

void anagram(string word){
    if(word.length() == s.length())
    {
        cout << word << "\n";
        return;
    }

    char last_char = ' ';

    for(int i=0; i<s.length(); i++)
    {
        if(!visited[i] && s[i] != last_char)
        {
            visited[i]=true;
            last_char = s[i];
            anagram(word+s[i]);
            visited[i]=false;
        }
    }

}

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

    int n;
    cin >> n;

    while(n--)
    {
        cin >> s;
        sort(s.begin(), s.end());
        fill(visited, visited+21, false);
        anagram("");
    }
    return 0;
}

 

중복된 문자열 출력에서 어려움이 있었다.

set를 통해 중복을 제거하니 시간 초과가 발생했다.

 

같은 재귀 함수 내에서 같은 알파벳을 사용하면 안된다는 조건...

잘 고려하도록 해야겠다.

 

끝!