[백준][Python 파이썬] 22945번 팀 빌딩

직관적으로는 모든 값을 이중 for문으로 순회하면서 능력치를 계산하는 방법이 있다. 

그러나 이 방법으로 하면 시간초과가 난다. 

 

리스트의 전체 값을 순회해야 하는데 정석대로 하면 시간초과가 나는 경우, 투 포인터를 사용해서 접근해볼 수 있다. 

능력치는 (두 개발자 사이에 있는 개발자 수) * (두 개발자의 능력치 중 작은 값)으로 계산되므로, left와 right이라는 두 포인터를 리스트의 양 끝에 배치시켜서 두 개발자 사이에 있는 개발자 수를 최대로 만들어 보자. 

 

그리고 두 포인터가 가리키는 값 중에서 누가 더 작은지를 비교해서, 더 작은 쪽의 값을 변화시키는 방식으로 포인터를 이동해 나간다. 

left 쪽의 값이 더 작다면 left를 한 칸 오른쪽으로, right의 값이 작다면 right를 한 칸 왼쪽으로 이동하는 식이다. 

 

그러면 이중 for문의 풀이는 O(n^2)였던 데 비해, 투 포인터로 O(n)에 풀 수 있어서 시간초과가 나지 않는다. 

 

import sys

input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

answer = 0
left, right = 0, N-1
while left < right:
    cur = (right-left-1) * min(arr[left], arr[right])
    answer = max(cur, answer)
    if arr[left] > arr[right]:
        right -= 1
    else:
        left += 1

print(answer)