[99클럽 코테 스터디 29일차 TIL] LeetCode | 1286. Iterator for Combination

29일차 문자열

꾸준히 잘 써오다가 28일차 TIL을 놓쳐버렸어요 🥲 다시 킵고잉~

Problem

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

Sol

오늘 문제는 주어진 문자로부터 주어진 길이의 1. 모든 조합을 생성하고 2. 다음 조합을 반환하고 3. 다음 조합이 있는지 확인하는 class CombinationIterator를 완성하는 문제였습니다. combinations을 사용한 코드와 그렇지 않은 코드 2가지로 해결해보았습니다.

itertoools.combination 사용

👀 Python 내장 모듈인 ‘itertools’의 combinations를 활용하면, 입력된 반복 가능한(iterable) 객체에서 주어진 길이의 조합을 생성할 수 있습니다.  

from itertools import combinations

class CombinationIterator:

    def __init__(self, characters: str, combinationLength: int):
        self.combinations = [''.join(comb) for comb in combinations(characters, combinationLength)]
        self.index = 0

    def next(self) -> str:
        combination = self.combinations[self.index]
        self.index += 1
        return combination

    def hasNext(self) -> bool:
        return self.index < len(self.combinations)


# 사용 예시
# obj = CombinationIterator("abc", 2)
# print(obj.next())    # "ab" 반환
# print(obj.hasNext()) # True 반환
# print(obj.next())    # "ac" 반환
# print(obj.hasNext()) # True 반환
# print(obj.next())    # "bc" 반환
# print(obj.hasNext()) # False 반환

1. init 초기화
- sefl.combinations : 주어진 문자들(characters)과 길이(combinationLength)로 생성된 가능한 모든 조합의 리스트 초기화
- self.index : 현재 조합의 위치 추적

2. 다음 combination 반환
- 현재 인덱스의 조합 가져옴
- 인덱스 +1 : 다음 호출에서 다음 조합을 가리키도록

3. 다음 combination 있는지 확인

generate_combinations 함수 구현

👀 back tracking을 활용하여 가능한 모든 조합을 생성하는 generate_combinations 함수를 만들어주었습니다.

class CombinationIterator:
    # not using combinations of itertools

    def __init__(self, characters: str, combinationLength: int):
        self.combinations = self.generate_combinations(characters, combinationLength)
        self.index = 0
        

    def generate_combinations(self, characters, combinationLength):
        def backtrack(start, path):
            if len(path) == combinationLength:
                combinations.append(''.join(path))
                return
            for i in range(start, len(characters)):
                path.append(characters[i])
                backtrack(i + 1, path)
                path.pop()
                
        combinations = []
        backtrack(0, [])
        return combinations
    
    def next(self) -> str:
        combination = self.combinations[self.index]
        self.index += 1
        return combination

    def hasNext(self) -> bool:
        return self.index < len(self.combinations)
        


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

1. init 초기화
- self.combinations, self.index 초기화

2. generate_combinations 함수
- 재귀를 사용해 가능한 모든 조합 생성
- backtrack : 시작 인덱스와 현재 경로를 매개변수로 받아 조합을 재귀적으로 생성
- 조합이 주어진 길이에 달하면, 해당 조합을 리스트에 추가

3. 다음 combination 반환

4. 다음 combination 있는지 확인

소감
공부를 많이 열심히 하자. 게을러지지 말자.