글 읽기 - 고수님들 시간초과 어떻게 해결할지 방법을 가르쳐주세요!

testtest4 4년 전 0

스택 사용해서 푸는 문제이고 프로그래머스 사이트에 같은 문제가 있고 해결하니 백준에서도 이 문제가 있어서 그대로 사용했는데 시간초과가 나오네요

이거 시간초과를 해결할 방법이 없을까요? 고수님들의 많은 조언 부탁드립니다

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

void solution(vector<int> heights) {
	int answer[500001];
	
	for (int i = heights.size() - 1; i >= 0; i--) {
		for (int j = i-1; j >= 0; j--) {
			if (heights[j] > heights[i]) {
				answer[i] = j + 1;
				break;
			}
		}
	}

	for (int i = 0; i < heights.size();i++) printf("%d ", answer[i]);
}

int main() {
	vector<int> myvec;
	int testcase;
	scanf("%d", &testcase);

	myvec.resize(testcase);
	for (int i = 0; i < testcase; i++) scanf("%d", &myvec[i]);
	solution(myvec);
}

lucian0910 4년 전 1

님이 하신 방법은 스택을 사용한 방법이 아닌 완전 탐색을 이용한 방법입니다. 이때 시간복잡도가 O(N^2)가 나와서 50만 개의 케이스를 가지는 이 문제에서 시간초과가 뜨는 겁니다. 스택을 이용해서 O(N) 내로 풀 수 있는 방법을 찾아야합니다.

testtest4 4년 전 0

@lucian0910

이런 그렇네요.. 다시 풀어야겟네요 조언 감사합니다!

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

문제

문제

출처

ICPC

고수님들 시간초과 어떻게 해결할지 방법을 가르쳐주세요!

testtest4 4년 전 0

lucian0910 4년 전 1

testtest4 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말