99클럽 코테 스터디 27일차 TIL, 문자열(Iterator for Combination)

1. 문제 정의

2. 문제 접근

문자열을 이용하라고 되어있지만 나는 dfs를 이용했다.

3. 문제 풀이

1. 모든 구할 수 있는 문자열의 경우를 구한다.
2. 메서드에 맞게 구현해준다.

4. 코드

class CombinationIterator {
    List<String> strList;
    int idx = 0;

    public CombinationIterator(String characters, int combinationLength) {
        strList = new ArrayList<>();
        int n = characters.length();
        
        dfs(0, characters,new StringBuilder(),combinationLength);
        // Collections.sort(strList);
    }
    
    public String next() {
        if(idx < strList.size()){
            return strList.get(idx++);
        }
        return "";
    }
    
    public boolean hasNext() {
        return idx == strList.size() ? false : true;
    }

    private void dfs(int start, String characters, StringBuilder sb, int l){
        if(sb.length() == l){
            // System.out.println(sb);
            strList.add(sb.toString());
            return;
        }
        for(int i = start; i < characters.length(); i++){
            char ch = characters.charAt(i);
            sb.append(String.valueOf(ch));
            dfs(i+1, characters, sb, l);
            sb.deleteCharAt(sb.length()-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();
 */

 

 

5. 회고

문제를 보자마자 백준의 N 과 M 시리즈가 생각이 났다. 겹치지 않으면서 모든 문자열을 구하는 건 dfs를 이용하면 쉽게 구할 수 있었다. 

 sorted distinct 이라는 조건을 인식을 못해서 list에 문자열을 모두 담아 준 뒤 다시 정렬을 한번 더 해주다가 마지막에 깨닫고 빼주었다. 이렇게 메서드를 같이 구현하는 문제들이 더 뭔가 문제를 더 풀맛이? 난다.