[백준][파이썬] 24523번. 내 뒤에 나와 다른 수

문제

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

 

풀이

첫 번째 풀이

각 i에 대해 모든 경우를 살펴보면서 조건을 만족하는 j를 출력하려고 했다.

for문을 두 번 도는 코드다보니 당연하게도(?) 시간 초과가 떴다.

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

answer = [-1] * N
for i in range(N-1) :
  for j in range(i+1, N) :
    if A[i] != A[j] :  # 조건 만족
      answer[i] = (j+1)
      break
print(*answer)

→ 시간 초과

 

두 번째 풀이

예제 1 처럼 같은 숫자가 반복되어 나타나는 경우, 조건을 만족하는 최솟값 j는 같은 값일 것이므로 굳이 모든 i에 대해 다 살펴볼 필요가 없다.

이 점에 집중하며, for문을 한 번만 돌도록 코드를 수정했다.

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

answer = [-1] * N
i = 0

for j in range(1, N) :
  if A[i] != A[j] :
    answer[i:j] = [j+1] * (j-i)
    i = j
print(*answer)