ABC 337 C 성공

N명의 사람이 자기 앞 사람의 번호를 말한다.

맨 앞 사람은 -1을 말한다.

이때 사람들의 순서를 출력한다.

 

 

 

 

 

 

 

 

 

 

 

# 내 코드
import sys

input = sys.stdin.readline

N = int(input())
l = list(map(int, input().split()))
x = [-1] * (N+1)
for e in range(N):
    if l[e] == -1:
        x[0] = e + 1
    else:
        x[l[e]] = e + 1

print(x[0], end=' ')
save = x[0]
for _ in range(1, N):
    print(x[save], end=' ')
    save = x[save]

맨 앞사람은 -1을 외치므로 가장 쉽게 찾을 수 있다.

문제는, 그 다음 사람은 앞사람의 index를 외치고 있으므로 정렬되지 않은 데이터에서 찾기 위해선 O(N)의 시간이 걸린다.

전체 순서를 찾으려면 O(N)이 N번이므로 시간초과다.

인덱스와 데이터를 바꾸는 방법으로 해결 가능하다.

문제는

1. 코딩의 목적을 제대로 되새기지 않고 짜느라 계속 헷갈렸다.

해결은

1. 코딩(내가 이 코드를 지금 왜 짜고 있는지)를 확실하게 인지하고 있거나 의사코드를 작성한다.

많은 문제를 풀어가며 수학, 컴퓨터적인 머리를 기르자.