[Python] 백준/BOJ 24523번: 내 뒤에 나와 다른 수 (Silver 2)

💻 Problem

문제 보러 가기

 

길이가 N인 수열 A_1  A_2 ...  A_N이 주어진다. 1 ≤ i ≤ N인 정수 i마다 i < j ≤ N이고 A_i ≠ A_j인 정수 j중 최솟값을 출력하라. 만약 이러한 j가 없다면 -1을 출력하라.

 

💡 Approach

처음엔 이중반복문으로 푸는 방법밖에 생각 안 났다... ㅜㅜ

근데 시간 계산해보니 이중반복문으로 풀면 시간 터져서 반복문을 중첩하지 않는 방식을 생각해 보았다...

 

연속된 A[i]의 값이 같으면 정답인 j도 항상 같다.

A[i]의 정답인 j는 시작하는 A[i]에서 자신과 같은 값인 칸들을 건너뛰고 처음으로 다른 값이 나오는 칸의 index이다.

 

결론은 투 포인터로 풀었다.

왼쪽을 가리키는 포인터 하나(l)와 오른쪽을 가리키는 포인터 하나(r)를 뒀다.

 

두 포인터가 가리키고 있는 값이 같으면 r 포인터는 오른쪽으로 한 칸 이동한다. (연속 구간 찾아서 패스)

같지 않다면 l부터 r 구간까지의 정답을 r + 1로 초기화해 준다. (연속 구간이 끝났으면 정답 찾기)

그 후, 두 포인터의 위치를 조정해 준다.

그다음 범위를 탐색해야 하므로 l은 r로, r은 방금 초기화된 l + 1로 조정한다.

 

정답 배열은 처음에 -1로 선언하여 위 탐색에서 j가 없었다면 -1을 출력하도록 한다.

 

✏️ Solution

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(lambda x: int(x) - 1, input().split()))
res = [-1] * N

l, r = 0, 1
while r != N:
    if A[l] == A[r]:
        r += 1
    else:
        res[l:r] = [r + 1] * (r - l)
        l = r
        r = l + 1

print(*res)

시간복잡도는 O(N)이다.

반복문 하나에서 대충 배열의 시작부터 끝까지 한 번 스캔하므로 O(N)이 된다.