[LeetCode] 1286 Iterator for Combination

💡  오늘의 학습 키워드

📌  조합

📌  백트래킹

 

문제 설명

문제 링크 : https://leetcode.com/problems/iterator-for-combination/

Design the CombinationIterator class:
- CombinationIterator(string characters, int combinationLength) Initializes
the object with a string characters of sorted distinct lowercase English letters and
a number combinationLength as arguments.
- next() Returns the next combination of length combinationLength in lexicographical order.
- hasNext() Returns true if and only if there exists a next combination.

제한 사항
1. 1 <= combinationLength <= characters.length <= 15
2. All the characters of characters are unique.
3. At most 10^4 calls will be made to next and hasNext.
4. It is guaranteed that all calls of the function next are valid.

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

itertools.combination을 사용하여 모든 조합을 미리 계산해 리스트에 저장하고 순서를 조절하는 메소드를 구현하는 문제였습니다.
next 메소드는 현재 인덱스 위치의 조합을 반환하고 인덱스를 증가시키며, hasNext 메소드는 다음 메소드 존재 여부를 반환합니다.

 

여기서 주의할 점은 combination 함수는 튜플 형태로 반환한다는 점입니다.
join 함수를 이용하여 해당 튜플 값들을 합쳐서 반환해주어야 합니다.

 

백트래킹 방식을 이용해 각 조합을 생성할 때마다 상태를 저장하고 되돌리는 과정을 거칠 수도 있는데,
이 과정은 재귀 호출과 리스트 조작을 포함하기 때문에 시간 복잡도와 메모리 사용량을 증가시킵니다. 
따라서 combination을 사용해 초기화 시점에 조합을 미리 계산해두는 것이 효율적입니다.

 

itertools.combination은 매우 최적화된 C로 구현되어 있어 파이썬에서 직접 조합을 생성하는 것보다 빠릅니다!

💡 내가 해결한 방식은?

combinations를 이용한 풀이

from itertools import combinations

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        # 해당 characters의 조합 결과 리스트
        self.combi = list(combinations(characters, combinationLength))
        # 현재 위치
        self.cur_idx = 0

    def next(self) -> str:
        result = ''.join(self.combi[self.cur_idx])
        self.cur_idx += 1
        return result

    def hasNext(self) -> bool:
        if self.cur_idx >= len(self.combi):
            return False
        else:
            return True

백트래킹을 이용한 풀이

class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
        self.characters = characters
        self.combinationLength = combinationLength
        self.currentCombination = []
        self.nextCombination = self._generate_next_combination()
    
    def _generate_next_combination(self):
        # 내부적인 상태를 유지하기 위한 재귀적 백트래킹 함수
        def backtrack(start, path):
            if len(path) == self.combinationLength:
                self.currentCombination.append(''.join(path))
                return
            for i in range(start, len(self.characters)):
                backtrack(i + 1, path + [self.characters[i]])
        
        # 첫 번째 조합을 생성합니다.
        backtrack(0, [])
    
    def next(self) -> str:
        if self.hasNext():
            return self.currentCombination.pop(0)
        return ""
    
    def hasNext(self) -> bool:
        return len(self.currentCombination) > 0

 

---

✍️  TIL

조합을 직접 구현하는 문제인줄 알았는데, 영어를 제대로 해석하고 조합을 사용하는 문제라는 것을 알았다.
itertools에 구현된 조합 메소드를 사용하는게 직접 구현하는 것보다 효율적이라는 것을 백트래킹 풀이법을 보고 알았다.
기억할 점이라면 collections의 두번째 매개변수의 활용과 해당 메소드의 리턴 값이 튜플이라는 점,
그래서 join을 통해 합쳐주어야 제대로 된 string 값을 리턴할 수 있다는 점이다.