(두 위치의 거리 * 두 위치의 원소 중 최솟값)의 최댓값을 투포인터로 찾는 방법

22945번: 팀 빌딩

 

 

n명이 한줄로 서있을 때 2명을 골라 그 2명 사이의 사람 수 * min(첫번째 사람의 능력치, 두번째 사람의 능력치)의 최댓값을 찾는 문제

 

[1,4,2,5]이면 A[1] = 4, A[3] = 5이고 두 사람 사이에는 1명 있고 둘 중 최솟값은 4니까 4가 최댓값이다

 

투 포인터로 해결할 수 있다해서 연습삼아 풀어볼려했는데

 

기존에 알던 투 포인터 풀이는 안먹히니 답이 없다

 

인덱스랑 같이 넣어서 정렬해야하나 일단 정렬이 안되어있고 포인터 움직여도... min값이 커졌다 작아졌다 하는데

 

근데 0번과 n-1번에 포인터를 두고 서로 간격을 좁혀가면 된다는데

 

그래도 어떻게 해야하는지 고민되더라고

 

A[i], A[i+1], A[i+2], A[i+3], ...., A[j]

 

i번과 j번을 가리키고 있을 때 value = min(A[i], A[j]) * (j - (i-1) -2)

 

j번을 1 감소시키더라도 min값이 커지거나 작아질 수 있고 i번을 1 증가시키더라도 min 값이 커지거나 작아질 수 있는데..

 

이 순간에 i를 증가시키냐 j를 감소시키냐

 

근데 조금 더 생각해보니까

 

만약 A[i] > A[j]라고 생각해보자.. 그러니까 A[j]가 더 작은 값일 때

 

i를 증가시킨다면?

 

여전히 A[i+1] > A[j]라고 한다면, min(A[i],A[j]) = A[j]로 동일하고 (j - (i-1) -2)은 1 감소하므로 value가 작아진다

 

그런데 A[i+1] < A[j]라고 한다면, min(A[i+1],A[j]) = A[i+1]가 되는데, 원래 A[j]보다 작아지고 (j - (i-1) -2)은 1 감소하므로 value가 작아진다

 

따라서 i를 증가시키는 것은 좋은 선택이 아니다

 

그러면 j를 감소시킨다면

 

A[i] > A[j-1]이라고 한다면 min(A[i],A[j-1])의 값은 A[j-1]로 변하는데 둘 사이의 거리 (j - (i-1) -2)은 1 감소하게 된다

 

여기서 A[j-1] > A[j]라고 한다면 min(A[i],A[j-1])이 원래보다 커지므로 value는 커질 가능성이 있다

 

물론 A[j-1] < A[j]라고 한다면 value는 작아진다

 

A[i] < A[j-1]이라고 한다면 min(A[i],A[j-1])은 A[i]가 되는데 이 역시 A[i] > A[j]이므로, min(A[i],A[j-1])이 원래보다 커져 value가 커질 가능성이 있다

 

그러니까 커질 가능성이 있는 부분을 탐색해야 맞으므로 A[i] > A[j]이면 j를 감소시키는 것이 맞다

 

반대로 A[i] <= A[j]라면 i를 증가시키는 것이 맞다

 

따라서 i = 0, j = n-1부터 시작해서 value를 계산하고 최댓값을 갱신한 다음 A[i], A[j]의 값에 따라 i,j를 바꿔준다

 

n = int(input())

A = list(map(int,input().split()))

i = 0
j = n-1

answer = 0

while i <= j:
    
    if A[i] > A[j]:

        v = A[j] * (j-(i-1)-2)
        j -= 1
    
    else:
        
        v = A[i] * (j-(i-1)-2)
        i += 1

    if answer < v:

        answer = v    

print(answer)

 

 

A의 원소가 10000이하라는 것을 이용해서 $O(X^{2})$에 해결하는 해법이 있다

 

A의 원소에 대한 인덱스 최솟값과 최댓값을 저장해둔다음

 

x = 1~10000, y = 1~10000에 대하여 두 원소 x,y를 선택했다고 할 때

 

y의 최대 인덱스와 x의 최소 인덱스 사이 거리가 가장 큰 경우가 최댓값이 될 수 있으므로 이를 탐색해보면 된다

 

n = int(input())

A = list(map(int,input().split()))

left = [-1]*(10001)
right = [-1]*(10001)

for i in range(n):
    
    if left[A[i]] == -1:
        
        left[A[i]] = i
    
    right[A[i]] = i

answer = 0

for x in range(1,10001):
    
    if left[x] == -1:
        
        continue

    for y in range(1,10001):
        
        if right[y] == -1:
            
            continue

        answer = max(answer, min(x,y) * (right[y] - left[x]+1 -2))

print(answer)

 

 

left에 x의 최소 인덱스 right에 x의 최대 인덱스를 저장해두는데 최소 인덱스 같은 경우는 한번만 갱신하면 되고

 

right에는 A[i]를 볼때마다 저장해둔다면 최대 인덱스를 저장해두는 거겠지