글 읽기 - 용액 시간초과 질문드려요..!

ehdwns2045 2년 전 0

용액문제에서.. 시간초과가 뜹니다..!ㅠㅠ

이래저래 고쳐서 테스트하였더니 78%까지 체점되다가 그 이후에 시간초과가 뜨네요.

오름차순으로 숫자가 입력되는 것을 감안해,

오른쪽 숫자부터 비교하도록 하였고 두 수의 합이 더 작아지지 않는다면 break 로 다음 수를 비교하도록 하였습니다.

그리고 0이 가장 최소값이므로 0이면 바로 정답을 출력하도록 했고..

양쪽 숫자의 합이므로, 이미 방문한 숫자는 빼도록 하였습니다.

시간을 더 줄일 수 있는 방법이 무엇이 있을까요..?

조언 부탁드립니다.^^

											import java.util.Scanner;


public class No_2467 {
	
	public static void main(String[] args) {
		
		Scanner input = new Scanner(System.in);
		
		int N = Integer.parseInt(input.nextLine());
		boolean[] visited = new boolean[N];
		int[] nums = new int[N];
		String[] lines = input.nextLine().split(" ");
		
		for(int i = 0; i < N; i++)
			nums[i] = Integer.parseInt(lines[i]);

		int[] min = new int[3];
		int[] result = new int[3];
		result[0] = Integer.MAX_VALUE;
		
		for(int i = 0; i < N; i++) {
			if(!visited[i]) {
				min[0] = Integer.MAX_VALUE;
				for(int j = N-1; j >= 0; j--) {
					if(i == j)
						continue;
					int num = Math.abs(nums[i] + nums[j]);
					if(num < min[0]) {
						min[0] = num;
						min[1] = nums[i];
						min[2] = nums[j];
						visited[i] = true;
						visited[j] = true;
						
						if(num == 0) {
							printResult(min);
							System.exit(0);
						}
						
					} else {
						break;
					}
				}
				if(min[0] < result[0]) {
					System.arraycopy(min, 0, result, 0, 3);
				}
			}
		}
		printResult(result);
	}
	
	public static void printResult(int[] ret) {
		String result = (ret[1] > ret[2])? ret[2] + " " + ret[1] : ret[1] + " " + ret[2];
		System.out.println(result);
	}
}

										

exqt 2년 전 0

하나를 정하고 이진 검색으로 지금 break 걸리는 부분을 O(logN)에 찾을 수 있습니다.

안쪽 for문을 이진 검색으로 대체하면 O(NlogN) 에 해결 되겠네요.

ehdwns2045 2년 전 0

아! 그렇군요ㅎㅎ
감사합니다.

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

문제

문제

출처

ACM-ICPC

용액 시간초과 질문드려요..!

ehdwns2045 2년 전 0

exqt 2년 전 0

ehdwns2045 2년 전 0

Baekjoon Online Judge

채점 현황

문제

출처

ACM-ICPC

Coder's High

서버 상태

도움말