📚 문제 : Line
📖 풀이
사람들을 1열로 세운다.
1열로 세운 사람들이 L, R로 왼쪽과 오른쪽을 바라보고 선다.
바라봤을 때 나오는 사람의 숫자만큼 세서 더해준다.
사람이 총 n명이면, 1~n번 사람의 방향을 최대로 바꿔 나올 수 있는 최대 값을 출력한다.
무조건 n번 지나면 가장 많이 셀 수 있도록 사람들의 방향이 지정이 된다.
문제를 풀기 위해 알아야 할 포인트는 가장자리의 사람부터 바꿔준다.(바꿀 수 없으면 pass)
그래서 일단 중심 값을 구하고 투 포인터로 맨 앞과 맨 뒤 사람들의 위치를 기억해 바꿔서 커질 수 있으면 바꿔준다.
맨 앞을 s, 맨 뒤를 e로 정하고 s와 e 중 중심값에서 먼 사람부터 확인한다.
확인한 결과 사람의 방향을 바꿨을 때 더 커질 수 있다면 바꾸고, 아니면 바꾸지 않는다.
이 때, 중심보다 앞에 있는 경우는 왼쪽을 바라보는 경우보다 오른쪽을 바라보는 경우에 값이 더 커진다. 따라서 왼쪽을 바라보고 있는 경우만 바꿔주면 된다.
중심보다 뒤에 있는 경우는 위와 반대로 오른쪽을 바라보고 있는 경우만 왼쪽으로 바꿔준다.
result를 n개 만큼 배열을 만들어 1~n 번 바꿔준 경우의 결과를 담을 것이다. 0으로 초기화 한다.
result에 하나씩 담아주고, 더이상 바꿔줄 수가 없다면 종료한다.
result에 그러면 0이 남는 경우가 발생하는 데, 이 때는 현재 나온 total 값을 담아주면 된다.(지금까지 구한 total 값이 최대 나올 수 있는 total 값이다.)
그리고 result를 언패킹 연산자를 활용해 출력한다.
📒 코드
t = int(input())
for _ in range(t):
n = int(input())
arr = input()
ans = [0 for _ in range(n)] # 각 자리 수
for i in range(n):
if arr[i] == 'L':
ans[i] = i
else:
ans[i] = n - i - 1
result = [0 for _ in range(n)] # k에 따른 각 자리 수의 합
total = sum(ans)
k = 0
s, e = 0, n - 1
mid = (s + e) // 2
while s <= e and k < n:
if mid - s >= e - mid:
if ans[s] == s:
total -= ans[s]
ans[s] = n - s - 1
total += ans[s]
result[k] = total
k += 1
s += 1
else:
if ans[e] == n - e - 1:
total -= ans[e]
ans[e] = e
total += ans[e]
result[k] = total
k += 1
e -= 1
# 나머진 total 값을 넣어준다.
for i in range(n)[::-1]:
if result[i] == 0:
result[i] = total
else:
break
print(*result)
🔍 결과
passionate developer