[코테연습] 1286. Iterator for Combination

 

오늘의 문제는 '문자열' 문제였다.

문자열을 조합한 뒤 함수로 출력하는 문제였는데, 키포인트는 문자열을 조합하는 방식이었다.

나는 DFS 백트래킹으로 푸는 방식이 떠올라 곧장 해당 방식으로 문제를 풀기로 했다.

1. DFS 로 순열 조합을 구현한다.
2. Set 에 중복되는 조합을 삭제한다.
3. List 에 담아 문자열 순으로 정렬한다.
4. Queue 에 담아 hasNext(), next() 함수를 구현한다.

class CombinationIterator {
    private Queue<String> queue = new LinkedList<>();
    private Set<String> set = new HashSet<>();
    public CombinationIterator(String characters, int combinationLength) {
        int x = combinationLength;
        String[] arr = characters.split("");
        boolean[] visited = new boolean[arr.length+1];
        String[] output = new String[x];
        dfs(arr, x, 0, visited, output, 0);
        List<String> list = new ArrayList<>(set);
        Collections.sort(list);
        queue.addAll(list);
    }
    
    public String next() {
        return queue.poll();
    }
    
    public boolean hasNext() {
        return !queue.isEmpty();
    }
    void dfs(String[] arr, int n, int depth, boolean[] visited, String[] output, int start){
        if (depth == n) {
            Arrays.sort(output);
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < output.length; i++) {
                builder.append(output[i]);
            }
            set.add(builder.toString());
            return;
        }

        for(int i = start; i < arr.length; i++) {
            if (!visited[i] ) {
                visited[i] = true;
                output[depth] = arr[i];
                dfs(arr, n, depth+1, visited, output,i+1);
                visited[i] = false;
            }
        }

    }
}