[백준] 1427번 소트인사이드

 

 

문제

 

소스코드

 

#include<iostream>
#include<queue>
#include<string>
 
int main() {
    std::string s;
    std::priority_queue<char> queue;
    std::cin >> s;
 
    for (int i = 0; i < s.size(); ++i) {
        queue.emplace(s[i]);
    }
 
    while (queue.empty() == false) {
        std::cout << queue.top();
        queue.pop();
    }
}

 

후기

이 문제를 해결하기 위한 키워드는 우선순위 큐이다.

 

일단 이 문제는 각 자리수마다 숫자를 정렬하는 문제이다. 하지만 이렇게 문제를 풀 경우 한가지 난관에 접하게된다.

그 난관은 바로 자릿수문제이다. 한자리 한자리 입력을 받는게 아닌 큰 정수 하나를 받기 때문에 이걸 나눠서 하던지 어떠한 

방법을 사용해서 나눠야 한다. 

그래서 나는 그러한 방법대신에 문자열로 입력을 받고 그 문자열의 문자를 하나씩 우선순위 큐에 넣었다. 

매번 값을 넣을 때마다 정렬을 하는것은 속도에 영향이 가기 때문에 Heap 자료구조를 사용해서 정렬를 할 수 있도록 하였으며

문자도 결국 숫자로 이루어져있기 때문에 정렬을  하면 동일한 결과를 얻을 수 있다.

 

출처 및 레퍼런스

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

 

관련 글

[자료구조 알고리즘/큐(Queue)와 스택(Stack)] - 우선 순위 큐(Priority Queue)

[온라인 코딩/힙(Heap)] - [백준] 1927번 최소 힙

[온라인 코딩/힙(Heap)] - [백준] 11279번 최대 힙

[온라인 코딩/힙(Heap)] - [백준] 11286번 절대값 힙