백준 2467 (용액) - java

https://www.acmicpc.net/problem/2467

2467번: 용액

투 포인터를 사용하는 문제이다. 주어진 입력의 수가 최대 100,000이기 때문에 이중 반복문을 사용한다면 O(N^2)의 시간 복잡도를 가지기 때문에 시간 초과가 발생하게 된다. 그렇기 때문에 투 포인터를 사용하여 O(N)의 시간 복잡도로 문제를 해결했다. 

left = 0, right = n-1 의 인덱스를 기준으로 board[left] + board[right]의 절댓값이 0에 가까운지를 계속해서 판단하다록 한다.

위의 합 값이 0보다 크다면 right 의 인덱스를 한 칸 아래로 줄이고 0보다 작다면 left의 인덱스를 한 칸 증가시킨다.

 

import java.io.*;
import java.util.*;

public class Main {
    static int n = 0;
    static int rl = -1;
    static int rr = -1;
    static int[] board;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        board = new int[n];

        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0;i<n;i++)
        {
            board[i] = Integer.parseInt(st.nextToken());
        }

        search();

        System.out.println(board[rl] + " " + board[rr]);

        br.close();
    }

    static void search()
    {
        int left = 0;
        int right = n-1;

        while(left < right)
        {
            int sum = board[left] + board[right]; // 현재 위치의 합
            if(sum==0) {
                rl = left;
                rr = right; // 0이라면 결과를 출력
                break;
            }
            // 0보다 작을 경우 합을 키워야 하기 때문에 left 인덱스를 증가
            else if(sum < 0) {
                if (rl == -1 && rr == -1) {
                    rl = left;
                    rr = right;
                } else if (Math.abs(board[rl] + board[rr]) >= Math.abs(sum)) {
                    rl = left;
                    rr = right;
                }
                // 초기화

                left = left + 1;
            }
            // 0보다 크다면 합을 줄여야 하기 때문에 right 인덱스를 감소
            else{
                if(rl==-1&&rr==-1)
                {
                    rl = left;
                    rr = right;
                }

                else if(Math.abs(board[rl]+board[rr]) >= Math.abs(sum))
                {
                    rl = left;
                    rr = right;
                }
                // 초기화

                right = right -1;
            }
        }
    }
}