백준 1083 c++ "소트" -PlusUltraCode-

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

 

 

[필자 사고]

그리디 알고리즘이다.

필자는 처음 이 문제를 푸는 방식은 바로 옆에 붙어있는 수들만 신경을 썼었다.

그러나 문제를 풀다가 생각해보니 옆에 있는 수만 생각할게 아니라 4번째 수가 첫번째로 올 수도 있구나 같은 생각이 들어 알고리즘을 수정했다. 아직 처음 접하면 바로 푸는 과정을 떠올리기는 쉽지가 않은 문제였다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

2. Input 함수

사용자로부터 숫자의 개수 N을 입력받고, 그다음 N개의 숫자를 입력받아 arr에 저장합니다. 마지막으로 바꿀 수 있는 총 횟수 S를 입력받습니다.

---

3. Swap 함수

배열의 두 인덱스를 받아 해당 위치의 값을 서로 바꿉니다. 간단한 교환 함수입니다.

---

4. Game_Start 함수

이 함수가 핵심 로직입니다. 다음과 같은 절차로 동작합니다:

(1) 배열의 왼쪽부터 한 칸씩 순회하면서

각 위치 i마다 해당 위치에서 시작하여, S번 이내의 거리 안에 있는 숫자 중에서 가장 큰 값을 찾습니다. 그 위치를 maxIdx로 저장합니다.

(2) maxIdx의 값이 현재 위치 i보다 크다면,

가장 큰 값을 현재 위치로 이동시키기 위해, maxIdx에서 i까지 한 칸씩 왼쪽으로 Swap을 반복합니다. 한 번 Swap할 때마다 S를 1 감소시킵니다.

즉, 주어진 횟수 안에서 가장 큰 수를 앞쪽으로 옮기기 위해 버블 정렬식으로 최대값을 앞으로 밀어내는 방식입니다.

(3) S가 0이 되면, 더 이상 교환할 수 없기 때문에 중간에 루프가 제한될 수 있습니다.

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int N, S;
vector<int> arr;

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}

	cin >> S;
}

void Swap(int idx1, int idx2) {
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}

void Game_Start() {
	for (int i = 0; i < N; i++) {
		int maxIdx = i;

		int Scount = 0;
		for (int j = i + 1; j < N; j++ ,Scount++) {
			if (Scount >= S)break;
			if (arr[maxIdx] < arr[j]) {
				maxIdx = j;
			}
		}

		for (int j = maxIdx; j > i; j--) {
			Swap(j, j - 1);
			S--;
		}
	}
	
	for (int i = 0; i < N; i++) {
		cout << arr[i] << " ";
	}

}

int main(void) {
	Input();
	Game_Start();
}