[파이썬/python] 백준 24523 - 내 뒤에 나와 다른 수

문제

https://www.acmicpc.net/problem/24523

---

문제 설명

1.   수열 A가 주어진다.
2. $1\le i \le N$인 정수 $i$마다 $i < j \le N$이고 $A_i \ne A_j$인 정수 $j$중 최솟값을 출력하라. 
3. 만약 이러한 j$j$가 없다면 −1$-1$을 출력하라.

---

풀이

1. 수열을 순회하면서 현재 인덱스와 이전 인덱스가 다른 위치를 찾아 배열에 저장한다.
2. 값이 전환되는 포인트를 기점으로 반복문을 통해 해당 위치의 인덱스를 사이의 범위만큼 출력한다.
   1. 마지막 포인트일 경우 -1을 출력한다.

---

코드

import sys
input = sys.stdin.readline

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

prev = arr[0]
lst = []
for i in range(1, N):
    if prev != arr[i]:
        lst.append(i)
        prev = arr[i]
lst = [0] + lst + [N]
for i in range(1, len(lst)):
    for _ in range(lst[i-1], lst[i]):
        print(-1,end=' ') if i == len(lst)-1 else print(lst[i]+1,end=' ')

---

시간복잡도

• 값이 달라지는 위치를 배열에 저장할 때 약 $O(N)$의 시간복잡도를 가진다.
• 결과값을 출력할 때도 약 $O(N)$의 시간복잡도를 가진다.
• 따라서 총 시간복잡도는 최악일 경우 $N = 10^6$, 약 $O(2*N)$의 시간복잡도를 가진다.