[백준/java] 2470번: 두 용액 - 투 포인터

728x90

2470번: 두 용액

 

값을 입력받을 때, 처음에 Scanner를 이용했었다가 시간초과가 4번정도 떴었다.

 

BufferedReader로 바꾼 후에도 시간초과가 뜨길래

 

정렬 방식에서 문제가 있나 싶었다.

 

입력되는 값이 너무 크다보니 범위가 커져서 Arrays.sort()의 경우 최악의 경우는 O(N^2)까지 가는 경우도 있으니

 

ArrayList로 입력을 받아서 Collections.sort()로 정렬하면 수행시간이 O(N log N)이 보장되기 때문에 

 

리스트로 입력받는 방법을 선택했다.

 

반응형

 

그리고 두 포인터 인덱스의 값의 합이 0일 때는 해당 인덱스들을 출력해야하기 때문에

 

두 포인터를 좁혀나가는 로직에서 break를 걸어주어야 한다.

 

package twoPointer;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

/**
 * 
 * @author dyl1912
 *
 *  https://www.acmicpc.net/problem/2470
 *  백준 2470반 두 용액
 * 
 *  Arrays.sort()를 안쓰고 Collections.sort()를 쓴 이유는
 *  Arrays.sort()는 퀵소트 기반으로 정렬을 하는데 최악의 경우 O(n^2)으로 정렬을 하고
 *  Collections.sort()의 경우는 O(NlogN)을 보장하기 때문이다.
 *  
 *  그리고 sum이 0보다 작거나 클때 비교 외에도 sum 값이 0이면 break를 해주어야 한다.
 */

public class P2470_TwoSolution {
	public static void main(String[] args) throws IOException {
		P2470_TwoSolution T = new P2470_TwoSolution();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = stoi(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {
			list.add(stoi(st.nextToken()));
		}
		
		int[] answer = T.solution(list, n);
		bw.write(answer[0] + " " + answer[1]);
		bw.flush();
	}
	
	public static int stoi(String str) {
		return Integer.parseInt(str);
	}
	
	public static int[] solution(ArrayList<Integer> list, int n) {
		int[] answer = new int[2];
		
		Collections.sort(list);
		
		int num = Integer.MAX_VALUE;
		int lt = 0, rt = n-1;
		while(lt < rt) {
			int sum = list.get(lt) + list.get(rt);
			
			if(num > Math.abs(sum)) {
				num = Math.abs(sum);
				answer[0] = list.get(lt);
				answer[1] = list.get(rt);
			}
			
			if(sum > 0) rt--;
			else if(sum < 0) lt++;
			else break;
		}
		
		return answer;
	}
}