[알고리즘풀이]백준 1920 : 수 찾기 JAVA

목차

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

 

 

개요

이번 알고리즘 스터디에서 JAVA를 이용해 백준 1920번 수 찾기를 풀게 되었습니다.

1920번: 수 찾기

 

본문

1) 문제

 

2) 과정

이 문제는 무난하게 40분?만에 풀었던 거 같아요. 지금껏 풀었던 문제들 중에 가장 쉬웠습니다. 문제를 얕보고 단순히 for문 2개를 돌렸더니 시간 초과가 한 번 떴던거 말곤 무난한 난이도였습니다. 

 

코드는 기본 구조인 input, func, output으로 구성했어요. 코드를 짧게 짜는데 집중했다면 아마 30줄 후반까지도 충분히 줄일 수 있을 정도로 그렇게 양이 많진 않습니다.

 

2-1) main

    public static void main(String[] args) throws IOException {
        input();
        func();
        output();
    }

main은 다음과 같습니다. 파라미터도 딱히 없고 차례대로 input, func, output을 불러냅니다.

 

2-2) input

    private static void input() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(reader.readLine());
        String[] strArrN = reader.readLine().split(" ");
        arrAList = new int[n];
        for(int i =0;i<n;i++) arrAList[i]=Integer.parseInt(strArrN[i]);
        Arrays.sort(arrAList);

        m = Integer.parseInt(reader.readLine());
        String[] strArrM = reader.readLine().split(" ");
        arrBList = new int[m];
        for(int i =0;i<m;i++) arrBList[i]=Integer.parseInt(strArrM[i]);

        answer = new int[m];
    }

 

input은 저의 백준 문제들의 인풋 기본! BufferedReader를 사용했습니다. (자세한 내용은 아래 링크 참고)

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

 

첫번째 줄에선 첫 배열의 개수인 n을 받아오고 두번째 줄에선 첫 배열의 값을 가져옵니다.

세번째 줄에선 두번째 배열의 개수인 m을 받아오고 네번째 줄에선 두번째 배열의 값을 가져옵니다.

answer = new int[m];을 통해 정답 배열 (두번째 배열의 인덱스 순으로 n에 존재하면 1, 아니면 0을 담은 배열)을 new해줍니다.

 

2-3) func()

    private static void func(){
        for(int i=0;i<m;i++){
            answer[i]=Arrays.binarySearch(arrAList,arrBList[i])<0?0:1;
        }
    }

for문을 돌며 Arrays 객체가 갖고있는 binarySearch함수를 통해 해당 값이 있으면 answer에 1, 아니면 0을 넣도록 했습니다.

Arrays.binarySearch는 첫번째 파라미터로 대상배열(검색을 할 배열), 두번째 파라미터로 대상값(검색하고자하는 대상)을 넣어줍니다. 그러면 리턴값으로 대상배열(arrAList)에서 대상값(arrBList[i])이 어디에 위치하는지 index값을 리턴합니다. 그리고 정상적인 인덱스가 아닌 음수가 나오면 이는 대상배열에 존재하지 않는다는 것을 의미합니다. 

 이를 이용하여 binarySearch값이 0보다 작으면 0을, 크다면 1을  answer[i]에 넣었습니다.

 

2-4) output

    private static void output() {
        for(int i : answer) System.out.println(i);
    }

그냥 main함수에 포함시켜도 되지만, 조금은 더 깔끔하게 보고싶어서 따로 함수를 만들었습니다. output함수는 answer에 담긴 정답을 줄마다 출력시켜줍니다.

 

3) 전체코드

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

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


public class Main {
    private static int n,m;
    private static int[] arrAList;
    private static int[] arrBList;
    private static int[] answer;

    private static void input() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(reader.readLine());
        String[] strArrN = reader.readLine().split(" ");
        arrAList = new int[n];
        for(int i =0;i<n;i++) arrAList[i]=Integer.parseInt(strArrN[i]);
        Arrays.sort(arrAList);

        m = Integer.parseInt(reader.readLine());
        String[] strArrM = reader.readLine().split(" ");
        arrBList = new int[m];
        for(int i =0;i<m;i++) arrBList[i]=Integer.parseInt(strArrM[i]);

        answer = new int[m];
    }

    private static void func(){
        for(int i=0;i<m;i++){
            answer[i]=Arrays.binarySearch(arrAList,arrBList[i])<0?0:1;
        }
    }

    private static void output() {
        for(int i : answer) System.out.println(i);
    }

    public static void main(String[] args) throws IOException {
        input();
        func();
        output();
    }

}

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

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

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