[알고리즘 풀이] 1181번 | 단어 정렬 | c++

문제 보기

 

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

 

무작위 단어들을 입력받고, 글자 수 오름차로 정렬 후, 알파벳 순서로 중복 제거 후 출력하는 문제입니다.

 

---

들어가며

저번에 풀어둔 것 중 한 가지인 단어정렬입니다. 

이것도 sort 써서 해서 좀 쉽긴 하나, 그래도 기록 겸 블로그를 씁니다.

실버 V 문제에서 푼 사람 많은 순으로 감이 잡히는 것들 해봤는데

어찌 다 정렬 문제네요.

 

---

 

코드 풀이

 

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

int main() {
	int count;
	cin >> count;
	vector<vector<string>> arr(51);
	for (int i = 0;i < count;++i) {
		string str;
		cin >> str;
		arr[str.size()].push_back(str);
	}
	string before="";
	for (vector<string> vec : arr) {
		sort(vec.begin(), vec.end());
		for (string str : vec) {
			if (before == str) continue;
			before = str;
			cout << str << endl;
		}
	}
}

우선 전체 코드입니다.

이후 하나하나 뜯어보며 코드의 구조를 알아보겠습니다.

---

int count;
cin >> count;
vector<vector<string>> arr(51);
for (int i = 0;i < count;++i) {
	string str;
	cin >> str;
	arr[str.size()].push_back(str);
}

count 변수에 받을 문자열의 개수를 받아옵니다.

이후 string으로 이중백터를 선언해 주는데, 행의 개수를 51개로 선언해 줍니다.

for문 안을 보면 알겠지만, 행의 인덱스가 곧 문자열의 문자 개수가 되는 겁니다.

이렇게 된다면 입력을 받는 동시에 첫 번째 조건인 문자 개수 조건은 자연스럽게 해결되는 겁니다.

이 코드에서 볼 점은 이게 다인 거 같습니다.

 

---

string before="";
for (vector<string> vec : arr) {
	sort(vec.begin(), vec.end());
	for (string str : vec) {
		if (before == str) continue;
		before = str;
		cout << str << endl;
	}
}

이후 코드입니다.

before이라는 이름으로 string 변수를 만들어둡니다. 나중에 설명할 거지만,

중복을 제거하는 데 사용할 변수입니다. for문으로 이중백터를 돌려 글자열 0개부터 51개까지

담은 백터를 한 개씩 가져옵니다. 이후 sort함수로 가져온 vec을 돌려주면 알파벳순으로

자동으로 정렬해 줍니다.

정렬한 vec을 for문으로 한번 더 돌려주면 정렬된 순서대로 문자열이 나와줍니다.

출력하기 전에 before에 담아주고 before랑 지금 출력할 것을 비교해서

같다면 중복이니 출력하지 않고 그대로 넘어가 줍니다.

이렇게 하면 조건을 모두 충족하고 효율? 적이게 코드를 짤 수 있습니다.

---

마치며

진짜 sort로 해서 쉬웠는데 인덱스로 행을 만들어서 좀 편하게? 빠르게? 해봤습니다.

sort로 너무 딸깍으로 하는 거 같아 뭔가 찔리긴 하지만 좋습니다.