AtCoder: D - Gathering Children - 파이썬(Python)

https://atcoder.jp/contests/abc136/tasks/abc136_d

D - Gathering Children

<문제 선지>

N을 S의 길이라고 하자. 왼쪽에서 오른쪽으로 배열된 N개의 사각형이 있고, 왼쪽에서 S의 i번째 문자가 왼쪽에서 i번째 사각형에 쓰여 있다.
가장 왼쪽 사각형에 쓰인 문자는 항상 R이고, 가장 오른쪽 사각형에 쓰인 문자는 항상 L이다.
처음에는 각 사각형에 한 명의 어린이가 서 있다.
각 어린이는 아래의 이동을 10^100회 수행한다.
어린이가 서 있는 사각형에 쓰여진 문자가 지정한 방향으로 한 사각형을 이동한다. L은 왼쪽을 나타내고 R은 오른쪽을 나타낸다.
어린이들이 이동을 수행한 후 각 사각형에 서 있는 어린이의 수를 구한다.

<접근 방법>

문제를 해결하는데 있어서 2단계의 과정을 진행하였다.

 

1단계: 문자열 값 압축하기

 

먼저, 연속된 L 또는 R이 몇 개씩 있는지 전처리를 진행하였다.

예시로, S = "RRLLLLRLRRLL" 을 처리하면 아래와 같이 저장된다.

[('R', 2), ('L', 4), ('R', 1), ('L', 1), ('R', 2), ('L', 2)]

 

2단계: 문제 해결하기

이제, 위에서 처리한 값을 이용하여 문제를 해결해 보자. 우선, 가장 간단한 형태부터 확인하여 규칙을 찾아보았다.

여기서 "RL" 순서로 되어있다면 이 두 자리에 계속 값이 바뀌기만 한다는 점을 발견하였다.

 

그러면 이제 10 ^ 100 번째에는 어떤 값이 되는지 확인할 방법을 찾아보자.

 

S = "RRLLLL" 에서, RL은 각각 1, 2번 index이고, R, L에 해당되는 값을 'O', 'X'로 표시해 보자.

R	R	L	L	L	L
X	O	X	O	X	O

 

그러면 결과는 R에 해당되는 칸에는 3, L에 해당되는 칸에는 3이 되는 것을 알 수 있다.

 

또 다른 예시로, S = "RRRLLLL"을 확인해 보자.

R	R	R	L	L	L	L
O	X	O	X	O	X	O

 

이번에는 R에 해당되는 칸에는 4, L에 해당하는 값은 3이 되는 것을 알 수 있다.

 

 

즉, 모이는 부분의 R, L에서 1칸씩 번갈아 가면서 값이 더해진다는 것을 알 수 있다.

 

이를 식으로 표현하면 아래와 같이 도출할 수 있다.

여기서, 연속인 R의 값 = r, 연속인 l의 값 = l이라 하자.

(R 쪽에 모이는 어린이의 수) = (r + 1) / 2 + l / 2
(L 쪽에 모이는 어린이의 수) = r / 2 + (l + 1) / 2

위의 식을 이용하여 반복문을 적용하면 답을 도출할 수 있다.

<소스 코드>

위의 접근법을 구현한 전체 소스 코드이다.

 

"RL"을 한 사이클로 반복문을 적용해야 하는 점과 idx 관리에 주의를 해야 한다.

 

s = input().strip()
arr = [0] * len(s)
count = []

current = 'R'
tmp = 0

for i in range(len(s)):
    if current != s[i]:
        count.append((current, tmp))
        current = s[i]
        tmp = 1
    else:
        tmp += 1
else: count.append((current, tmp))

idx = -1

for i in range(0, len(count) - 1, 2):
    r = count[i]
    l = count[i + 1]
    idx += r[1]
    
    arr[idx] = (r[1] + 1) // 2 + l[1] // 2
    arr[idx + 1] = r[1] // 2 + (l[1] + 1) // 2

    idx += l[1]
print(*arr)