백준 1181번 (단어 정렬, C++) [BAEKJOON]

단어 정렬

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

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초256 MB123599513783834940.167%

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터

2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000)

둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다.

주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다.

단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

예제 입력 1

13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

예제 출력 1

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

출처

  • 문제를 만든 사람: author5

알고리즘 분류


입력받은 단어를 아래의 기준으로 정렬하는 문제

1. 길이가 짧은 것부터

2. 길이가 같으면 사전 순으로

map과 multimap의 성질을 이용하여 해결하였습니다.

통과된 코드

#include <iostream>
#include <map>

using namespace std;

map<string, int> myMap;

multimap<int, string> mMap;

string str;

int n;

int main()
{
	ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
	// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	// map에 넣어서 중복된 단어를 제거하고
	// 알파벳 순으로 정렬 합니다. (map의 성질)
	// key = string, value = int 
	for (int i = 0; i < n; i++) {
		cin >> str;
		myMap.insert(make_pair(str, str.length()));
	}

	// multimap에 넣어 숫자가 같으면 들어온 순서대로 입력됩니다.
	// key = int (multimap은 중복 허용), value = string
	for (auto it = myMap.begin(); it != myMap.end(); it++) {
		mMap.insert(make_pair(it->second, it->first));
	}

	for (auto it = mMap.begin(); it != mMap.end(); it++) {
		cout << it->second << "\n";
	}
	return 0;
}

정렬 기준을 반대로 해서 틀림

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

Scroll to Top