[Miracle Baekjoon] 2일차 - 2751번 수 정렬하기 2 - C++

시작하며

 

 오늘은 미라클 백준 2일 차입니다. 이제 비록 2일 차지만 매일매일 문제 푸는 건 생각보다 쉽지 않은 일이라는 것을 느꼈습니다. 오늘은 수업 중간중간 짬짬이 시간을 내서 문제를 하나 풀어봤습니다. 그리고 앞으로는 썸네일을 가능하면 한번 직접 그려보려고 합니다. 그림판에서 마우스로 그리기 때문에 퀄리티는 낮지만 ai 그림 생성으로는 제가 원하는 구도가 안 나오기 때문에 그리기로 했습니다. 감사합니다.

---

수 정렬하기 2

 

Illustrated by Yongjun

 

 

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

---

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

---

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

예제 입력 1

5 5 4 3 2 1

 

예제 출력 1

1 2 3 4 5

---

문제풀이

 

 이번 문제는 약간의 고민이 필요한 문제였습니다. 다행히도 전에 비슷한 문제를 하나 풀어봐서 문제 푸는데 많은 도움이 되었습니다. - 수 정렬하기 3 - 음의 백만부터 양의 백만까지의 넓은 수 범위를 최대 백만 개까지 받아야 하는 문제입니다. 이렇게 많은 수를 배열에 담고 이를 정렬하는 것은 너무 많은 시간과 비용이 듭니다. 그래서 저는 양의 100만까지의 수를 담을 배열과, 음의 100만까지의 수를 담을 배열을 만들고 어떤 수가 입력 되었었는지 아니었는지만 기록하여 작은 수부터 만약 기록되었다면 출력하고 기록되지 않았으면 출력하지 않는 방식으로 정렬하여 출력하기로 결정했습니다.

#include <iostream>
using namespace std;

int main(void){
    bool mincnt[1000001]={};
    bool plucnt[1000001]={};

    int N,temp;
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>temp;
        if(temp<0)
        {
            mincnt[-temp]=1;
        }
        else
        {
            plucnt[temp]=1;
        }
    }
    for(int i=1000000;i>0;i--)
    {
        if(mincnt[i]==1)
        {
            cout<<-i<<endl;
        }
    }
    for(int i=0;i<1000001;i++)
    {
        if(plucnt[i]==1)
        {
            cout<<i<<endl;
        }
    }
    return 0;
}

 

 하지만 이 코드는 틀렸습니다. 메모리는 넘지 않았지만 시간이 초과되었기 때문입니다. cout과 endl은 printf와 \n에 비해 시간이 오래 걸리므로 이것을 바꾸어 주었더니 해결되었습니다.

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

int main(void){
    bool mincnt[1000001]={};    //마이너스 100만부터 -1까지의 수를 확인
    bool plucnt[1000001]={};    //0부터 100만까지의 수를 확인

    int N,temp;
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>temp;
        if(temp<0)    //입력이 음수라면 마이너스 배열에 체크
        {
            mincnt[-temp]=1;    //입력이 음수이므로 -temp인덱스에 체크
        }
        else    //양수라면 플러스 배열에 체크
        {
            plucnt[temp]=1;
        }
    }
    for(int i=1000000;i>0;i--)    //마이너스 100만부터 -1까지의 수중에서
    {                             //체크된 인덱스를 출력한다.
        if(mincnt[i]==1)
        {
            printf("%d\n",-i);    //마이너스이므로 -붙여서 출력
        }
    }
    for(int i=0;i<1000001;i++)    //0부터 100만까지의 수중에서
    {                             //체크된 인덱스를 출력한다.
        if(plucnt[i]==1)
        {
            printf("%d\n",i);
        }
    }
    return 0;
}

 

마치며

 

 이번 문제는 제가 수 정렬하기 3을 먼저 풀어봤었기 때문에 쉽게 풀었지만 처음 수 정렬하기 3을 푸는데 시간이 조금 걸렸던 것을 생각하면 조금 어려웠던 것 같습니다. 역시 수학과 문제를 푸는 창의력이 중요한 것 같습니다. 오늘도 읽어주셔서 감사합니다.