[알고리즘풀이]백준 3273 : 두 수의 합 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

개요

이번 알고리즘 스터디에서 JAVA를 이용해 백준 3273번 두 수의 합 문제를 풀게 되었습니다.

3273번: 두 수의 합

 

본문

1) 문제

 

 

2) 과정

이 문제도 난이도 있는 편은 아니었습니다. 이것도 30분? 40분 정도 걸렸던 것 같아요.

 

이번엔 다른 문제풀이들과는 달리 코드를 최대한 줄여보았습니다. 그래서 main하나로 코드가 끝이납니다. 

 

2-1) main

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

        n = Integer.parseInt(r.readLine());

        String[] strArrN = r.readLine().split(" ");
        intArr = new int[n];
        for(int i =0;i<n;i++) intArr[i]=Integer.parseInt(strArrN[i]);

        m = Integer.parseInt(r.readLine());

        int index=0;
        Arrays.sort(intArr);
        for(int i=0;i<n;i++) index+=Arrays.binarySearch(intArr,(m-intArr[i]))>=0 ? 1:0;
        System.out.println(index/2);    
    }

main은 다음과 같습니다. 구분을 하자면 m=Integer.parseInt(r.readLine());까지가 입력부분이고, 마지막 System.out.println(index/2);가 출력부분, 그 사이가 로직부분입니다.

 

입력부분 >>

입력부분은 아래 링크를 활용하시면 이해하실 수 있습니다.

[개념정리] System.in / InputStreamReader / BufferedReader 정리

그렇게 배열의 크기를 말하는 n, 배열을 담은 intArr, 배열의 두 값으로 만들어야하는 m을 받아올 수 있었습니다.

 

로직부분 >>

    int ans=0;
    Arrays.sort(intArr);
    for(int i=0;i<n;i++) ans+=Arrays.binarySearch(intArr,(m-intArr[i]))>=0 ? 1:0;

Arrays.sort(intArr)로 뒤죽박죽으로 들어왔을 수도 있는 값을 오름차순으로 정렬합니다.

 

 그리고 Arrays 객체가 갖고있는 binarySearch함수를 통해 해당 값이 있으면 ans에 1, 아니면 0을 더하도록 했습니다.

Arrays.binarySearch는 첫번째 파라미터로 대상배열(검색을 할 배열), 두번째 파라미터로 대상값(검색하고자하는 대상)을 넣어줍니다. 그러면 리턴값으로 대상배열(intArr)에서 대상값(m-intArr[i] , intArr의 현재 인덱스 i와 더해서 m이 나올 값을 찾기 위함)이 어디에 위치하는지 index값을 리턴합니다. 그리고 정상적인 인덱스가 아닌 음수가 나오면 이는 대상배열에 존재하지 않는다는 것을 의미합니다.  이를 이용하여 binarySearch값이 0보다 작으면 0을, 크다면 1을  ans에 더했습니다.

 

출력부분 >>

 

System.out.println(ans/2);

ans는 중복이 허용된 갯수를 의미합니다. 즉, m이 10일때, {1,9}, {2,8}, {8,2), {9,1}이 들어있음을 의미합니다. 그러면 문제의 정답보다 2배 많은 값이 답으로 들어가게 되기 때문에 이를 반으로 나눠 ans/2를 출력해주었습니다.

 

3) 전체코드

그렇게 완성된 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    private static int n,m;
    private static int[] intArr;

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

        n = Integer.parseInt(r.readLine());

        String[] strArrN = r.readLine().split(" ");
        intArr = new int[n];
        for(int i =0;i<n;i++) intArr[i]=Integer.parseInt(strArrN[i]);

        m = Integer.parseInt(r.readLine());

        int ans=0;
        Arrays.sort(intArr);
        for(int i=0;i<n;i++) ans+=Arrays.binarySearch(intArr,(m-intArr[i]))>=0 ? 1:0;
        System.out.println(ans/2);    
    }

}

깃헙으로 더 자세히 보고싶으시다면, 아래 링크를 참고해주세요 :)

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/binarySearch/BOJ3273.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비