[BOJ] 1015_수열정렬

수열 정렬

문제 링크: https://www.acmicpc.net/problem/1015

1015번: 수열 정렬

비내림차순 문제에 관한 내용이다.

비내림차순이란?

각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다.
즉, a0 ≥ a1 ≥ a2 ≥ ... 이다.

 

이를 바탕으로 문제를 정리해보자.
예제 입력과 출력을 보면,
3
2 3 1이 입력이 되었다. 그리고 출력은 1 2 0이다.

어떻게 된것인가?

2 3 1 의 배열을 정렬하면 1 2 3이다.
입력된 2 친구는 index상 1번에 위치한다.
입력된 3 친구는 index상 2번에 위치한다.
입력된 1 친구는 index상 0번에 위치한다.

 

이 인덱스의 값을 출력하면 1 2 0이 나온다.

 

나는 이를 보고 배열이 두 개가 필요하다고 생각이 들었다.

하나는 기존 입력된 값을 저장하는 배열 A, 하나는 정렬되어 인덱스를 저장하는 값을 저장하는 배열 B.

하지만 기존 입력된 값이 인덱스를 저장하는 배열요소에 접근할 수 있어야 한다.
그리고 B라는 배열 또한 정렬되기 위해 데이터를 저장하여야 한다.

 

A배열이 필요한 것은 B배열 각각의 요소의 주소를 담을 포인터변수
B배열이 필요한 것은 입력된 값을 저장하는 integer 변수, 인덱스를 저장하는 index 변수가 필요하다.

 

 

이미지를 토대로 각각 클래스로 만들어 배열로 선언해보자.

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

class cpy {
public:
	int cpyN;
	int idx;
};


bool compare(cpy* A, cpy* B) {
    return (A->cpyN < B->cpyN);
}


int main() {

	int N;
	cin >> N;
	cpy** A = new cpy*[N+1];
	cpy** B = new cpy*[N+1];


	for (int i = 0; i < N; i++) {
		cpy *temp = new cpy();
		
		int n;
		cin >> n;

		temp->cpyN = n;
		temp->idx = i;

		B[i] = temp;
		A[i] = temp;

	}

	sort(B, B + N, compare);

	for (int i = 0; i < N; i++) 
		B[i]->idx = i;

	for (int i = 0; i < N; i++) {
		cout << A[i]->idx<< " ";
	}

	return 0;
}

그리고 문제에서 조건이 하나 주어진다.

만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.

이 뜻은 같은 값이 여러개라면 먼저 나온 인덱스 값을 우선으로 출력하라는 의미이다.

 

비교하는데 있어 값이 같을 경우 먼저 입력된 idx를 비교하도록 compare함수를 재정의한다.

 

정답코드

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

class cpy {
public:
	int cpyN;
	int idx;
};


bool compare(cpy* A, cpy* B) {
	if (A->cpyN != B->cpyN)
		return (A->cpyN < B->cpyN);
	else
		return (A->idx < B->idx);
}

int main() {

	int N;
	cin >> N;
	cpy** A = new cpy*[N+1];
	cpy** B = new cpy*[N+1];


	for (int i = 0; i < N; i++) {
		cpy *temp = new cpy();
		
		int n;
		cin >> n;

		temp->cpyN = n;
		temp->idx = i;

		B[i] = temp;
		A[i] = temp;

	}

	sort(B, B + N, compare);

	for (int i = 0; i < N; i++) 
		B[i]->idx = i;

	for (int i = 0; i < N; i++) {
		cout << A[i]->idx<< " ";
	}

	return 0;
}