[알고리즘풀이]백준 7795 : 먹을 것인가 먹힐 것인가 JAVA

목차

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

 

 

개요

이번 알고리즘 스터디에서 JAVA를 이용해 백준 7795번 먹을 것인가 먹힐 것인가를 풀게 되었습니다.

7795번: 먹을 것인가 먹힐 것인가

 

본문

1) 문제

 

 

2) 과정

이것도 꽤나 쉽게? 한 30분?40분 걸려 풀어낸 문제라 난이도가 그리 높은 문제는 아니였습니다.

 

코드는 이번에는 조금 긴 input, 중요로직인 func, 출력을 담당하는 output으로 구성하였습니다.

 

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));
        T = Integer.parseInt(reader.readLine());
        answer = new int[T];

        arrList = new Vector<int[]>();
        for(int j =0;j<T;j++){
            String[] strArrFirst = reader.readLine().split(" ");
            int n = Integer.parseInt(strArrFirst[0]);
            int m = Integer.parseInt(strArrFirst[1]);
            int[] intArrNM = new int[]{n,m};
            arrList.add(intArrNM);

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

            String[] strArrThird = reader.readLine().split(" ");
            int[] intArrB = new int[m];
            for(int i =0;i<m;i++) intArrB[i]=Integer.parseInt(strArrThird[i]);
            Arrays.sort(intArrB);
            arrList.add(intArrB);
        }
    }

 

읽어오는 것 관련된 정보는 아래 링크를 확인해주세요 :)

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

첫번째 줄을 읽어 테스트 케이스의 수를 T에 저장합니다. 이후 for문을 돌며 첫번째 배열의 수와 두번째 배열의 수를 int[]를 저장하는 Vector에 넣고, 첫번째 배열과 두번째 배열을 오름차순 정렬하고 vector에 넣어 저장하길 T번 반복합니다.

 

input을 굳이 안나누고 for문으로 진행했다면 아마 해당 문제의 코드 수나 메모리 수는 더 줄어들었을테지만 시각적으로 보기 좋게 나누기 위해 input에서 입력받은 모든 값을 vector<int[]>f로 저장했습니다.

 

2-3) func()

   private static void func(){
        for(int i=0;i<T;i++){
            int[] intArrNM= arrList.get((i * 3));
            int[] intArrA= arrList.get(1 + (i*3));
            int[] intArrB= arrList.get(2 + (i*3));

            int num=0;
            for(int A : intArrA){
                for(int B : intArrB){
                    if(A<=B) break;
                    else num++;
                }
            }
            answer[i]=num;
        }
    }

input에서 저장한 값들이 회전수와 비례하여 각각 3*i , 3*i+1, 3*i+2의 위치에 있단 것을 이용하여 intArrNM (n과 m값을 담은 배열), intArrA (첫번째 배열), intArrB(두번째 배열)을 사용하기 좋게 가져옵니다. 그리고 intArrA 속에서 intArrB를 돌리며 첫번째 배열의 값이 두번째 배열의 값보다 큰지 비교해 잡아먹을 수 있다면 num을 1씩 증가시키고, 첫번째 배열의 값이 두번째 배열의 값보다 작아지게 되면(오름차순 정렬한 것을 이용) 이를 멈춰 불필요한 반복을 줄였습니다.

 

그리고 for문을 모두 마치면 T에 따라 첫 배열에서 두번째 배열을 잡아먹을 수 있는 쌍의 개수를 출력해야하기 때문에 answer이란 배열을 이용해 잡아먹은 횟수(num)을 저장해줍니다.

 

2-4) output()

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

func에서 저장한 answer값을 하나씩 출력해줍니다.

 

3) 전체코드

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

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

public class Main {
    private static int T;
    private static Vector<int[]> arrList;
    private static int[] answer;

    private static void input() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(reader.readLine());
        answer = new int[T];

        arrList = new Vector<int[]>();
        for(int j =0;j<T;j++){
            String[] strArrFirst = reader.readLine().split(" ");
            int n = Integer.parseInt(strArrFirst[0]);
            int m = Integer.parseInt(strArrFirst[1]);
            int[] intArrNM = new int[]{n,m};
            arrList.add(intArrNM);

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

            String[] strArrThird = reader.readLine().split(" ");
            int[] intArrB = new int[m];
            for(int i =0;i<m;i++) intArrB[i]=Integer.parseInt(strArrThird[i]);
            Arrays.sort(intArrB);
            arrList.add(intArrB);
        }
    }

    private static void func(){
        for(int i=0;i<T;i++){
            int[] intArrNM= arrList.get((i * 3));
            int[] intArrA= arrList.get(1 + (i*3));
            int[] intArrB= arrList.get(2 + (i*3));

            int num=0;
            for(int A : intArrA){
                for(int B : intArrB){
                    if(A<=B) break;
                    else num++;
                }
            }
            answer[i]=num;
        }
    }

    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/BOJ7795.java

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