[Baekjoon] 25287 순열 정렬
https://www.acmicpc.net/problem/25287
import sys
input = sys.stdin.readline
def yesorno():
N = int(input());
num = list(map(int, input().split()));
mid = N//2 if N%2==0 else N//2+1
idx = num.index(mid)
num[0] = min(num[0], N-num[0]+1)
for i in range(1, idx):
num[i] = min(num[i], N-num[i]+1)
if num[i] < num[i-1] : return 0;
for i in range(idx+1, N):
num[i] = max(num[i], N-num[i]+1)
if num[i] < num[i-1] : return 0;
return 1;
for _ in range(int(input())):
if yesorno(): print('YES')
else: print('NO')
problem 1 : 문제 해석 오류, 시간 초과
모든 요소에 i = N-i+1 연산을 진행하는 것으로 착각하였으나, 필요한 요소만 i = N-i+1 연산을 해주면 된다. 모든 i는 i와 N-i+1 두 가지 값만 가질 수 있기 때문에 (*(N-(N-i+1)+1)=i) 해결 될 리 없었다. 매 단계마다 모든 요소의 크기를 바꿔주기 때문에 시간 초과도 따라옴
soltion
1~N의 숫자 중 중간값을 찾아 mid로 정의하고, mid보다 앞에 있는 원소들은 i와 N-i+1 중 min을, 뒤에 있는 원소들은 max를 취하도록 하였다. 시간초과를 해결하기 위해, 한 단계가 진행될 때마다 전 원소와 크기를 비교하여 올바르지 않은 크기 순서가 나타날 경우 바로 return 0을 진행하였다.