angs91   1년 전

map과 vector를 처음 써보는데 이렇게 쓰는게 맞나요?

자꾸 시간초과가 뜨네요 ㅠㅠ

어디부분이 시간이 많이 차지하는지 모르겠네요.


코드는 아래와 같습니다.

고수님들의 조언 부탁드리겠습니다.

bupjae   1년 전

map과 vector 사용법은 잘못되지는 않았습니다만...


작성하신 프로그램의 시간복잡도는 O(n log n)입니다.

하지만 이 문제를 시간초과 없이 풀기 위해서는 O(n) 알고리즘이 필요합니다.


jjwdi0   1년 전

우선 std::map은 삽입, 삭제가 O(log n)에 이루어지기는 하나 매우 느리게 작동하고요.

위 코드에서는 특히 string형을 key로 사용해서 더 오래 걸리는 것 같습니다.

저는 입력값이 8자리 정수임을 착안해서 key를 int형으로 선언했습니다. 그러면 O(n log n)으로도 통과하실 수 있을 겁니다.

appa   1년 전

bupjae님이 말씀하신 O(n) 알고리즘이 무엇인지는 잘 모르겠네요.
O(n log n)으로도 충분히 해결 가능합니다.
jjwdi0님이 말씀하신 것도 하나의 요인은 될 수 있지만, 본 프로그램에서 가장 주된 요인은 cin과 cout의 느린 수행 속도 때문입니다.
아래 코드는 300ms로 맞는 코드입니다.
ios::sync_with_stdio를 쓰시면 cin의 속도가 향상되며, cout << ~~~ << endl 보다는 puts( ~~~ )를 하시는 게 훨씬 빠릅니다.
기본적으로 C++ 입출력보다 C의 입출력이 빠르다는 점 참고하시면 되겠습니다.
그럼 string type의 데이터는 어떻게 입력받나 궁금하실 수 있는데,
저는 char buffer[100]={0,} 이런식으로 배열을 잡아 둔 후에, scanf("%s",buffer)를 한 후
string s = "";
for (int i = 0; buffer[i]; i++) s+= buffer[i];
이런 식으로 buffer에 있는 내용을 s에 옮깁니다.

angs91   1년 전

댓글 달아주신분들 너무 감사합니다!

출력만 바꿨을 뿐인데 해결됐습니다.

앞으로 cin cout은 잘 안써야겠어요.

O(n)알고리즘 궁금합니다 ㅠㅠ map을 안써야 되는거죠?

bupjae   1년 전

map은 삽입/삭제 연산이 O(log n) 인데 비해, unordered_map 는 삽입/삭제 연산이 O(1) 입니다.

다만, unordered_map 은 iteration 순서가 정의되어 있지 않으므로 이를 보조하기 위해 list 또는 vector가 필요합니다.

unordered_map 과 (list 또는 vector) 를 조합하면 O(n) 으로 작성이 가능합니다.

angs91   1년 전

감사합니다 꼭 공부해보겠습니다

일단은 이렇게 풀었습니다. 200ms가 나오네요

댓글을 작성하려면 로그인해야 합니다.