백준 3061번 [사다리](C++) -yes6686- 티스토리

백준 문제 풀이: 3061 [사다리]

---

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

문제 설명:

주어진 배열을 정렬하면서, 인접한 원소의 위치를 교환하는 방식으로 정렬됩니다. 이 과정에서 발생하는 교환 횟수를 출력하는 문제입니다.

문제는 T개의 테스트 케이스로 구성되어 있으며, 각 테스트 케이스마다 n개의 숫자로 이루어진 배열이 주어집니다. 각 테스트 케이스의 배열을 정렬할 때 발생하는 총 교환 횟수를 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[1001]; // 최대 배열 크기

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

    int T; // 테스트 케이스 개수
    cin >> T;

    while (T--) {
        int n; // 배열 크기
        cin >> n;

        // 배열 입력
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }

        int ans = 0; // 교환 횟수
        // 삽입 정렬 알고리즘으로 교환 횟수 계산
        for (int i = 1; i < n; i++) {
            int k = i;
            for (int j = k; j >= 1; j--) {
                if (arr[j] < arr[j - 1]) {
                    // 인접한 두 원소 교환
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    ans++; // 교환 횟수 증가
                }
            }
        }

        // 각 테스트 케이스의 교환 횟수 출력
        cout << ans << '\n';
    }

    return 0;
}

예제 입력:

2
5
5 4 3 2 1
3
1 3 2

예제 출력:

10
1

---

코드 설명

• 핵심 알고리즘: 삽입 정렬 알고리즘을 사용하여 배열을 정렬하면서, 발생한 교환 횟수를 계산합니다.
• 구현 세부사항:
  • 외부 반복문은 배열의 각 원소에 대해 실행됩니다.
  • 내부 반복문은 현재 원소가 올바른 위치에 배치될 때까지 인접한 원소들과 교환합니다.
  • 교환이 발생할 때마다 교환 횟수를 증가시킵니다.
• 시간 복잡도:
  • 최악의 경우 시간 복잡도는 O(n²)입니다(테스트 케이스마다).
  • 최적의 경우(이미 정렬된 배열) 시간 복잡도는 O(n)입니다.

---

결과

각 테스트 케이스에 대해 배열을 정렬하면서 발생한 총 교환 횟수를 출력합니다. 문제는 기본적인 정렬 알고리즘의 구현과 교환 횟수 계산을 연습하는 데 적합합니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!