[C++] 백준 1181번 단어 정렬

1. 문제이해

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

1181번: 단어 정렬

 

N개의 단어가 주어졌을 때, 단어의 길이가 짧은것부터 정렬하는 것이 목표이다.

단, 단어의 길이가 같다면 사전순으로 정렬하며, 같은 단어는 한번만 출력한다.

 

 

 

2. 문제풀이

 

언뜻 보면 단어의 길이만 보고 정렬하면 될것같은 간단한 문제이지만,

몇가지 조건이 더해진 살짝 까다로운 문제이다.

단어의 길이가 같다면 사전순으로 정렬한다는 것과, 같은 단어는 한번만 출력한다는 점이다.

 

단어의 정렬은 기존 C++의 내장함수인 sort 함수를 이용해 길이순으로 정렬하되,

sort(v.begin(), v.end(), compare);  부분 중 compare 부분을 이용해

단어의 길이가 같다면 사전순으로 정렬한다는 점을 추가로 구현하기로 구상했다.

 

같은 단어를 한번만 출력해야 한다는 점은, 단어를 길이순, 사전순으로 모두 정렬한 뒤 구현해주었다.

단어를 모두 정렬한 뒤에는 같은 단어가 앞뒤로 모두 붙어있을 수 밖에 없기 때문에,

출력시 앞뒤 단어가 같다면 해당 부분을 건너뛰도록 구현하기로 했다.

위와 같은 방법을 이용해 구현한 코드는 아래와 같다.

 

 

 

3. 소스코드

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

int cmp(string a, string b) {
	// 1. 길이가 같다면, 사전순으로
	if (a.length() == b.length()) {
		return a < b;
	}
	// 2. 길이가 다르다면, 짧은 순으로 
	else {
		return a.length() < b.length();
	}
}

// 범위가 크기때문에 전역변수로 설정
string word[20000];

int main() {
	int N;

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> word[i];
	}

	sort(word, word + N, cmp);

	for (int i = 0; i < N; i++) {
		// 중복된 경우 한번만 출력
		if (word[i] == word[i - 1]) {
			continue;
		}
		cout << word[i] << "\n";
	}

	return 0;
}

우선 입력받은 단어를 정렬해주는 cmp 함수를 선언해준다.

cmp 함수를 통해 길이가 짧은 순으로 정렬하되, 길이가 같다면 사전순으로 정렬되도록 했다.

 

이후 메인함수에서는 N개의 단어를 입력받고, (word[i])

위에서 선언한 cmp함수를 이용해 해당 단어들을 정렬해주었다.

단어들이 길이순, 사전순으로 정렬된 이후에는 for문을 통해 단어들을 출력해주었다.

단, 중복된 단어들은 한번만 출력해야하기 때문에, 앞 단어와 출력하고자 하는 단어가 같다면,

해당 부분의 단어는 중복되는 것이므로 건너뛰도록 했다.

 

 

---

어제에 이어서 정렬알고리즘 문제를 풀어주었다.

최대한 다양한 유형의 알고리즘을 많이 풀어보도록 해야지😊