[BOJ/백준 10431][C++] 줄세우기

문제

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

백준 10431

 

문제 내용

학생들의 키 순서대로 줄을 세우려고 한다.

결과적으로 오름차순을 만들어야 하지만, 아래 과정을 따라야 한다

1. 먼저 아무나 한 명을 맨 앞 줄에 세운다.
2. 그다음부터는 한 명씩 줄의 맨 뒤에 서며, 매번 아래 과정을 거친다.
3-1. 자기보다 키가 큰 사람이 앞에 없으면 그 자리에 서 있는다.
3-2. 자기 앞에 키 큰 사람이 한 명 이상 있다면, 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다. 이때 A부터 그 뒤의 모든 학생들은 공간을 만들기 위해 한 발씩 뒤로 물러선다.

문제에서 학생들이 총 얼마나 뒤로 물러섰는지를 구하면 된다.

 

문제 풀이

3-2 조건에서, 자기 앞에 키 큰 사람이 한 명 이상 있으면, 그중 가장 앞에 있는 학생 바로 앞에 선다고 되어있다.

하지만 학생 C가 줄에 맨뒤에 섰을 때, 해당 줄은 이미 정렬이 되어있는 상태이다.

어차피 학생 C보다 키가 큰 사람들은 전부 한 발씩 물러나야 하기 때문에, C의 키와 앞사람의 키를 비교해 나가며 swap 시켜도 된다. 

 

코드

#include <iostream>
#include <vector>

using namespace std;

int sorting(vector<int> &arr) {
    int cnt = 0;

    int idx = arr.size() - 1;
    while (idx != 0) {
        if (arr[idx] < arr[idx - 1]) {
            int tmp = arr[idx];
            arr[idx] = arr[idx - 1];
            arr[idx - 1] = tmp;
            idx--;
            cnt++;
        } else {
            return cnt;
        }
    }
    return cnt;
}

void solution() {
    vector<int> arr;
    int cnt = 0;
    int step;
    cin >> step;
    cout << step;
    for (int i = 0; i < 20; i++) {
        int num;
        cin >> num;
        arr.push_back(num);
        cnt += sorting(arr);
    }
    cout << " " << cnt << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solution();
    }
}