문제 개요
n개의 요소를 가진 배열 A가 있다고 가정해 보겠습니다. 함수 F(p)는 순열 p에서 인접한 두 요소들의 합을 모두 구한 뒤 오름차순으로 정렬한 배열로 정의됩니다. 즉, F(p) = sort([p₁+p₂, p₂+p₃, ..., pₙ₋₁+pₙ]) 입니다. 배열 A로 표현된 하나의 순열이 주어졌을 때, F(A)의 결과가 원래 배열과 완전히 동일한 다른 순열을 찾아야 합니다.
예시
입력이 A = [2, 1, 6, 5, 4, 3]이라면 출력은 [3, 4, 5, 6, 1, 2]가 될 수 있습니다. 그 이유를 살펴보겠습니다.
- F(A) = sort([2+1, 1+6, 6+5, 5+4, 4+3]) = sort([3, 7, 11, 9, 7]) = [3, 7, 7, 9, 11]
- F([3, 4, 5, 6, 1, 2]) = sort([3+4, 4+5, 5+6, 6+1, 1+2]) = sort([7, 9, 11, 7, 3]) = [3, 7, 7, 9, 11]
두 정렬 결과가 완전히 같으므로 [3, 4, 5, 6, 1, 2]는 조건을 만족하는 유효한 답입니다. 물론 이 외에도 여러 가지 답이 존재할 수 있습니다.
핵심 아이디어
이 문제의 해법은 의외로 간단합니다. 배열을 그대로 뒤집기만 하면 됩니다. 배열을 뒤집으면 인접 요소 합들이 원래 배열의 인접 합들을 역순으로 나열한 것과 같아지므로, 정렬했을 때 결과가 반드시 동일하기 때문입니다. 따라서 복잡한 계산 없이 배열을 역순으로 출력하는 것만으로 O(n) 시간 안에 문제를 해결할 수 있습니다.
알고리즘 단계
이 문제를 해결하기 위해 다음 단계를 따릅니다.
n := size of A for initialize i := n - 1, when i >= 0, update (decrease i by 1), do: print A[i]
C++ 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void solve(vector<int> A) {
int n = A.size();
for (int i = n - 1; i >= 0; i--)
cout << A[i] << ", ";
}
int main() {
vector<int> A = { 2, 1, 6, 5, 4, 3 };
solve(A);
}입력
{ 2, 1, 6, 5, 4, 3 }출력
3, 4, 5, 6, 1, 2,
복잡도 분석
시간 복잡도: O(n) — 배열을 한 번 역순으로 순회하며 출력합니다.
공간 복잡도: O(1) — 추가적인 저장 공간이 필요하지 않습니다.