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

오늘의 과제

리트코드 medium으로 분류된 Iterator for Combination 입니다.

 

이번 유형은 문자열 입니다.

문제

https://leetcode.com/problems/iterator-for-combination/description/

 

 

먼저 문제 요구사항 요약입니다.

 

소문자로 정렬된 알파벳 문자열과 조합해야 할 길이가 주어질 때 가능한 모든 조합을 생성하고, 이 조합을 순차적으로 반환하거나 다음 값의 여부를 반환하는 메서드를 작성해야 합니다.

 

풀이 방법은 최대한 간단히 하기위해 조합 가능한 문자열을 미리 만들어 리스트에 넣어두고 next와 hasNext는 리스트의 값을 이용하는 방식으로 진행하겠습니다.

 

먼저 초기화입니다. 조합 가능한 문자열을 담을 리스트와 next, hasNext에 사용할 인덱스를 전역 변수로 선언합니다.

leetCode에서는 매 TC 실행마다 독립 실행이 아니기 때문에 진입점에서 반드시 초기화를 진행해줘야 다음 TC에 영향이 가지 않습니다.

private List<String> combinations;
private int idx;

public CombinationIterator(String characters, int combinationLength) {
    // leetCode는 초기화가 없으면 에러발생
    combinations = new ArrayList<>();
    idx = 0;

    generateCombinations(characters, combinationLength, 0, new StringBuilder());
}

 

 

조합 가능한 문자열을 리스트에 담는 메서드입니다. DFS를 활용하였으며 입력으로 주어진 조합 가능한 최대 길이를 이전 탐색에서의 Level로 사용했습니다. 즉, DFS의 탈출 조건은 쌓인 문자열이 입력으로 주어진 제한 길이입니다. 매개 변수는 조합해야할 characters, 조합 제한 길이인 combinationLength, 몇 번째 문자를 조합에 써야하는지를 나타내는 start, 마지막으로 조합되고 있는 path 입니다.

private void generateCombinations(String characters, int combinationLength, int start, StringBuilder path) {
    if (path.length() == combinationLength) {
        combinations.add(path.toString());
        return;
    }

    for (int i = start; i < characters.length(); i++) {
        path.append(characters.charAt(i));
        generateCombinations(characters, combinationLength, i + 1, path);
        path.deleteCharAt(path.length() - 1);
    }
}

 

 

사실 미리 조합에서 리스트에 담았다면 문제 풀이는 끝났다고 봐도 무방합니다. 나머지는 리스트 내 값을 이용하여 결과만 반환하도록 해주면 됩니다. next()의 경우 idx 번째 인덱스에 있는 조합된 문자열을 주면 되고 호출 될 때 마다 후위 연산으로 idx는 커지고 있으니 리스트의 사이즈보다 커졌다면 이미 모두 반환했다는 뜻이 되니 사이즈만 비교해주면 됩니다.

public String next() {
    return combinations.get(idx++);
}

public boolean hasNext() {
    return idx < combinations.size();
}

 

 

코드입니다.

import java.util.*;

class CombinationIterator {

    private List<String> combinations;
    private int idx;

    public CombinationIterator(String characters, int combinationLength) {
        // leetCode는 초기화가 없으면 에러발생
        combinations = new ArrayList<>();
        idx = 0;

        generateCombinations(characters, combinationLength, 0, new StringBuilder());
    }

    private void generateCombinations(String characters, int combinationLength, int start, StringBuilder path) {
        if (path.length() == combinationLength) {
            combinations.add(path.toString());
            return;
        }

        for (int i = start; i < characters.length(); i++) {
            path.append(characters.charAt(i));
            generateCombinations(characters, combinationLength, i + 1, path);
            path.deleteCharAt(path.length() - 1);
        }
    }
    
    public String next() {
        return combinations.get(idx++);
    }

    public boolean hasNext() {
        return idx < combinations.size();
    }
}

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

 

 

배운 점

백트래킹을 떠올리지 못하고 한참 헤매다 리트코드 자체에서 제공하는 힌트에 "전처리로 생성합니다" 덕분에 의미 있는 접근을 할 수 있었습니다. 다만 2번 힌트인 비트 마스킹을 사용하십시오 라는 문구로 인해 첫 접근은 비트 마스킹으로 진행했습니다. 

 

문자열이 "abc"라고 가정했을 때 0부터 가능한 비트 마스크의 최대 길이인 2^n까지 반복하면서 Integer.bitCount를 이용해 비트의 개수가 입력으로 주어진 조합 가능한 최대 길이가 되면 유효한 조합으로 판단하고 리스트에 추가했고 비트 마스크를 이용했기 때문에 뒤죽박죽 된 리스트에 추가 된 문자열들을 정렬해주기 위해 Collections.sort를 사용했습니다.

 

작성하면서도 코드에 비트 마스크 개념을 입히는 작업이 너무 머리가 아팠고 시간복잡도 또한 하위권으로 나와 더 나은 답을 찾아보니 백트래킹 코드가 나와 이해가 편하고 활용성 좋은 풀이 방법으로 문제를 정리했습니다. 비록 하나의 문제에 두 개 이상의 문제를 풀 시간을 소요하긴 했으나 하나의 또 다른 접근법을 배운 것 같아 유익한 문제였습니다.

 

 

 

 

오늘의 한줄평

이해가 안되도 포기마라. 모두의 시작은 1 + 1 = 귀요미다.