백준 10804번 [카드 역배치](C++) -yes6686- 티스토리

백준 문제 풀이: 10804 (카드 역배치)

---

문제 링크: https://www.acmicpc.net/problem/10804

문제 설명:

1부터 20까지의 숫자가 순서대로 나열된 카드가 있습니다. 총 10번의 구간 [a, b]가 주어지며, 각 구간에 대해 해당 카드 순서를 **역순으로 배치**해야 합니다. 최종적으로 바뀐 카드 순서를 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[21]; // 카드 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    // 초기 카드 배열 설정
    for (int i = 1; i <= 20; i++) {
        arr[i] = i;
    }

    // 10번의 구간 역배치
    for (int i = 0; i < 10; i++) {
        int a, b;
        cin >> a >> b; // 구간 [a, b] 입력

        // 역순으로 바꾸기
        int m = (b - a + 1) / 2; // 절반만 교환하면 됨
        for (int j = 0; j < m; j++) {
            int temp = arr[a + j];
            arr[a + j] = arr[b - j];
            arr[b - j] = temp;
        }
    }

    // 최종 카드 순서 출력
    for (int i = 1; i <= 20; i++) {
        cout << arr[i] << ' ';
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 초기 설정: - 배열 arr를 1부터 20까지 초기화합니다.
• 구간 역배치: - 입력으로 받은 구간 [a, b]에 대해 **절반만 순서를 바꾸면 됩니다.** - m = (b - a + 1) / 2: 구간의 길이를 절반으로 나누어 반복 횟수를 결정합니다.
• 교환 과정: - arr[a + j]와 arr[b - j]를 서로 교환합니다.
• 최종 출력: - 1번부터 20번까지 카드의 순서를 출력합니다.

시간 복잡도 분석

• 각 구간에 대해 O((b - a) / 2)의 연산이 수행됩니다.
• 10번의 구간이 주어지므로 전체 시간 복잡도는 **O(10 × (20 / 2)) = O(100)**입니다.
• 입력이 작기 때문에 효율적으로 실행됩니다.

---

결과

10번의 구간 역배치를 수행한 후 카드의 최종 순서를 출력합니다.

• 입력 예시:

  5 10  
  9 13  
  1 8  
  3 7  
  6 15  
  4 10  
  2 12  
  3 9  
  4 8  
  7 15

• 출력 예시:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!