[백준] 27210-신을 모시는 사당

문제바로가기

맨 처음에 .count연산으로 풀었다가 당연하게도 시간 초과가 났다.

for i in range(N):
    for j in range(N, 0, -1):
        idea = max(idea, abs(stones[i:j].count(1)-stones[i:j].count(2)))
print(idea)

이런 식으로 이중 포문으로 검사했다가 O(n^3) (생각해보면 당연함.)이 나오는 엄청난 결과를 얻었는데 아무리 생각해도 1의 개수랑 2의 개수 차이를 표현할 아이디어가 없어서 검색을 해봤다.

해결 방법은 바로 2인 값을 -1로 바꾸면 된다. 이런 좋은 방법이!

N = int(input())
stones = list(map(int, input().split()))
prefix_sum = [0]*(N+1)
stones = [-1 if x == 2 else x for x in stones]

for i in range(N):
    if N == 1:
        prefix_sum[i] = stones[i]
    else:
        prefix_sum[i+1] = prefix_sum[i] + stones[i]

max_diff = 0
min_val = prefix_sum[0]
max_val = prefix_sum[0]

for i in range(1, N+1):
    max_diff = max(max_diff, abs(prefix_sum[i]-min_val), abs(max_val-prefix_sum[i]))
    max_val = max(prefix_sum[i], max_val)
    min_val = max(prefix_sum[i], min_val)

print(max_diff)

그리고 실수해서 오래 걸린 부분은 바로 min_val과 max_val 둘 다 생각해야한다는 것. 수가 작은 수부터 점점 커질 수도 있고예시 : 1 1 1 2 2, 큰 수부터 점점 작이질 수 있기 때문에예시 : 2 2 2 1 1 두 경우 모두 고려하기 위한 방법이다.