[엘리스 알고리즘 코드 챌린지 시즌 2] 예선 3일 [Python]

풀이

입력받은 문자열 S에 대해 압축을 해제하는 문제다.

압축된 문자열은 K(Q)의 형식으로 주어지며 이를 해제할 경우 Q를 K번 반복한다는 의미다.

스택과, 재귀 중 스택으로 푸는 방법이 익숙해 스택을 사용해 풀이했다.

 

K(K(Q)K(Q))와 같은 예외를 고려해 문자열의 역순으로 진행했다.

정작 제공된 테스트케이스에는 이와 같은 예외가 없었다.

우선 ')' 인 경우에는 그냥 stack에 집어넣자.

그 다음에는 Q에 해당하는 수들이 들어올 것이다.

만약 stack의 마지막 요소가 ')'가 아니라면 Q의 길이를 저장하는 방식이므로 주어진 수( num )를 넣거나 더해주자.

탐색을 계속 진행해 '(' 가 나온다면 스택에 넣은 Q의 길이를 뽑아 K와 곱해준 후 다시 스택에 넣어주면 된다.

이 과정에서 중복계산과 스택에 남아있는 구분자 ')' 를 제거해준 후 스택에 K(Q)의 길이를 넣어주자.

 위의 과정을 반복하면 마지막에는 스택에 문자열 압축을 해제한 전체 문자열의 길이가 남을 것이다. 출력해주자.

---

소스코드

보기

---

출처

엘리스 코드 챌린지