[ 백준 1083 ] 소트 (C++) - 그리디

---

🔗 문제 링크

https://www.acmicpc.net/problem/1083

---

💡 문제 풀이 및 해석

1. 배열의 크기가 최대 50이므로 항상 최대로 옮긴다고 해도 50 * 49 / 2 밖에 되지 않는다. 완전탐색, 그리디 방식으로 풀 수 있다는 뜻이다.
2. 문제 풀이 순서도는 다음과 같다.
   2-1. 기회가 끝나거나(S == 0) 모두 정렬(left == right)이 될때까지 반복한다.
   2-2. 옮길 수 있는 기회만큼(left_index + S) 탐색한다. 단, 탐색이 N을 넘어가는 순간 멈춘다.
   2-3. 탐색한 범위에서 가장 큰 숫자의 위치와 left_index의 위치를 교환한다. 그만큼 기회를 차감한다.
   2-4. 교환을 한 뒤에는 다음으로 정렬하는 위치를 옮겨준다. (left_index + 1)

---

⭐️ 정답 코드 및 설명

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int N, S;
vector<int> A;

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        A.push_back(num);
    }
    cin >> S;
}

void change(int left_index, int right_index) {
    for (int i = right_index; i > left_index; i--) {
        int temp = A[i];
        A[i] = A[i - 1];
        A[i - 1] = temp;
    }
}

void sol() {
    int left_index = 0;
    while (S > 0) {
        int MAX = -1, right_index = left_index;
        if (left_index == N) break;
        for (int i = left_index; i <= left_index + S; i++) {
            if (i >= N) break;
            if (A[i] > MAX) {
                MAX = A[i];
                right_index = i;
            }
        }
        if (left_index == right_index) {
            left_index++;
            continue;
        } else {
            change(left_index, right_index);
            S -= right_index - left_index;
        }
        left_index++;
    }
}

int main() {
    input();
    sol();
    for (int i : A) {
        cout << i << " ";
    }

    return 0;
}

---

🤔 문제 후기

그닥 어려운 문제는 아니였는데, 처음에 옮길 수 있는 기회가 N-left_index 보다 크냐 작냐로 나눠서 했었는데, 그러면 너무 복잡해졌다. 그래서 결국 두 경우를 하나로 합치고, if (i >= N) break; 을 추가했다. 그리고 left_index == right_index 일 때, 다음 탐색 위치로 넘어갔어야 했는데, 그냥 continue만 해놓고 무한반복이 풀리지 않아서 원인을 찾느라 조금 시간이 걸렸던 문제였던 것 같다.