문제 풀이)
문제에서 제시하는 풀이과정을 이해하는데 시간이 걸렸던 문제였다.
문자열을 분해하는 단계를 가만히 읽어보면 특정 과정을 반복하고 문자열을 또개 또 같은 과정을 반복하다 조건을 만족하지 못하면 종료하란 상황.
재귀적으로 시도해보겠다고 결정.
문제에서 말하는 과정은 다음과 같다. 첫번째 입출력 예의 경우 문자열을 'banana'다
첫번째로 x는 'b'가 되고 나머지 문자열은 'anana'가 된다.
이때 b의 갯수는 1개 이고 anana를 왼쪽에서 오른쪽으로 읽을때 첫번째로 b가 아닌 a의 갯수가 1개 이므로 ba를 분리하고 나머지 nana를 가지고 위의 과정을 되풀이합니다.
이번엔 n이 시작문자 이므로 n 1개 그 다음 ana를 왼쪽에서 오른쪽으로 읽어나가며 n인 경우와 n이 아닌 경우 각각 count를 해줘야합니다. 첫번째에 a가 나와서 n 1번 a1번 이므로 na를 분리한후 나머지 na를 가지고 위의 과정을 되풀이합니다.
위 과정을 구현한 재귀적 코드는 다음과 같습니다.
import sys
sys.setrecursionlimit(10000) # 재귀 콜스택 오버플로 방지
def solution(s):
global answer
answer = 1
def recursion(s):
global answer
start = s[0]
x, y = 1, 0
for i, val in enumerate(s[1:]): # 시작 글자를 제외하고 왼쪽에서 오른쪽으로 읽기
if x == y: # 나온 수가 같다면
answer += 1
return recursion(s[i+1:]) # 지금까지 읽은 문자열을 제외하고 나머지로 다시 반복 실행
if i == len(s)-1: # 더는 읽을 문자열이 없을경우
answer += 1
break
if val == start: #만약 맨 앞글자와 같다면 앞글자 수를 update
x += 1
else: # 다른 글자라면 다른 글자 수를 update
y += 1
recursion(s)
return answer
'Algorithm' 카테고리의 다른 글
[프로그래머스 - lv1, 2018 KAKAO BLIND RECRUITMENT] [1차] 다트 게임, 파이썬 (2) | 2023.03.15 |
---|---|
[프로그래머스 - lv1] 최소직사각형 (0) | 2023.03.13 |
[프로그래머스 - lv1, 2023 KAKAO BLIND RECRUITMENT] 개인정보 수집 유효기간 파이썬 (0) | 2023.03.07 |
[프로그래머스 - lv1] 기사단원의 무기 파이썬 (4) | 2023.03.06 |
[프로그래머스 - lv1, 2018 KAKAO BLIND RECRUITMENT] - [1차] 비밀지도 (0) | 2023.03.03 |