99클럽 코테 스터디 24일차 TIL - DFS

오늘의 학습 키워드

DFS
Combination

---

알고리즘 문제

LeetCode Medium 1286. Iterator for Combination

---

공부한 내용

오늘은 스스로 생각한 DFS를 활용해서 처음부터 끝까지 혼자힘으로 풀었다. 너무 기분이 좋다!

---

오늘의 회고

처음 시도

• 주어진 문자열의 한 문자씩 모두 탐색해서 원하는 길이의 문자열을 만드는(조합하는) 문제였기 때문에 DFS로 문자열의 0번 인덱스부터 마지막 인덱스까지 순서대로 조합을 찾는 방법을 생각했다.
  • 문제에서 이미 오름차순으로 정렬된 문자열이 주어지기 때문에 앞에서부터 순서대로 자신의 이후 인덱스부터 차례로 조합하면서 모든 조합을 찾을 수 있다.
• DFS로 생각했고, 큐(Queue) 자료구조를 사용해 조합한 문자열을 큐에 넣고, 오름차순으로 정렬되서 이미 큐에 들어가기 때문에 그대로 앞에서부터 꺼내면 된다.
• 그 다음으로 재귀 종료 조건을 생각해야 하는데 반복하면서 문자열에 1씩 증가하는 인덱스의 값을 더할때마다 카운팅을 하면서 원하는 문자열 길이만큼 조합을 만들고, 원하는 문자열 길이만큼 카운팅이 되었을 때 return하도록 생각했다.

해결

• DFS 알고리즘과 Queue 자료구조로 해결했다!

---

문제 풀이

import java.util.*;

class CombinationIterator {
    private String characters;
    private int len;
    private Queue<String> queue;

    public CombinationIterator(String characters, int combinationLength) {
        this.characters = characters; 
        this.len = combinationLength;
        this.queue = new LinkedList<>();
        for (int i = 0; i < characters.length(); i++) {
            dfs(characters.substring(i,i+1), i, 1);
        }
    }
    
    public void dfs(String str, int index, int count) {
        if (count == len) {
            queue.offer(str);
            return;
        }

        for (int i = index+1; i < characters.length(); i++) {
            dfs(str+characters.substring(i,i+1), i, count+1);
        }
    }

    public String next() {
        return queue.poll();
    }
    
    public boolean hasNext() {
        return !queue.isEmpty();
    }
}

/**
 * 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();
 */