문자열을 활용한 알고리즘 문제풀이

오늘 푼 문제: 1286. Iterator for Combination

입출력

• 입력: 명령어들이 담긴 문자열 배열과 해당 연산의 인자가 담긴 이차원 배열이 주어집니다.
• 출력: 각 명령어들의 결과값을 배열에 반환합니다.

예제 코드

class CombinationIterator {
    /**
     * 1. 객체 생성 시, DFS로 주어진 combinationLength에 해당하는 조합을 큐에 저장
     * 2. hasNext()의 경우 큐에 남은 조합이 있는지 확인
     * 3. next()의 경우 q.poll()하여 조합에 해당하는 문자를 반환
     */
    int idx;
    int level;
    int length;
    int[] ch;
    String characters;
    Queue<int[]> q;

    public CombinationIterator(String characters, int combinationLength) {
        this.characters = characters;
        this.length = combinationLength;
        this.q = new LinkedList<>();
        this.idx = 0;
        this.ch = new int[combinationLength];
        this.level = 0;
        DFS(0, 0);
        // System.out.println(q.size());
    }
    
    public String next() {
        String result = "";
        int[] comb = q.poll();
        for (int i : comb) result += characters.charAt(i);
        return result;
    }
    
    public boolean hasNext() {
        return !q.isEmpty();
    }

    public void DFS(int L, int D) {
        if (L == length) {
            // System.out.println("ch = " + Arrays.toString(ch.clone()));
            q.offer(ch.clone());
        } else {
            for (int i = D; i < characters.length(); i++) {
                ch[L] = i;
                DFS(L + 1, i + 1);
            }
        }
    }
}

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator obj = new CombinationIterator(characters, combinationLength);
 * String param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

• 모든 문자 조합을 정수배열로 표현하여 큐에 담습니다.
• 문자 조합의 경우 DFS를 활용하여 구하였습니다.
• hasNext의 경우 큐가 비었는지 확인하기 위하여 isEmpty() 매서드를 활용하였습니다.
• next의 경우 큐에서 배열을 가져와 해당 조합에 맞는 문자열을 반환하였습니다.

회고

• 더 나은 방법이 있을거라 100% 확신합니다.
• 그저 내가 바보일뿐.
• 만약 문자열의 길이가 더 길었다면...? 아마도 통과하지 못하였을것이라 생각합니다.
• 슬픕니다....