[백준/C++] 1015번. 수열 정렬

문제

1015번: 수열 정렬

---

1. 첫 번째 풀이

사고 과정

- 설명을 이래저래 돌려놨지만, 결국 가장 작은 수부터 0, 1, 2, ..., N-1을 대입한다는 소리

- 가장 간단한 방법은 min_element를 사용하는 것이다.

 

1. 배열 A, P를 생성한다.

2. 정수 i, c = 0을 선언한다.

2. 배열 A를 입력받는다.

3. A 내에서 min_element를 적용, 최솟값의 인덱스 i를 얻는다..

4. P[i]에 c를 대입하고 c를 1 증가시킨다.

5. A[i]를 1,001로 변경한다. (혹은 -1로 변경하고, max_element를 이용한다.)

 

코드

#include <stdio.h>
#include <vector>
#include <algorithm>

int main() {
	int n, i, c = 0;
	scanf("%d", &n);

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

	// 배열 A 입력
	for (i = 0; i < n; i++) {
		scanf("%d", &A[i]);
	}
	
	// 핵심 로직
	while (n--) {
		i = min_element(A.begin(), A.end()) - A.begin();
		P[i] = c++;
		A[i] = 1001;
	}

	// 출력
	for (auto iter : P) {
		printf("%d ", iter);
	}
}

 

결과

printf에서 숫자와 공백을 같이 출력해서 틀리지 않을까 걱정했는데, 다행히 성공했다.

---

2. 두 번째 풀이 (마지막 풀이)

사고 과정

- 위 방법은 단순하고 직관적이지만, min_element가 실행 시마다 N번 실행된다는 단점이 있다. 즉, 이 코드의 시간복잡도는 O(n^2)이다.

- 이를 O(n)으로 끝낼 수 있을 것 같다. 어떻게 할 수 있을까?

- 우선 O(nlogn)으로 끝내는 방법은, A의 인덱스와 값을 pair로 연결한 후 정렬하는 것(stable하게). 이후 P에 대입하면 빠르게 풀 수 있다.

- n번으로 끝내는 방법이 있을까? 이는 곧, A[i]의 원소가 몇 번째로 큰 원소인지 한 번에 알아내야 한다는 뜻이다. 두 값을 일일히 비교하는 방법으론 O(n)의 시간복잡도는 불가능하다.

- 그렇다면 Counting Sort는 어떨까?

- 기본적으로 크기 1,000의 배열이 필요하다. 같은 값이 중복될 수 있으니, 2차원 벡터로 구성해야 할 것이다. 그리고 배열을 처음부터 순회하며 P[i]를 구성한다면 가능할 것이다.

- 벡터의 크기가 큰 게 걸리지만, 시도해볼 가치는 있다.

 

코드

#include <stdio.h>
#include <vector>
#include <algorithm>

int main() {
	int n, c = 0;
	scanf("%d", &n);
	std::vector<int> A(n, 0), P(n, 0);
	std::vector<std::vector<int>> count(1001, std::vector<int>());

	// 배열 A 입력
	for (int i = 0; i < n; i++) {
		scanf("%d", &A[i]);
	}

	// Count에 대입
	for (int i = 0; i < n; i++) {
		count[A[i]].push_back(i);
	}

	// Count에 기반하여 P 생성
	for (auto vec : count) {
		for (auto i : vec) {
			P[i] = c++;
		}
	}

	// 출력
	for (auto i : P) {
		printf("%d ", i);
	}
}

 

결과

메모리 사용량이나 시간은 변화가 없다. 사실 둘 다 0 ms라 딱히 비교가 안 된다... 하지만 count 배열을 생성하는데 n번, count 배열을 전부 순회하지만, P[i] = c++이 n번 실행되니, 전체 코드의 시간복잡도를 O(n)이라고 볼 수 있을 것이다.

---

가장 효율적인 코드

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

choyi0521님의 코드. 짧은 코드와 적은 메모리 사용량이 인상적이다.

 

내 코드와 비교

위 코드는 배열 A를 입력받으며, 동시에 배열 B를 생성한다. 방법은 아래와 같다.

 

1. A[i]에 입력받는다. (여기선 a+i로 주소를 직접 지정)

2. 0부터 i까지 순회, 둘 중 큰 값을 1 증가시킨다.

2-1. 예를 들어 A[0] = 3, A[1] = 2라면, A[0] > A[1]이므로 B[0]을 1 증가시킨다. 그럼 B[0] = 1, B[1] = 0이 된다. 입력이 2 3 1이라면 B는 1 2 0이 된다.

 

이 알고리즘을 사용하면 A를 입력받음과 동시에 B가 생성되므로, 전체적인 프로세스가 줄어든다.

---

강평

사실 비교해본 알고리즘은 두 번째 풀이 때 생각해 본 것이었다. 다만 난 이때 시간복잡도에만 신경을 썼기 때문에, 첫 번째 풀이에 비하면 연산량은 줄어들지만 O(n^2)인 해당 알고리즘은 생각하지 않았다.

하지만 위 방법을 사용하면 입력과 풀이를 통합할 수 있고, 추가 메모리도 필요하지 않다. 무엇보다 코드가 매우 간결해진다.

단순한(?) 정렬 문제였지만, 여러 방법으로 풀어보는 재미가 있었다. 그리고 Counting Sort를 써볼 수 있어 좋았다.