백준 1427 c++ "소트인사" -PlusUltraCode-

https://www.acmicpc.net/problem/1427

 

[필자 사고]

문자열과 우선순위 큐를 이용하면 쉽게 입력받은 문자열을 내림차순으로 정렬 가능하다.

[코드 해설]

 

• 우선순위 큐 준비
  • 우선순위 큐(priority queue)는 항상 가장 큰 값이 맨 앞에 오도록 자동 정렬되는 자료구조입니다.
  • 따라서 여기에 숫자들을 넣어두면, 꺼낼 때마다 가장 큰 숫자부터 나오게 됩니다.
• 문자열 입력 받기
  • 숫자로 이루어진 문자열을 입력받습니다.
  • 예를 들어 "314159"라는 문자열이 들어왔다고 가정합니다.
• 문자 하나씩 숫자로 변환해서 큐에 넣기
  • 문자열을 한 글자씩 읽습니다.
  • 문자를 정수로 바꾸기 위해 '0'을 빼줍니다.
    • '3' → 3, '1' → 1, '4' → 4 …
  • 이렇게 변환한 숫자들을 차례대로 우선순위 큐에 넣습니다.
• 큰 수부터 꺼내면서 출력하기
  • 큐가 빌 때까지 반복합니다.
  • 매번 큐에서 가장 큰 숫자를 꺼내어 출력합니다.
  • 결과적으로 숫자들이 내림차순으로 차례대로 출력됩니다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int main(void) {
	priority_queue<int, vector<int>> pq;
	string str;
	cin >> str;
	for (int i = 0; i < str.size(); i++) {
		pq.push(str[i] - '0');
	}

	while (!pq.empty()) {
		cout << pq.top();
		pq.pop();
	}
}