이번 문제는 시간 초과 발생으로 인해 많은 시도를 했던 문제이다. 처음에는 단순하게 이중 for문으로 작성하였고 N의 범위로 인해 당연하게 시간 초과가 발생하였다. 성능 개선을 고민하던 중 while문 안에서 포인터 2개로 서로를 비교하도록 작성하였지만 또 다시 시간 초과가 발생하였다. 문제점은 바로 p1과 p2가 다를 경우에 p1을 1만 증가시켰던 부분이었다.

while p1<=p2:
	if p1==n-1:
    	break
    if arr[p1]!=arr[p2]:
    	answer.append(p2+1)
        p1+=1
        p2=p1+1
    elif p2==n-1 and arr[p1]==arr[p2]:
    	answer.append(-1)
        p1=+=1
        p2=p1+1
    elif arr[p1]==arr[p2]:
    	p2+=1

p1과 p2가 같을 경우에는 p2만 1씩 증가하기 때문에 같은 수가 연속으로 있다면 p2는 그만큼 멀어질 것이다. p1과 p2가 가리키는 수가 다를 때, p2가 지나온 수들은 모두 p1과 같은 수 이므로, p1이 가리키는 수의 결과값과 같은 값을 가지게 된다. 그러므로 지나온 수들에 대한 결과값까지 한번에 입력해주어야 시간을 단축할 수 있다.

while p1<=p2:
    if p1==n-1:
        break
    if arr[p1]!=arr[p2]:
        answer+=[p2+1]*(p2-p1)
        p1=p2
        p2+=1
    elif p2==n-1 and arr[p1]==arr[p2]:
        answer+=[-1]*(p2-p1)
        break
    elif arr[p1]==arr[p2]:
        p2+=1

마지막 원소의 경우 비교 대상이 없기 때문에 무조건 -1을 가지게 된다. 그러므로 while문 이후에 answer에 -1을 한번 더 넣어주어야 한다.

• n을 입력받는다.
• arr을 입력받는다.
• 정답을 저장할 리스트 answer를 선언한다.
• 두 포인터로 사용할 변수 p1, p2를 0, 1로 선언한다.
• p1이 p2보다 작거나 같을 동안 반복하는 while문을 돌린다.
  -> 만약 p1이 n-1일 경우, while문을 종료한다.
  -> 만약 arr[p1]이 arr[p2]와 다를 경우,
  --> answer에 [p2+1]을 p2-p1개 넣는다.
  --> p1을 p2로 갱신한다.
  --> p2를 1 증가시킨다.
  -> 만약 p2가 n-1이고, arr[p1]이 arr[p2]와 같을 경우,
  --> answer에 -1을 p2-p1개 넣는다.
  --> while문을 종료한다.
  -> 만약 arr[p1]이 arr[p2]와 같을 경우,
  --> p2를 1 증가시킨다.
• answer에 -1을 넣는다.
• answer를 언팩킹하여 출력한다.

이 풀이는 O(N)의 시간복잡도를 가진다.

Code

import sys
input=sys.stdin.readline
n=int(input())
arr=list(map(int, input().split()))
answer=[]
p1, p2=0, 1
while p1<=p2:
    if p1==n-1:
        break
    if arr[p1]!=arr[p2]:
        answer+=[p2+1]*(p2-p1)
        p1=p2
        p2+=1
    elif p2==n-1 and arr[p1]==arr[p2]:
        answer+=[-1]*(p2-p1)
        break
    elif arr[p1]==arr[p2]:
        p2+=1
answer.append(-1)
print(*answer)