BOJ 10804 - 카드 역배치

문제

1부터 20까지의 카드가 순서대로 놓여있을 때, 주어진 10개의 구간을 차례로 뒤집은 후 최종 배열을 출력하라.

입력

10줄에 걸쳐 뒤집을 구간의 시작과 끝이 주어진다.

출력

최종 카드 배열을 공백으로 구분하여 출력한다.

예제

입력	출력
`5 10` `9 13` `...`	`1 2 ... 20`

풀이

배열을 초기화하고 10번의 구간 뒤집기를 수행한다.

배열을 {1, 2, ..., 20}으로 초기화한다
10번의 구간 [s, e]를 입력받는다
양 끝에서 안쪽으로 이동하며 swap으로 구간을 뒤집는다
최종 배열을 출력한다

핵심 아이디어: 크기가 20으로 고정이므로 각 뒤집기를 투 포인터로 O(구간 크기)에 수행하면 된다.

코드

#include <iostream>
using namespace std;
int arr[21];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
 
  for (int i = 1; i < 21; i++)
  {
    arr[i] = i;
  }
 
  for (int i = 0; i < 10; i++)
  {
    int s, e, a, b;
    cin >> s >> e;
    a = s;
    b = e;
    for (int j = 0; j < (e - s + 1) / 2; j++)
    {
      swap(arr[a++], arr[b--]);
    }
  }
 
  for (int i = 1; i < 21; i++)
  {
    cout << arr[i] << " ";
  }
  return 0;
}

복잡도

시간: O(1) (최대 10 * 20 = 고정 크기)
공간: O(1)

문제