백준 28065번: SW 수열 구하기 [python]

난이도 : 실버 4
유형 : 해 구성하기
출처 : https://www.acmicpc.net/problem/28065

문제 요약

길이 N의 수열 A를 1..N의 서로 다른 정수로 구성하되,
인접 차들의 절댓값 |A[i+1]-A[i]| (i=1..N-1) 이 모두 서로 다르고, 결과적으로 1..N-1의 어떤 순열이 되도록 하는 수열(= SW 수열)을 하나 출력하라.
즉, 아무거나 하나만 맞게 만들면 정답.

핵심 아이디어(구성)

두 포인터 L=1, R=N을 두고 작은 수, 큰 수를 번갈아 배치하면 된다.

예)

• N=4 → [1, 4, 2, 3]
  • 차이: 3, 2, 1 → 서로 다르고 {1,2,3} 완성

이렇게 배치하면 인접 차가
(R-L), (R-(L+1)), (R-1-(L+1)), ... 가 되어
N-1, N-2, ..., 1 처럼 중복 없이 모든 값이 한 번씩 등장한다.
따라서 SW 수열 조건을 만족.

1. L=1, R=N으로 시작

2. L<R인 동안 L, R을 순서대로 넣고 L+=1, R-=1

3. 홀수 길이라면 마지막에 L==R이 되므로 그 값 하나 추가

   위와 같은 “양끝에서 안쪽으로” 채우기만으로 정답 수열을 만들 수 있다. 구현도 O(N).

해답 및 풀이

import sys
input = sys.stdin.readline

n = int(input().strip())
L, R = 1, n
ans = []

while L < R:
    ans.append(L)
    ans.append(R)
    L += 1
    R -= 1

if L == R:  # n이 홀수일 때 가운데 하나 남음
    ans.append(L)

print(*ans)