[BOJ/JAVA&GO] 백준 2467번 : 용액

2467번: 용액

2020.10.20 코드

---

 

• 생각

투 포인터 방식을 사용하면 될 것 같다.

1. 일단 입력 받은 배열을 오름차순 정렬을 통해 왼쪽부터 오른쪽으로 점점 수가 커지게 정렬시킨다.

2. 용액 배열 양쪽에서 다가오면서, 두 개의 합이 0에 가장 가까울 경우 저장해준다.

3. 두 개의 합이 0 보다 작을 경우, 조금 더 0보다 가까운 경우가 있는지 알아보기 위해 왼쪽에서 다가오는 index를 하나 늘려준다.

4. 두 개의 합이 0보다 클 경우, 조금 더 0보다 가까운 경우가 있는지 알아보기 위해 오른쪽에서 다가오는 index를 하나 줄여준다.

 

• 코드

 

import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
    static int[] array;
    static int N, answer1, answer2;
	
	public static void main(String[] args) throws Exception {
		SetData();
		TwoPointer();
		System.out.println(answer1 + " " + answer2);
	}

	// 데이터
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);
		
        N = in.nextInt();
		array = new int[N];
		answer1 = answer2 = 0;

		for (int i = 0; i < N; ++i) {
			array[i] = in.nextInt();
		}
		Arrays.sort(array);
	}

	private static void TwoPointer() {
		int min = Integer.MAX_VALUE;
		int left = 0, right = N - 1;
		
		// 투 포인터
		while (left < right) {
			int sum = array[left] + array[right];

			// v가 최소일 때 특성값 갱신
			if (min > Math.abs(sum)) {
				min = Math.abs(sum);
				answer1 = array[left];
				answer2 = array[right];
			}

			if (sum > 0)
				right--;
			else
				left++;
		}
	}
}

class InputReader {

	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String readString() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

 

 

Retry

2024.1.15 코드

풀이

일단, N개의 입력은 정렬된 상태로 입력이 된다고 주어진다. (-> 굳이 정렬을 할 필요가 없다는 뜻)

 

두 수의 합이 0에 가장 가까운 방법을 찾으면 되기때문에 가장 왼쪽과 가장 오른쪽을 더 해주면서 절대값이 더 큰 값의 index를 왼쪽은 + 1, 오른쪽은 - 1하며 반복하면 된다고 생각했다. 왼쪽 index가 오른쪽 index보다 작을 때까지만!

 

    public static void main(String[] args) throws Exception {
        InputReader in = new InputReader(System.in);

        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = in.nextInt();

        int minimum = 100;
        int al=0, san=0;
        int left = 0, right = n-1;
        while(left < right) {
            int sum = arr[left] + arr[right];
            // 합이 이전 비교보다 0에 가까울 경우
            if(Math.abs(sum) <= minimum) {
                al = arr[left];
                san = arr[right];
                minimum = Math.abs(sum);
            }

            if(Math.abs(arr[left]) <= Math.abs(arr[right])) {
                right--;
            } else {
                left++;
            }
        }
        System.out.println(al + " " + san);
    }

첫 풀이는 위와 같다. 하지만, 27% 정도에서 틀렸습니다.

 

문제를 다시 잘 읽어본 결과 minimum 초기 값이 너무 작아서 틀렸다고 나온 것 같았다. 10억 2개만 있는 경우 더하면 20억이 될 수도 있기때문이다.

    public static void main(String[] args) throws Exception {
        InputReader in = new InputReader(System.in);

        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = in.nextInt();

        int minimum = 2000000001;        // 20억보다 1큰 20억 1로 초기화
        int al=0, san=0;
        int left = 0, right = n-1;
        while(left < right) {
            int sum = arr[left] + arr[right];
            // 합이 이전 비교보다 0에 가까울 경우
            if(Math.abs(sum) <= minimum) {
                al = arr[left];
                san = arr[right];
                minimum = Math.abs(sum);
            }

            if(Math.abs(arr[left]) <= Math.abs(arr[right])) {
                right--;
            } else {
                left++;
            }
        }
        System.out.println(al + " " + san);
    }

위의 코드로 Success!

 

Go 풀이

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

var reader *bufio.Reader = bufio.NewReader(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)

func main() {
	defer writer.Flush()
	var n int
	fmt.Fscan(reader, &n)
	arr := make([]int, n)
	for i := 0; i < n; i++{
		fmt.Fscan(reader, &arr[i])
	}

	minimum := 2000000001
	al := 0
	san := 0
	left := 0
	right := n-1
	for left < right {
		sum := arr[left] + arr[right]
		if(int(math.Abs(float64(sum))) <= minimum) {
			al = arr[left];
			san = arr[right];
			minimum = int(math.Abs(float64(sum)));
		}

		if(int(math.Abs(float64(arr[left]))) <= int(math.Abs(float64(arr[right])))) {
			right--;
		} else {
			left++;
		}
	}
	fmt.Fprintln(writer, al, san)
}

기존 fmt.Scanf혹은 Println을 사용하면 시간 초과가 뜬다. 더 빠르게 입출력을 할 수 있도록 도와주는 라이브러리를 사용해야 한다고 함.

bufio라는 라이브러이고 링크를 보면 도움이 될 것이다.