[99클럽 코테 스터디] 18일차 TIL - 문자, Iterator for Combination

[18일차 미들러] 문자열

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

* 대충 번역: CombinationIterator 클래스를 설계하라.

-  CombinationIterator(string characters, int combinationLength)는 고유한 영어 소문자로 정렬된 문자열 characters와 숫자 combinationLength를 인자로 받아 객체를 초기화한다.

- next()는 길이가 combinationLength인 다음 조합을 사전순으로 반환한다.

- hasNext()는 다음 조합이 존재할 경우에만 true를 반환한다.

Solution

주어진 문자열 characters를 combinationLength 길이만큼 출력할 것이다. 이 때 next가 호출될 때마다 사전식으로 정렬된 문자열이 차례대로 반환되는 것이다. 예를 들어, "abc", 2로 객체가 초기화 되었을 때는 "ab"-"ac"-"bc" 순서로 출력된다.

 

먼저, 가능한 모든 조합을 구하고 사전식으로 정렬하는 방식을 생각했다. 이 방식대로 하려면 현재 어디까지 출력했는지, 인덱스, 가능한 모든 조합 배열과 같은 멤버 변수가 추가로 필요하다. 구현에는 실패해서 홈페이지에 공개된 정답 코드를 참고했다.

class CombinationIterator(object):

    def __init__(self, characters: str, combinationLength: int):
        self.c = characters
        self.n = combinationLength
        self.i = 0
        self.ans = []
        self.permute('', 0)

    def permute(self, word, start):
        if len(word) == self.n:
            self.ans.append(word)
            return
        else:
            for i in range(start, len(self.c)):
                self.permute(word + self.c[i], i+1)
        
    def next(self) -> str:
        ans = self.ans[self.i]
        self.i += 1
        return ans 

    def hasNext(self) -> bool:
        return self.i < len(self.ans)

핵심은 모든 조합으로 가능한 문자열을 찾는 premute 함수이다.

 def permute(self, word, start):
        if len(word) == self.n:
            self.ans.append(word)
            return

재귀를 활용하였고, 종료 조건은 combinationLength 길이만큼 문자열이 길어졌을 때이다. 그 후 정답을 저장하는 멤버 변수 ans에 추가한다.

        else:
            for i in range(start, len(self.c)):
                self.permute(word + self.c[i], i+1)

start는 인자로 받고, 문자열 전체 길이까지 반복하여 문자열을 끝까지 순회한다. 만들어지고 있는 단어 word에 현재 위치(인덱스)의 문자를 덧붙인다. 

 

나는 처음 조건을 만족한 문자열(길이가 self.n)이 append 되면 더 이상 순회가 없는 것이라고 생각했다. 그러나 for문에서 재귀를 호출하고 있기 때문에 해당 루프의 호출은 끝났어도, 계속해서 차례로 호출되며 문자열이 만들어지는 것이었다.

문제에 제시된 예시로 permute함수 동작 과정을 도식화해 보았다.

나다어

나는 다음에 어떻게 풀까

• 재귀를 구현하기 위해서는 여러 스탭을 한 번에 생각해서는 안된다. 무조건 하나의, n번째 케이스에 대한 구조를 짜야한다.
• 반복문에서 재귀를 구현하면 많은 경우를 커버할 수 있다. 또 다시 위의 나다어처럼, 단계만 구분하고 통채로 재귀 함수 처리 해버려야 안꼬인다.