글 읽기 - 두 용액 문제 시간초과좀 봐주세여 ㅠㅠ

hos921019 5년 전 0

제가 생각한 while 문의 시간복잡도는 O(N) 인데 혹시 잘못되었나요??

#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
//ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ//
int a[100001];
int main(void)
{
	int N; scanf("%d", &N);
	for (int i = 0; i < N; i++) scanf("%d", a + i);
	sort(a, a + N);
	int left = 0, right = N - 1, al = 0, ar = 0;
	lld ans = 1e20+6;
	while (left < right && left < N && right >= 0)
	{
		lld sum = a[left] + a[right];
		if (abs(sum) < ans)
		{
			al = left, ar = right, ans = abs(sum);
		}
		if (sum > 0)
		{
			right -= 1;
		}
		else if (sum < 0)
		{
			left += 1;
		}
	}
	printf("%d %d", a[al], a[ar]);
}

djm03178 5년 전 0

sum이 정확히 0이면 어떻게 될까요?

hos921019 5년 전 0

와.. 감사합니다!... 대단하시네요.. 어떻게 바로 보자마자 예외케이스가 나오시는지.. 연습만이 답인가요 ...ㅠㅠ

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

문제

문제

출처

ICPC

두 용액 문제 시간초과좀 봐주세여 ㅠㅠ

hos921019 5년 전 0

djm03178 5년 전 0

hos921019 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말