[백준 2751번 수 정렬하기 2 / C++]

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

‘2750번- 수 정렬하기’와 동일한 방식으로 풀기가 가능하다.

 

하지만 스터디에서 배웠던 counting sort방식으로 문제를 풀어보고 싶었다 헤헤😉

수의 범위를 설정하는 것에 있어서 주의가 필요했다. 수에 절대값을 주었을 때 1000000을 넘지 않는다고 했으니 이 -1000000~1000000의 범위를 고려해야했다.

 

그렇기 때문에 counting sort에 사용할 배열의 크기를 2000001로 설정했다.

후에 입력값을 받으면서 입력값+1000000을 해주어 음수의 범위까지 배열에 담을 수 있도록 하였다.

후에 처음부터 끝까지 수가 있는 곳의 인덱스-1000000를 해주어 출력해주었다.

 

 

code 🌱

#include <iostream>
using namespace std;
bool num[2000001];
int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, number;
    cin >> N;

    while (N--) {
        cin >> number;
        num[number + 1000000] = true;
    }

    for (int i = 0; i <= 2000000; i++) {
        if (num[i]) {
            cout << i - 1000000 << "\n";
        }
    }

    return 0;
}