[백준/C++] 1083번. 소트

문제

1083번: 소트

---

1. 첫 번째 풀이

사고 과정

- 시간 제한은 널널한 편. 배열을 전부 검사해보고 큰 수를 한 칸 전진시켜도 충분한 시간이다.

- 예제들로 살펴보면, 앞에서부터 검사하며 뒤의 수가 더 클 때 자리를 교환하면 될 것 같다.

- 하지만 굳이 사전순으로 뒷선다고 조건을 건 걸 보면, 배열 내 원소의 자릿수가 다른 경우도 감안해야 할 것 같다.

- 자릿수가 같다면 그냥 큰 수를 올리면 된다. 96과 89면 96이 앞서면 된다. 하지만 919와 99라면, 99가 작은 수임에도 앞서야 한다.

- 따라서 수의 맨 앞자리 부터 두 수를 비교해야 하므로, int보다 string이 더 적합해보인다.

- 자릿수가 다를 경우, 다양한 예외가 발생한다.

- 예를 들어, 123 1231231은 교환하면 안 되고, 123 1231234는 교환해야 한다.

- 더 짧은 쪽은 끝에 도달 시 처음으로 돌아가서 비교, 반복 횟수는 긴 쪽을 기준으로 하면 될 것 같다.

 

1. 배열을 문자열 배열로 받는다.
2. 배열의 맨 앞부터, 두 수를 비교한다.
   1. 두 수의 순서 비교는 긴 쪽의 수를 기준으로 한다. 맨 앞자리부터 비교하되, 짧은 수가 끝나면 다시 처음으로 돌아가 긴 쪽의 다음 수와 비교한다.
3. 두 수가 swap해야 하는 수라면 swap한다.

- 말로 설명하려니 약간 어려운데, 코드를 보자.

 

코드

#include <iostream>
#include <vector>

bool isReversed(std::string str1, std::string str2) {
	// str1이 더 짧다고 가정
	if (str1.length() > str2.length()) {
		return isReversed(str2, str1);
	}

	/*
	* 수가 123 1231234일 경우 swap해야 하지만, 123 1231231일 경우 안 해야 한다.
	* 따라서 str2을 전부 검사하되, str1이 끝나면 처음으로 돌아간다.
	*/ 
	int j = 0;
	for (int i = 0; i < str2.length(); i++, j++) {
		if (j == str1.length()) {
			j = 0;
		}

		if (str1[j] > str2[i]) {
			return false;
		}
		else if (str1[j] < str2[i]) {
			return true;
		}
	}

	// 바꿔도 결과가 같다면 바꾸지 않는다.
	return false;
}

int main() {
	// 입력
	int n;
	std::cin >> n;

	std::vector<std::string> nums(n, "");

	for (int i = 0; i < n; i++) {
		std::cin >> nums[i];
	}

	int s;
	std::cin >> s;

	// 계산
	while (s--) {
		for (int i = 0; i < n - 1; i++) {
			if (isReversed(nums[i], nums[i + 1])) {
				std::swap(nums[i], nums[i + 1]);
				break;
			}
		}
	}

	// 출력
	for (int i = 0; i < n; i++) {
		std::cout << nums[i] << " ";
	}

	return 0;
}

 

결과

결과는 실패.

---

2. 두 번째 풀이

사고 과정

- 예제에서 문제가 생기진 않았는데, 아마 출력의 끝에 공백이 들어가서 그런 걸까?

- 출력 끝의 공백 문자를 제거해보자.

 

코드

#include <iostream>
#include <vector>

bool isReversed(std::string str1, std::string str2) {
	// str1이 더 짧다고 가정
	if (str1.size() > str2.size()) {
		return isReversed(str2, str1);
	}

	/*
	* 수가 123 1231234일 경우 swap해야 하지만, 123 1231231일 경우 안 해야 한다.
	* 따라서 str2을 전부 검사하되, str1이 끝나면 처음으로 돌아간다.
	*/ 
	int j = 0;
	for (int i = 0; i < str2.size(); i++, j++) {
		if (j == str1.size()) {
			j = 0;
		}

		if (str1[j] > str2[i]) {
			return false;
		}
		else if (str1[j] < str2[i]) {
			return true;
		}
	}

	// 바꿔도 결과가 같다면 바꾸지 않는다.
	return false;
}

int main() {
	// 입력
	int n;
	std::cin >> n;

	std::vector<std::string> nums(n, "");

	for (int i = 0; i < n; i++) {
		std::cin >> nums[i];
	}

	int s;
	std::cin >> s;

	// 계산
	while (s--) {
		for (int i = 0; i < n - 1; i++) {
			if (isReversed(nums[i], nums[i + 1])) {
				std::swap(nums[i], nums[i + 1]);
				break;
			}
		}
	}

	// 출력
	for (int i = 0; i < n - 1; i++) {
		std::cout << nums[i] << " ";
	}
	std::cout << nums[nums.size() - 1];

	return 0;
}

 

결과

아쉽게도 그런 문제가 아니었다.

---

3. 세 번째 풀이

사고 과정

- 여기서 상당히 많이 헤멨는데, 질문 게시판에서 반례를 찾다가 뭔가를 발견했다. 다른 사람들은 int로 두 수를 비교만 했다는 것.

- 그래서 설마...? 하는 마음으로 코드를 넣어봤다.

 

코드

#include <iostream>
#include <vector>

int main() {
	// 입력
	int n;
	std::cin >> n;

	std::vector<int> nums(n, 0);

	for (int i = 0; i < n; i++) {
		std::cin >> nums[i];
	}

	int s;
	std::cin >> s;

	// 계산
	while (s--) {
		for (int i = 0; i < n - 1; i++) {
			if (nums[i] < nums[i + 1]) {
				std::swap(nums[i], nums[i + 1]);
				break;
			}
		}
	}

	// 출력
	for (int i = 0; i < n - 1; i++) {
		std::cout << nums[i] << " ";
	}
	std::cout << nums[nums.size() - 1];

	return 0;
}

간단히 테스트해보자.

 

결과

이것도 아니었다.

---

4. 마지막 풀이

사고 과정

- 드디어 반례를 찾았다.

5

5 3 4 7 2

2

의 경우, 5 7 3 4 2가 나와야 한다.

- 즉, 앞쪽부터 검사했던 게 문제였던 것.

- 그럼 최댓값을 찾아 s만큼 땡겨오고, 남으면 또 탐색하는 알고리즘이 필요해보인다. 세 번째 풀이처럼 int로 수를 먼저 비교해보자.

- s번만 땡길 수 있으니, 앞에서 s + 1개의 원소만 비교해야 한다.

- 땡겨온 후엔 해당 수를 제외하고, 범위를 재설정해 s가 0이 될 때까지 반복한다.

 

코드

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

int main() {
	// 입력
	int n;
	std::cin >> n;

	std::vector<int> nums(n, 0);

	for (int i = 0; i < n; i++) {
		std::cin >> nums[i];
	}

	int s;
	std::cin >> s;

	// 계산
	int start = 0, end = s;
	while (start < nums.size() && s > 0) {
		if (end >= nums.size()) {
			end = nums.size() - 1;
		}

		int max_index = std::max_element(nums.begin() + start, nums.begin() + end + 1) - nums.begin();
		
		// 최댓값을 맨 앞으로 땡겨온다.
		while (max_index > start) {
			std::swap(nums[max_index], nums[max_index - 1]);
			max_index--; s--;
		}

		// 범위 재설정
		start++; end = start + s;
	}

	// 출력
	for (int i = 0; i < n - 1; i++) {
		std::cout << nums[i] << " ";
	}
	std::cout << nums[nums.size() - 1];

	return 0;
}

이번엔 됐으면 좋겠다.

 

결과

드디어 성공했다.

---

개선

사고 과정

- 하지만 여전히 의문은 남았다. 이 코드는 원소를 숫자로 보고, 자릿수가 같아야 성립한다. 하지만 문제엔 자릿수가 같다는 가정이 없다.

- 처음 생각했던 string으로 보고 한 자리씩 비교하는 게 더 정확해보이지만, 그 경우 최댓값을 구하는 데서 문제가 생긴다. 따라서 지금은 이 코드가 최선이다.

- 어쩌면 내가 문제 이해를 잘못한 건 아닐까?

---

가장 효율적인 코드

https://www.acmicpc.net/source/16394986

noxnia님의 코드. 동일하게 최댓값을 탐색한 후 땡겨오는 로직이다.

 

내 코드와 비교

- 나는 swap을 모든 순간 실행했고, 그때마다 s를 1씩 줄였다.

- 하지만 이 분은 s는 한 번에, start부터 max_index까지의 거리만큼 줄인 후, 배열을 한 칸씩 밀고 앞에 집어넣었다.

- 나보단 확실히 연산량이 줄어들었다.

---

강평

문제 이해에서 발목잡힌 문제. 사전 순으로 뒷선다는 말에 꽂혀 string으로 시작했고, 최댓값을 찾아 땡겨온다는 로직을 생각하지 못 했다. 사실 아직도 이게 맞는 코드인지 모르겠다. 9보다 29가 앞서니까. 그래도 가장 단순한 방법이 수 비교였으므로, 가장 단순한 방법부터 생각해보지 못한 점에 반성하자.