2023.2.26.(목)

문제

problem

접근 방법

조건이 참 까다롭습니다.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

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

일단 길이가 짧은 순서대로 정렬을 해주는 것이 좋겠습니다. 따라서 벡터에 pair, 즉 <int, string> 형태로 입력된 자료들을 넣어줄 것입니다. 문자열의 길이와 문자열 쌍을 벡터에 하나씩 넣어주는 것입니다.

이 상태에서 <algorithm> 라이브러리에 들어 있는 sort 함수를 사용하여 벡터를 정렬하여 줍니다. 정렬은 pair의 first를 기준으로 정렬됩니다. 만약 두 번째 값인 second를 기준으로 정렬하고 싶다면, 정렬 함수를 따로 만든 후에 sort 함수에 넣어주어야 합니다.

<int, int> 의 pair v를 예로 들어 설명해 볼게요.

* first를 기준으로 정렬할 때

bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
   return a.first < b.first; 
}

* second를 기준으로 정렬할 때

bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
   return a.second < b.second;
}

마지막으로 sort(v.begin(), v.end(), cmp); 를 해주면 됩니다. pair <int, string> 을 sort 하면 처음에는 int 를 기준으로 정렬이 됩니다. int 가 같을 때는 string 을 기준으로 정렬이 되는 듯합니다.

벡터를 문자열의 길이를 기준으로 정렬해 주었다면, 이번에는 3번 조건인 단, 중복된 단어는 하나만 남기고 제거해야 한다. 라는 조건을 만족해 주어야 합니다. 우리는 여기에서 erase 함수와 <algorithm> 라이브러리에 들어 있는 unique함수와 사용할 것입니다.

순서대로 1, 2, 1, 3, 2, 1, 2 가 들어 있는 벡터에 unique 함수를 적용하면 아무런 변화가 일어나지 않습니다. 즉, 벡터를 먼저 sort 를 해 준 후에 unique 함수를 적용해 주어야 합니다. sort 함수를 적용하면 벡터에는 1, 1, 1, 2, 2, 2, 3 이 차례대로 남게 됩니다. 이 상태에서 unique(v.begin(), v.end())를 해줍니다.

unique 함수의 정확한 원리는: whipbaek.log: c++ unique() 함수에 관하여 를 확인해 주세요!

unique 함수를 적용하였다면, 중복되는 수들의 첫번째 값을 포인터로 받게 됩니다. 이 포인터부터 벡터의 마지막 포인터 전까지에 중복된 수들이 들어 있는 거에요. 이때 erase 함수를 적용하여 중복된 이 수들을 모두 지워 주어야 합니다. v.erase(unique(v.start(), v.end()), v.end()) 이렇게 말이죠.

이렇게 sort 된 벡터를 unique 함수와 erase 함수를 써서 문제를 해결할 수 있었습니다!

코드

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

int main(){

	int N; 
	cin >> N; 

	vector< pair<int, string> > strList; 
	string str; 

	for (int i = 0; i < N; i++) {
		cin >> str; 
		strList.push_back(make_pair(str.length(),str)); 
	}

	sort(strList.begin(), strList.end());
	strList.erase(unique(strList.begin(), strList.end()), strList.end()); 

	for (int i = 0; i < strList.size(); i++) {
		cout << strList[i].second << endl; 
	}

	return 0;
}