[백준/자바] #6443

방법은 대략 생각났다. python으로 이 문제를 풀었을 때는 sorted word의 각 character가 몇 번 등장하는지를 담은 dictionary 변수를 만들고, 재귀함수로 해당 변수에서 알파벳의 count를 뺐다가 더했다가 하면서 값을 구했던 걸로 기억한다. 

 

그런데 똑같은 방법을 java로 쓰려니 구체적인 구현 방법이 잘 생각나지 않았다. 30분이 지나도 진척이 없어서 다른 풀이를 참고했다. 아쉬운 마음에 풀다 만 코드라도 올려본다. 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Map;

class Main {

    static int N;
    static char[] words;
    static Map<Character, Integer> wordDictionary;
    static BufferedWriter bw;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine().strip());
        for(int i=0; i<N; i++) {
            words = br.readLine().strip().toCharArray();
            makeWordDictionary(words);
            char currentChar = words[0];
            char[] initialCharArray = {words[0]};
            wordDictionary.put(currentChar, wordDictionary.get(currentChar) - 1);
            makeAnagram(initialCharArray);
            wordDictionary.put(currentChar, wordDictionary.get(currentChar) + 1);
        }
        br.close();
        bw.flush();
        bw.close();
    }

    private static void makeWordDictionary(char[] sortedWordArray) {
        wordDictionary = new HashMap<>();
        for(int i=0; i<sortedWordArray.length; i++) {
            char currentChar = sortedWordArray[i];
            if (wordDictionary.containsKey(currentChar)) {
                wordDictionary.put(currentChar, wordDictionary.get(currentChar) + 1);
            } else {
                wordDictionary.put(currentChar, 1);
            }
        }
    }

    private static void makeAnagram(char[] sortedWordArray) throws IOException {
        if(sortedWordArray.length == words.length) {
            bw.write(new String(sortedWordArray) + "\n");
            return;
        }
    }
}

 

여기서 Stack을 사용해보고, 매번 쓰는 BufferedWriter 대신에 StringBuilder도 사용해볼 수 있었다. 새삼 java로 코딩테스트를 많이 안 풀어본지라 생소한 부분이 꽤 있었다.

 

 

다른 풀이를 참고해서, 아래와 같이 코드를 작성해 봤다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

class Main {

    static int N;
    static char[] word;
    static int[] wordDictionary;
    static Set<String> set;
    static Stack<Character> stack;
    static StringBuilder answerSb;
    static int ALPHABET_COUNT = 26;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        answerSb = new StringBuilder();

        N = Integer.parseInt(br.readLine().strip());
        for(int i=0; i<N; i++) {
            set = new TreeSet<>();
            stack = new Stack<>();

            word = br.readLine().toCharArray();

            wordDictionary = new int[ALPHABET_COUNT];
            for(char ch : word) {
                wordDictionary[ch - 'a'] += 1;
            }

            combination();
            set.stream().forEach(s -> answerSb.append(s + "\n"));
        }
        System.out.println(answerSb.toString());
        br.close();
    }

    private static void combination() {
        if (word.length == stack.size()) {
            StringBuilder wordSb = new StringBuilder();
            for(char ch : stack) {
                wordSb.append(ch);
            }
            set.add(wordSb.toString());
            return;
        }

        for(int i=0; i<ALPHABET_COUNT; i++) {
            if(wordDictionary[i] > 0) {
                wordDictionary[i] -= 1;
                stack.push((char) (i + 'a'));
                combination();
                stack.pop();
                wordDictionary[i] += 1;
            }
        }
    }
}