ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

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

Posted on Feb 11, 2021 #정렬   #Algorithm  

1181 | 단어 정렬

🙋‍♀️ 문제

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

  1. 길이가 짧은 것부터
  2. 길이가 같으면 사전 순으로

🙌 입출력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

🙋‍♂️ 예제 입출력

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

i
im
it
no
but
more
wait
wont
yours
cannot
hesitate

🚀 코드

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
using namespace std;

class word {
	public:
		string num;
		int len;

		word(string _num) {
			num = _num;
			len = num.length();
		}
};

bool compare(word &a, word &b) {
	if (a.len < b.len)  return true;
	else if (a.len == b.len) { // 길이가 같으면
		if (a.num < b.num) return true;
		else return false;
	}
	else return false;
}

int main() {
	int n;
	cin >> n;
	getchar();
	string num;
	vector<word> v;
	set<string> s; // 중복 여부를 확인할 set
	for (int i = 0; i < n; i++) {
		cin >> num;
		if (s.find(num) == s.end()) {
			v.push_back(word(num));
			s.insert(num);
		}
	}
	sort(v.begin(), v.end(), compare);
	for (int i = 0; i < v.size(); i++) {
		cout << v[i].num << '\n';
	}
	return 0;
}

🌠 메모

이번 문제도 algorithm STL의 sort()를 이용했다. 그러나 중복 여부를 확인하는 부분에서 전체 배열을 모두 확인하느라 시간초과가 났었는데, 이를 해결하기 위해 set을 사용했다.

set 컨테이너는 기본적으로 중복을 허용하지 않는다. 따라서 set에는 따로 중복검사를 하지 않고 insert하고, 알고리즘의 find보다 찾기에 더 최적화되어있는 (더 빠른) set의 find함수를 이용했다.

set의 find는 알고리즘의 find와 마찬가지로 원소를 찾으면 해당 원소를 가리키는 iterator를 반환하고 찾지 못했다면 set.end()를 반환한다.

따라서 s.find(num) == s.end()를 통해 set에 이미 들어있는 값인지를 확인하고 vector에 삽입하도록 한다.



# 카테고리