백준 알고리즘 1181번: 단어 정렬 [C++]

문제 출처: www.acmicpc.net/problem/1181

1181번: 단어 정렬

1. 코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int cmp(const string& a, const string& b)
{
	if (a.length() == b.length())			//길이가 같다면
		return a < b;						//사전순으로 올림차순
	else
		return a.length() < b.length();		//길이순으로 올림차순
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;

	string* word = new string[n];

	for (int i = 0; i < n; i++)
		cin >> word[i];

	sort(word, word + n, cmp);

	for (int i = 0; i < n; i++)
	{
		cout << word[i] << '\n';
		while (word[i] == word[i + 1]) i++;		//현재 문장과 다음 문자이 같다면 다음 문장으로 접근(중복 방지)
	}

	delete[] word;
	return 0;
}

(실행)

2. 풀이

int n;
cin >> n;

string* word = new string[n];

변수 n을 통해 데이터 케이스 개수를 입력받고 string 포인터 변수를 n만큼 동적 할당한다.

for (int i = 0; i < n; i++)
    cin >> word[i];

n번 문자열을 입력한다.

sort(word, word + n, cmp);

sort함수를 이용하여 word의 순서를 정렬하는데

int cmp(const string& a, const string& b)
{
	if (a.length() == b.length())			//길이가 같다면
		return a < b;						//사전순으로 올림차순
	else
		return a.length() < b.length();		//길이순으로 올림차순
}

문자열의 길이가 같다면 사전 순서를 기준으로 올림차순을 해주고 그렇지 않다면 길이를 기준으로 올림차순으로 정렬해준다.

for (int i = 0; i < n; i++)
{
    cout << word[i] << '\n';
    while (word[i] == word[i + 1]) i++;		//현재 문장과 다음 문장이 같다면 다음 문장으로 접근(중복 방지)
}

그리고 반복문을 이용하여 정렬된 순서로 문자열을 출력하는데 현재의 문장과 다음 문장이 같은지 확인하고 만약 같다면 i의 값을 1 증가시켜서 다음 문자를 접근하게 한다. 문장의 중복을 방지하기 위해서이다.

delete[] word;

그리고 word의 메모리 해제를 해주면 끝이다.

3. 느낀 점

string이 char보다 너무나 사용하기 편해서 좋았다. 그리고 string도 동적 할당이 가능하여 이 문제를 해결하는데 도움이 되었다.