글 읽기 - 시간초과뜨는데 어딜 개선해야할지 모르겠습니다.

Plorence 4년 전 0

set 컨테이너가 자동정렬 된다는 점을 이용해 원소끝까지 접근해서 출력하고 erase 메서드를 호출하는데, 12%에서 시간초과가 나네요.. 뭐가 문제일까요?

#include <iostream>
#include <set>
int main(void) {
	std::set<int> set = std::set<int>();
	int N = 0;
	//std::ios_base::sync_with_stdio(false);
	//std::cin.tie(NULL);
	//std::cout.tie(NULL);
	std::cin >> N;
	while (N--) {
		int X = 0;
		std::cin >> X;
		if (X == 0) {
			if (set.size() == 0) {
				std::cout << "0\n";
			}
			else {	
				std::set<int>::iterator it = set.begin();
				for (int i = 0; i < set.size()-1; i++) {
					++it;
				}
				std::cout << *it << "\n";
				set.erase(*it);
			}
		}
		else {	
			set.insert(X);
		}
	}
}

djm03178 4년 전 1

원소 처음부터 끝까지 순회하는 과정 자체가 O(N)입니다. 이럴 거면 그냥 배열로 하고 매번 insertion을 하는 것보다 나을 것이 하나도 없습니다.

맨 뒤에 원소에 바로 접근하는 방법으로 rbegin도 있고, end에서 하나를 뺄 수도 있으며, set 자체가 역순으로 저장하게끔 greater를 사용할 수도 있습니다.

Plorence 4년 전 0

알고리즘 자체에 문제가 있나 보네요. 도와주셔서 감사합니다!

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

문제

문제

출처

ICPC

시간초과뜨는데 어딜 개선해야할지 모르겠습니다.

Plorence 4년 전 0

djm03178 4년 전 1

Plorence 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말