[Python/Java] 백준 2470 - 두 용액 [투 포인터]

문제

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

 

해설

완전 탐색으로 풀었을 때 시간초과가 발생하였다. 투 포인터라는 개념을 적용시켜 성능을 개선시킬 수 있었다.

 

Python

1차 시도(실패)

완전 탐색으로 풀이하여 시간 초과가 발생하였다.

 

from sys import stdin


def solution(N: int, lst: list):
    current_sum = abs(max(lst))

    lst = sorted(lst)
	result = [lst[0], lst[-1]]

	for l1 in lst:
        for l2 in lst[::-1]:
            if l1 != l2:
                new_sum = abs(l1+l2)
                if new_sum < current_sum:
                    current_sum = new_sum
                    result = [str(l1), str(l2)]
    print(" ".join(result))


n = int(stdin.readline())
material = list(map(int, stdin.readline().split(" ")))
solution(n, material)

 

2차 시도(성공)

투 포인터 알고리즘을 적용하였다.

 

from sys import stdin


def solution(N: int, lst: list):
    start = 0
    end = N - 1
    lst.sort()

    result = [lst[start], lst[end]]
    current_sum = abs(sum(result))

    while start < end:
        new_sum = lst[start] + lst[end]
        if abs(new_sum) < current_sum:
            current_sum = abs(new_sum)
            result = [lst[start], lst[end]]
            if current_sum == 0:
                break

        if new_sum < 0:
            start += 1
        else:
            end -= 1
    print(result[0], result[1])


n = int(stdin.readline())
materials = list(map(int, stdin.readline().split(" ")))
solution(n, materials)

 

Java

import java.io.*;
import java.util.*;
import java.lang.Math;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String[] materialInput = br.readLine().split(" ");
        
        List<Integer> material = new ArrayList<>();
        for(String c : materialInput){
            material.add(Integer.parseInt(c));
        }

        Collections.sort(material);
        int start = 0;
        int end = n - 1;
        
        List<Integer> result = List.of(material.get(start), material.get(end));
        int current_sum = Math.abs(result.stream().mapToInt(Integer::intValue).sum());
        int new_sum = 0;

        while(start < end){
            new_sum = material.get(start) + material.get(end);
            if(Math.abs(new_sum) < current_sum){
                current_sum = Math.abs(new_sum);
                result = List.of(material.get(start), material.get(end));
            }

            if(new_sum < 0){ start++; }
            else{ end--; }
        }

        System.out.println(result.get(0) + " " + result.get(1));
    }
}