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

1. 문제이해

1015번: 수열 정렬 (acmicpc.net)

1015번: 수열 정렬

 

주어진 배열 A에 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는것이 목표이다.

 

 

 

2. 문제풀이

 

일단 문제를 이해하는것부터 난해했던 문제였다.

차라리 긴 예시 과정을 보여줬으면 좋았을텐데..

문제에서, 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 되고, 이때, B[P[i]] = A[i]이다.

주어진 배열 A에 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는것이 문제의 목표이다.

즉, A[i] = B[P[i]] 이고, BP[i]가 비내림차순이 되도록 정리한 후,

정렬된 값들을 B[i]라고 할때, 이때의 P[i]의 값들을 차례로 출력하는 것이 목표이다.

 

문제를 이해하는게 어렵기때문에, 이번에도 간단한 예제 풀이를 준비했다.

(찬찬히 읽어보면 분명 도움이 될거라고 믿습니다.🤭)

 

 

위 예제에서 주어진 배열 A의 길이는 4, 배열의 각 원소의 값은 2, 3, 1, 4 이다.

문제에서 배열 A[i] = B[P[i]]라고 했으므로, B[P[i]]의 element 값에 A[i]의 값을 넣어주었다.

(element와 index가 각각 무엇을 뜻하는지는 그림의 오른쪽 상단 참고)

이후, B[P[i]]를 비내림차순으로 정렬, 이를 B[i]라고 다시 명명하면,

예제에서 B[P[2]] = B[0]이 되고, P[2] = 0 이 된다.

이렇게 나온 P값들을 index 기준으로 다시 비내림차순으로 정렬하면 결과를 구할 수 있다.

즉, 수열 P를 구하는 과정은 다음과 같다.

 

 

1. 배열 A의 값들을 B[P[i]]의 element에 저장

 

2. B[P[i]]를 element 기준 비내림차순으로 정렬

 

3. 정렬된 값(element)들을 B[i]에 저장

 

4. B[i]와 B[P[i]] 값을 비교하여 P[i]의 값 구하기

(P[i]의 element = B[i]의 index, P[i]의 index = B[P[i]]의 index 저장)

 

5. P[i]의 값을 index 기준으로 정렬. 정렬된 element값 출력

 

 

위와 같은 과정을 거쳐, 수열 A를 입력받아 수열 P를 출력하는 것이 목표이다.

여기까지 모두 이해가 되었다면, 코드를 작성하는 일만 남았다.

 

필자는 우선, 수열을 배열이 아닌 class로 선언해주었고,

class 내에 element, index 변수를 두어, 이를 통해 수열들을 선언해주었다.

또한, element, index 값을 기준으로 정렬을 하면서, 다른 값이 변화되지 않게끔

stable sort를 이용하여 정렬을 해주었다.

 

예전에 이와 비슷한 문제인 "나이순 정렬" 을 풀이한 적이 있는데, 해당 문제는 밑의 링크를 참고하자.

https://beginnerdeveloper-lit.tistory.com/11

[C++] 백준 10814번 나이순 정렬

 

이후에는 위 그림과 동일한 과정을 거쳐 결과를 출력했다.

자세한 설명은 아래 소스코드와 함께 보도록 하자.

 

 

 

3. 소스코드

#include <iostream>
#include <algorithm>
using namespace std;

// element, index를 저장하고 있는 class 정의
class arr {		
public:
	int element;
	int index;
};

// element 기준으로 오름차순 정렬하기 위한 함수
bool cmp(arr a, arr b) {	
	return a.element < b.element; 
}

// index 기준으로 오름차순 정렬하기 위한 함수
bool cmp2(arr a, arr b) {	
	return a.index < b.index;
}

int main() {
	int N;
	int A[50];              // 수열 A
	arr* BP = new arr[50];	// 수열 BP
	arr* B = new arr[50];	// 수열 B
	arr* P = new arr[50];	// 수열 P

	// 1. 수열 A의 크기와 각 값들을 입력받음
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	// 2. 수열 A의 값들을 수열 BP의 값(element)에 저장
	//    수열 BP의 위치값(index)은 i와 동일
	for (int i = 0; i < N; i++) {
		BP[i].element = A[i];
		BP[i].index = i;
	}

	// 3. 수열 BP를 element 값 순서대로 오름차순 정렬
	stable_sort(BP, BP + N, cmp);	// element 값 순서대로 오름차순 정렬

	// 4. element값 기준으로 정렬된 수열 BP의 값들을 B의 element에 저장
	//    수열 B의 위치값(index)은 i와 동일
	for (int i = 0; i < N; i++) {
		BP[i].element = B[i].element;
		B[i].index = i;
	}

	// 5. P의 element값에 B의 위치(index)값 저장, P의 위치값은 BP의 위치값과 동일
	for (int i = 0; i < N; i++) {
		P[i].element = B[i].index;
		P[i].index = BP[i].index;
	}

	// 6. 수열 P를 위치값(index) 순서대로 정렬
	stable_sort(P, P + N, cmp2);	// index 값 순서대로 오름차순 정렬

	// 7. 위치 순서대로 정렬된 수열 P의 값(element) 출력
	for (int i = 0; i < N; i++) {
		cout << P[i].element << " ";
	}

	return 0;
}

메인함수에 앞서 먼저 3가지 함수를 선언해주었다.

 

1. class arr 함수

: element와 index 변수를 포함하는 클래스.

배열은 element에 해당하는 값 하나만 저장할 수 있으므로,

class를 통해 index 까지 저장할 수 있도록 하였다.

 

2. bool cmp 함수

: element 기준으로 비내림차순(오름차순) 정렬하는데 필요한 함수

 

3. bool cmp2 함수

: index 기준으로 비내림차순(오름차순) 정렬하는데 필요한 함수

 

위 세가지 힘수를 선언해준 뒤,

메인함수에서 수열 A의 크기(N), 수열 A, class arr 형식의 수열 BP, B, P를 선언한다.

(수열 A는 수열 BP의 element에 값을 복사해주는 용도로만 사용되므로,

따로 class 형식으로 선언하지 않았다.)

이후, 아래 7가지 단계에 맞춰 코드를 구현해주었다. (코드의 주석과 동일)

 

1. 수열 A의 크기와 각 값들을 입력받음

2. 수열 A의 값들을 수열 BP의 값(element)에 저장

3. 수열 BP를 element 값 순서대로 비내림차순(오름차순) 정렬

4. element값 기준으로 정렬된 수열 BP의 값들을 B의 element에 저장

 5. P의 element값에 B의 위치(index)값 저장. P의 위치값은 BP의 위치값과 동일

 6. 수열 P를 위치값(index) 순서대로 정렬

7. 위치 순서대로 정렬된 수열 P의 값(element) 출력

 

 

---

for문이 여러번 사용되어서 시간초과가 나지 않을까 걱정했지만,

다행히도 시간초과가 나지 않았던 문제였다.😌

코드를 구현하는 것보다 문제를 이해하는데 시간이 더 오래걸린 문제기도 했다.🤣

다른분들은 코드를 정말 짧게 구현하신분도 많던데,

포스팅을 마치고 한번 구경하러 가야겠다.😊