글 읽기 - 왜틀렸는지 모르겠습니다.(C/C++)

yunbinni 2년 전 0

맞게 한거 같은데,,,

왜

틀렸는지 잘 모르겠습니다.

도와주신다면 감사하겠습니다..!

#include <bits/stdc++.h>
using namespace std;

int n, a[1000004], b[1000004];

int main() {
//	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i];
	
	memset(b, -1, sizeof(b));
	for(int i = 0; i < n - 1; i++) {
		for(int j = i + 1; j < n; j++) {
			if(a[i] < a[j]) {
				b[a[i]] = a[j];
				break;
			}
		}
	}
	
	for(int i = 0; i < n; i++) {
		cout << b[a[i]] << " ";
	}
	
	return 0;
}

dustkd1004 2년 전 1

16, 23줄에서 b[a[i]]가 아니라 b[i]로 바꿔야합니다.

근데 이렇게 바꿔도 시간초과가 발생해요. 위 알고리즘 시간 복잡도는 O(n^2)인데 n이 최대 백만이기 때문에 최악의 경우 1조번 연산해야합니다.

따라서 시간초과가 발생하는 것이 당연하죠.

시간복잡도를 줄이는 다른 방법을 한번 생각해보세요

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

문제

문제

출처

ICPC

왜틀렸는지 모르겠습니다.(C/C++)

yunbinni 2년 전 0

dustkd1004 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말