[Python] 20309. 트리플 소트

처음 풀이

n = int(input())
numbers = list(enumerate(map(int, input().split())))   # (인덱스, 숫자) 같이 저장
numbers.sort(key=lambda x: x[1])    # 숫자 기준으로 정렬

is_even = True  # 홀수 순서, 짝수 순서 판별
for idx, num in numbers:
    if (idx % 2 and is_even) or (not idx % 2 and not is_even): # 인덱스가 홀수인데 짝수 순서이거나, 인덱스가 짝수인데 홀수 순서라면
        print('NO') # 정렬 불가능
        break

    is_even = not is_even

else:
    print('YES')

 

위의 풀이는 (인덱스, 숫자)를 같이 저장하고 정렬해서 해당 인덱스가 맞는 순서(짝수 / 홀수)인지 판별했는데,
생각하고 보니 정렬할 필요가 없었다. 어차피 숫자는 홀수 순번 자리는 홀수 순번끼리, 짝수 순번 자리는 짝수 순번끼리 자리를 바꾸므로
짝수 순번 자리에 모두 짝수 숫자가 오고, 홀수 순번 자리에 모두 홀수 숫자가 오면 된다. 

따라서 아래와 같이 코드가 개선되었다 !

개선된 풀이 

n = int(input())    # 배열의 크기
numbers = list(map(int, input().split()))   # 배열의 원소
for i in range(n):
    # 짝수번째 값이 모두 짝수여야 정렬 가능
    if i % 2:   # 짝수 자리라면 (0부터 시작하므로 사실상 짝수 자리)
        if numbers[i] % 2:  # 근데 원소가 홀수라면
            print('NO') # 정렬 불가능
            exit()
else:
    print('YES')    # 그 외는 정렬 가능