[python] 9519 - 졸려

9519번: 졸려 (acmicpc.net)

9519번: 졸려

 

문자열 구현 문제였다.

처음 접근 방식은 다음과 같다.

문자열을 원래대로 복원하기만 하면 되기 때문에

바꿔야 할 알파벳 수를 구한 후 문자열을 바꾼다.

 

처음 주어진 규칙을 반대로 하기만 하면 되기 때문에

while문을 이용하여 횟수만큼 반복한 후

문자열을 출력한다.

 

그런데 두 번째 예제를 보니 왠지 시간초과에 걸릴 것만 같았다..

문자열이 모두 같은 알파벳일 경우 횟수에 의미가 없기 때문이다.

 

그래서 중간에 break도 걸어보고 다양하게 시도해 보았으나 계속 시간 초과가 떴고

그러던 와중 좋은 해결법이 떠올랐다.

 

첫 입력 문자열이 aabbc 라면 반복하다 보면 원래 입력 문자열이 나오는 시점이 있을 것이다.

이를 이용하여 알고리즘을 짜 보았다.

 

1. while문을 이용하여 문자열을 규칙에 따라 복원하면서 처음 문자열과 같지 않다면 새로운 배열에 저장

2. 처음 문자열과 같은 순간이 온다면 while문을 종료

3. 새로운 배열에 저장된 문자열들이 입력 문자열이 변화하는 주기가 되기 때문에

    (변화횟수 //  새로운 배열 길이)-1 의 인덱스에 있는 원소 값이 구하고자 하는 문자열이 된다.

# 9519 졸려
import sys
from collections import deque
input = sys.stdin.readline

x = int(input())
word = list(input().strip())
start = ''.join(word)
#원래 입력값이 나올때까지 반복되는 문자배열 저장
rst=[]

while True:
    # 위치 변화 개수
    n = len(word) // 2
    stk=[]
    stk2=deque()
    
    # for문을 돌며 위치를 변화시켜야 하는 알파벳과 그렇지 않은 알파벳 검사
    for i in range(len(word)-1, -1, -1):
        alpha=word.pop()
        if i == (2*n)-1:
            stk.append(alpha)
            n-=1
        else:
            stk2.appendleft(alpha)
    word=list(stk2)+stk
    
    # 처음 입력값과 다르다면 rst에 append, 그렇지 않다면 종료
    if ''.join(word) != start:
        rst.append(''.join(word))
    else:
        rst.append(''.join(word))
        break
    
# rst의 길이가 1이라면 문자열의 알파벳이 모두 같으므로 그대로 출력
# 길이가 다르면 반복하는 횟수를 rst의 길이로 나눈 나머지-1이 인덱스인
# 배열 rst의 원소 출력
if len(rst) == 1:
    print(rst[0])
else:
    k = x%len(rst)
    print(rst[k-1])

 

이렇게 하면 실행 횟수를 단축할 수 있을 뿐 아니라 

2번 예제와 같이 문자열의 알파벳이 모두 같은 경우 한번의 비교를 통해

바로 출력 가능하다!

 

스스로 생각해낸 방법으로 시간초과 문제를 해결해서 뿌듯함을 느꼈던 문제였다:)

 

 

* 모든 코드는 github에서 관리합니다.  seinShin (SEIN SHIN) (github.com)

seinShin - Overview