[백준] 1181번 - 단어 정렬

www.acmicpc.net

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

문제

💡

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

길이가 짧은 것부터

길이가 같으면 사전 순으로

단, 중복된 단어는 하나만 남기고 제거해야 한다.

시간 제한: 2초

메모리 제한: 256MB

입력

💡

첫째 줄에 단어의 개수 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

풀이

배열에 문자열을 저장하고, 우선순위대로 정렬하면 되는 간단한 문제이다. 먼저 길이를 비교하고, 같으면 알파벳 우선순위를 비교한다. 같은 문자열은 삭제시키는 조건이 있어, 비교함수에서 따로 구현할 필요는 없다.

원소의 정렬과 중복제거가 필요하므로 set 자료구조가 적절하다. 또한, 대소관계가 다소 복잡하므로 비교용 함수객체를 만들어 사용했다.

코드


#include <iostream>
#include <set>

using namespace std;
struct comp {
	bool operator()(const string& a, const string& b) const {
		if (a.size() == b.size()) {
			for (int i = 0; i < a.size(); ++i) {
				if (a[i] == b[i]) continue;
				return a[i] < b[i];
			}
			return false;
		}
		return a.size() < b.size();
	};
};


int main() {
	int N;
	cin >> N;
	set<string, comp> arr;
	for (int i = 0; i < N; ++i) {
		string input;
		cin >> input;
		arr.insert(input);
	}

	for (const string& str : arr) {
		cout << str << "\n";
	}

	return 0;
}

후기

문제 자체는 정렬만 사용하면 되는 간단한 문제라 넘기려 했지만, 좋은 풀이를 찾은것 같아 작성했다. 처음에 vector를 사용해 문자열을 저장했는데, 중복을 제거하는 과정에서 시간복잡도를 더 줄일 수 있는 방법이 있지 않을까 생각해 다른 자료구조를 찾아보았다. hash가 먼저 떠올랐지만 정렬이 불가능했고, 검색해 보니 set이라는 적절한 자료구조가 있었다.

set은 기본적으로 중복을 허용하지 않는 자료구조이며 삽입삭제 시 PQ처럼 정렬을 수행한다. 탐색 속도는 logN으로 vector와 비교해 빠르진 않지만 쓸만했고, 이번 문제는 정렬과 중복제거가 필요해 vector보다 잘어울린다고 생각했다.

다른 사람의 풀이도 살펴보았다. 그중 눈에 띈 부분은 comp함수 부분인데, 나는 문자열의 각 자리를 하나 씩 비교해야 정확한 비교가 가능하다고 생각했는데 string의 operator에 이미 오버로딩 되있다는 것을 알았다. 어차피 비교 전 삽입 과정에서 중복은 제거되므로, 인덱스를 사용하는 방식을 수정하면 더 좋았을것 같다.


struct comp {
	bool operator()(const string& a, const string& b) const {
		if (a.size() == b.size()) {
			return a < b;
		}
		return a.size() < b.size();
	};
};

이러면 코드가 더욱 깔끔해진다.

또한, 대소문자를 구분하는 조건을 대비해 해결 방법을 찾아보니, std::transform과 ::tolower이라는 함수를 알게 되었다.

transform은 배열 범위에서 일련의 작업을 수행하고, ::tolower는 C의 함수인데 문자를 소문자로 수정한다.

두 함수를 응용해 다음과 같이 문자열을 소문자로 변경할 수 있다.


vector<int> array = {a, b, c, d, e};
std::transform(array.begin(), array.end(), array.begin(), ::tolower);
//             시작 지점       끝 지점   결과를 덮어 쓸 범위    행위

::tolower의 반대로 ::toupper도 있다.

새롭게 알게 된 transform은 행위로 ::tolower 말고도 사용자정의 함수도 사용할 수 있다고 하니 다른 문제에서 응용 해봐야야겠다.