런-길이 인코딩(Run-Length Encoding)된 소문자 문자열 s로 생성되는 반복자(iterator) 클래스를 정의한다고 가정해 보겠습니다. 이 반복자 클래스에는 두 가지 핵심 함수가 필요합니다.
- next(): 반복자의 다음 요소를 찾아 반환합니다.
- hasnext(): 다음 요소가 존재하는지 여부를 확인합니다.
예를 들어 입력이 s = "2b1a"라고 할 때, 이 문자열로 객체를 생성한 후 next(), hasnext(), next(), next(), hasnext() 순서로 호출하면 출력은 "b", True, "b", "a", False가 됩니다.
해결 접근 방식
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- 문자열 s를 매개변수로 받는 생성자(
__init__)를 정의합니다. - output := 새로운 리스트, num := 빈 문자열로 초기화합니다.
- s의 각 문자 i에 대해 다음을 수행합니다.
- i가 알파벳이면 output 끝에 num을 정수로 변환해 추가하고, 그다음 i를 추가한 뒤 num을 빈 문자열로 초기화합니다.
- 그렇지 않으면(숫자인 경우) num에 i를 이어 붙입니다.
- next() 함수를 정의합니다.
- hasnext()가 참이면 count := output[0], letter := output[1]로 설정합니다.
- count를 1 감소시킨 후, count > 0이면 output[0] 값을 1 감소시킵니다.
- 그렇지 않으면 output에서 앞의 두 요소([개수, 문자] 쌍)를 제거합니다.
- letter를 반환합니다.
- hasnext() 함수를 정의합니다. output의 크기가 0이 아니면 True를, 그렇지 않으면 False를 반환합니다.
예제 코드
다음 구현을 통해 더 잘 이해해 보겠습니다.
class RunLengthIterator:
def __init__(self, s):
self.output = []
num = ""
for i in s:
if i.isalpha():
self.output.append(int(num))
self.output.append(i)
num = ""
else:
num += i
def next(self):
if self.hasnext():
count = self.output[0]
letter = self.output[1]
count -= 1
if count > 0:
self.output[0] -= 1
else:
self.output = self.output[2:]
return letter
def hasnext(self):
if len(self.output) != 0:
return True
return False
s = "2b1a"
obj = RunLengthIterator(s)
print(obj.next())
print(obj.hasnext())
print(obj.next())
print(obj.next())
print(obj.hasnext())
코드 동작 원리
생성자는 인코딩된 문자열을 파싱하여 [개수, 문자] 쌍의 리스트로 변환합니다. 예를 들어 "2b1a"는 [2, 'b', 1, 'a']가 됩니다. next()가 호출될 때마다 현재 문자의 남은 개수를 하나 줄이고, 개수가 0이 되면 해당 쌍을 리스트에서 제거하여 다음 문자로 넘어갑니다. 덕분에 문자열 전체를 미리 펼쳐 놓지 않고도 메모리를 효율적으로 사용할 수 있습니다.
입력
"2b1a" obj = RunLengthIterator(s) obj.next() obj.hasnext() obj.next() obj.next() obj.hasnext()
출력
b True b a False