#include <iostream>
#include <list>
using namespace std;
int main() {
int n; cin >> n;
list<string> words;
for (int i = 0; i < n; i++) {
string k; cin >> k;
bool inserted = false;
bool dup = false;
for (list<string>::iterator iter = words.begin(); iter != words.end(); iter++) {
//중복이면 넘김
if (k == *iter) {
dup = true;
break;
}
//사이즈가 작거나 사이즈가 같을 때 사전순으로 작을 때 삽입
if ((k.size() == iter->size() && k < *iter) || k.size() < iter->size()) {
words.insert(iter, k);
inserted = true;
break;
}
}
//사전순으로 가장 크거나 길이가 가장 길 때 삽입
if (!inserted && !dup) words.insert(words.end(), k);
}
for (list<string>::iterator iter = words.begin(); iter != words.end(); iter++) cout << *iter << endl;
return 0;
}
백준 1181이고
저렇게 하면 시간초과가 뜨는데...
빠른 것 같은데 왜 시간초과가 뜨는지 모르겠음
선형 자료구조 중에서 가장 느려터진 list 쓰고, tie랑 sync_with_stdio 없이 cin/cout 쓰고, 애초에 정렬 알고리즘도 n^2이고, endl 사용하고... 고칠 게 넘 많다.
sync 끄고 endl \n으로 바꾸니 1800ms로 통과가 되긴 했다..
오늘 얘한테 오전 다 썼는데, O(n^2)짜리로는 암만 최적화해도 삽입정렬로도 못 풀어 퀵 소트를 구현하거나 표준 헤더에 들어있는 qsort함수 써
아냐 되긴 됐어ㅋㅋㅋㅋㅋ
퀵소트가 빠르긴 하구나
경험상 c++에서 제공하는 라이브러리로 문제풀때 사용하는 자료구조는 vector, set, map, priority_queue, queue, stack 정도만 해도 끝이라고 배웠어. list는 이중연결리스트인데 나도 이걸로 저번에 풀다가 메모리초과난적이 있었는데 당연한거지만 각각의 개체가 앞뒤 값에 해당하는 포인터랑 자기자신 값을 들고 있어서 자료구조 자체가 존나 무거웠던거임