백준 1181번 - 단어 정렬

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

1181번: 단어 정렬

sort 정렬을 활용하면 된다. 여기서 sort에 주는 함수 인자를 길이를 비교하는 것을 추가해주면 된다.

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
bool comp(string s1, string s2)
{
	if (s1.length() == s2.length())
		return s1 < s2;
	else
		return s1.length() < s2.length();
}

int main()
{
	int N;
	cin >> N;

	string* arr = new string[N];

	for (int i = 0; i < N; i++)
		cin >> arr[i];

	sort(arr, arr + N, comp);
	

	for (int i = 0; i < N; i++)
	{
		for (int j = i+1; j < N; j++)
		{
			if (arr[i] == arr[j])
				arr[j] = "0";
		}
	}
	for (int i = 0; i < N; i++)
	{
		if (arr[i] == "0")
			continue;
		cout << arr[i] << endl;
	}
}

아래에서 두번째 반복문은 중첩되는 걸 없애기 위해 활용했는데, 반복문을 돌리다 보니 O(N^2)이 걸려서 좀 시간이 걸렸다.

이 시간을 줄이기 위해서 그냥

 for(int i=0;i<N;i++){
        if(temp==a[i])continue;
        cout<<a[i]<<'\n';
        temp=a[i];
    }

이렇게 줄이면 시간을 훨씬 단축할 수 있다.

sort함수가 자주 나오는데, 확실히 알아두자.