BOJ 10989 - 수 정렬하기 3

수 정렬하기 3 - 🥉 Bronze 1

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

중복이 가능한 일련의 숫자를 입력받아 정렬하여 출력하는 문제이다. 하지만 메모리 제한이 8MB임을 주의해야하는 문제다.

처음에는 vector에 삽입하여 algorithm을 이용한 오름차순 sort로 시도하였고, multiset에 삽입하여 출력하는 방식으로도 시도하였다. 하지만 2가지 전부 메모리 제한에 걸리는 방식이었다.

이를 해결하기 위해 map을 사용하였다. map에 입력받은 숫자를 key값으로 삽입하고, 이에 대한 value는 중복되는 숫자의 개수로 지정하여 저장하였다.

이에 대한 풀이 코드는 아래와 같다.

풀이 코드

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

int N, input;
map<int, int> sorted;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N;
    // 숫자를 입력받아 map에 저장하여 개수 증가
	while (N--) {
		cin >> input;
		sorted[input]++;
	}
	
    // 해당 개수만큼 반복하여 key값을 출력
	for (auto iter : sorted) {
		for (int i = 0; i < iter.second; i++) {
			cout << iter.first << "\n";
		}
	}
	
	return 0;
}

결과