백준 9063 대지[JAVA]

Ga0·2023년 3월 27일
Javaalgorithmbaekjoon백준알고리즘자바코딩
0

baekjoon

목록 보기
9/125
post-thumbnail


문제 해석

  • 문제 자체는 읽고 바로 이해할 수 있을 정도로 쉽게 읽히는 문제이다.
  • 간단하게 문제를 정리하자면, 점(=옥구슬)의 개수(n)개를 입력받아 n개 만큼 점의 좌표를 입력받는다.
  • 입력받은 후에 각각의 점들을 기준 잡아, 점이 둘러싼 면적을 구하면 되는 문제이다.

문제 접근(내방식)

  • 나는 간단하게 생각해서 x좌표의 최솟값과 최댓값, y좌표의 최솟값과 최댓값을 구해서 (x좌표의 최댓값 - x좌표의 최솟값) * (y좌표의 최댓값 - y좌표의 최솟값)을 해주면 면적이 구해지니까 이렇게 풀었다.

코드1

import java.io.*;
import java.util.StringTokenizer;

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());
        StringTokenizer token;

        int[][] axis = new int[n][2]; //x좌표 y좌표 넣는 배열

        for(int i = 0; i < n; i++){
            token = new StringTokenizer(br.readLine());
            for(int j = 0; j < 2; j++){ //x, y좌표니까
                axis[i][j] = Integer.parseInt(token.nextToken());
            }
        }
        br.close();

        int x_min = axis[0][0]; //2차원 배열 마지막 인덱스가 0인 것은 x좌표
        int x_max = axis[0][0];
        int y_min = axis[0][1]; //2차원 배열 마지막 인덱스가 1인 것은 y좌표
        int y_max = axis[0][1];

        //배열의 행의 크기 만큼 반복을 돌려 해당 x, y 좌표의 최소, 최댓값을 구한다.
        for(int i = 0; i < n; i++) {
            if (x_max < axis[i][0]) {
                x_max = axis[i][0];
            }

            if (x_min > axis[i][0]) {
                x_min = axis[i][0];
            }

            if (y_max < axis[i][1]) {
                y_max = axis[i][1];
            }

            if (y_min > axis[i][1]) {
                y_min = axis[i][1];
            }
        }

        System.out.println((x_max-x_min)*(y_max-y_min)); //면적구하기

    }
}

결과1

  • 이렇게 풀었더니,,, 어마무시하게 나왔다... 메모리와 시간이 이렇게까지 나온건 거의 초창기때말고는 처음이다.
  • 그래서, 다른 분들은 어떻게 코드를 작성했는지 알아보려한다!

참고해서 작성한 코드2

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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());

        int x_axis[] = new int[n]; //x좌표 배열 따로
        int y_axis[] = new int[n]; //y좌표 배열 따로

        for(int i  = 0; i < n; i++){
            //어차피 token for문 안에서만 쓰니까
            StringTokenizer token = new StringTokenizer(br.readLine());
            x_axis[i] = Integer.parseInt(token.nextToken());
            y_axis[i] = Integer.parseInt(token.nextToken());
        }
        br.close();
        //작은 수부터 큰 수로 정렬하는 (즉, index가 작으면 작은수, index가 크면 큰 수)
        Arrays.sort(x_axis);
        Arrays.sort(y_axis);

        System.out.println((x_axis[n-1]-x_axis[0])*(y_axis[n-1]-y_axis[0]));
    }
}

결과2

  • 처음 작성한 코드보다 for문이 적게 들어가서 시간이 단축될 것 같다고 생각했지만... 더 느리다(?)
    => 내 생각엔 Array.sort()를 타고들어가면 아래와 같은 반복문이 있다. (아마 이 이유에서 시간 단축의 의미는 없었던 것이 아닌지... 추측)
    private static int getDepth(int parallelism, int size) {
        int depth = 0;

        while ((parallelism >>= 3) > 0 && (size >>= 2) > 0) {
            depth -= 2;
        }
        return depth;
    }
  • 시간을 더 줄여보기 위해서 반복문을 줄이는 방식으로 코드를 작성해보았다.

코드3(틀린코드)

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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());

        int x_axis[] = new int[n]; //x좌표 배열 따로
        int y_axis[] = new int[n]; //y좌표 배열 따로

        int x_min = Integer.MAX_VALUE; //최솟값을 구하기 위해 가장 큰 int형의 값을 넣고 작으면 갱신하는 방식으로
        int x_max = 0; //0으로 설정해두고, 가장 큰 수가 int
        int y_min = Integer.MAX_VALUE;
        int y_max = 0;

        for(int i  = 0; i < n; i++){
            //어차피 token for문 안에서만 쓰니까
            StringTokenizer token = new StringTokenizer(br.readLine());
            x_axis[i] = Integer.parseInt(token.nextToken());
            y_axis[i] = Integer.parseInt(token.nextToken());


            //for문을 최소화로 하기 위해 if문으로 해서 각 x, y의 최솟값을 구했다.
            if(y_axis[i] >  y_max){
                y_max = y_axis[i];
            }

            if(y_axis[i] < y_min){
                y_min = y_axis[i];
            }

            if(x_axis[i] >  x_max){
                x_max = x_axis[i];
            }

            if(x_axis[i] < x_min){
                x_min = x_axis[i];
            }
        }
        br.close();

        System.out.println((x_max-x_min)*(y_max-y_min));
    }
}

결과3

  • 하지만 결과는 틀렸다고 나온다.
  • 이유를 찾았다! 좌표값은 - 값이 나올 수 있는데 +를 가정하고 max = 0으로 지정했던게 문제가 되었던 것이다!

고친 코드3

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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());

        int x_axis[] = new int[n]; //x좌표 배열 따로
        int y_axis[] = new int[n]; //y좌표 배열 따로

        int x_min = Integer.MAX_VALUE; //Integer의 가장 큰 값
        int x_max = Integer.MIN_VALUE; //Integer의 가장 작은 값
        int y_min = Integer.MAX_VALUE; //Integer의 가장 큰 값
        int y_max = Integer.MIN_VALUE; //Integer의 가장 작은 값

        for(int i  = 0; i < n; i++){
            //어차피 token for문 안에서만 쓰니까
            StringTokenizer token = new StringTokenizer(br.readLine());
            x_axis[i] = Integer.parseInt(token.nextToken());
            y_axis[i] = Integer.parseInt(token.nextToken());

            //for문을 최소화로 하기 위해 if문으로 해서 각 x, y의 최솟값을 구했다.
            if(y_axis[i] >  y_max){
                y_max = y_axis[i];
            }

            if(y_axis[i] < y_min){
                y_min = y_axis[i];
            }

            if(x_axis[i] >  x_max){
                x_max = x_axis[i];
            }

            if(x_axis[i] < x_min){
                x_min = x_axis[i];
            }
        }
        br.close();

        System.out.println((x_max-x_min)*(y_max-y_min));
    }
}

결과3

  • for문을 줄이니 메모리는 아주 살짝 줄고 시간도 생각보다 많이 줄었다!

마지막 코드(정답)

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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());

        int x_min = Integer.MAX_VALUE;
        int x_max = Integer.MIN_VALUE;
        int y_min = Integer.MAX_VALUE;
        int y_max = Integer.MIN_VALUE;

        for(int i  = 0; i < n; i++){
            //어차피 token for문 안에서만 쓰니까
            StringTokenizer token = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(token.nextToken());
            int y = Integer.parseInt(token.nextToken());

            //배열에 저장하는 것이 메모리 낭비일 수도 있겠다는 생각!
            if(y >  y_max){
                y_max = y;
            }

            if(y < y_min){
                y_min = y;
            }

            if(x >  x_max){
                x_max = x;
            }

            if(x < x_min){
                x_min = x;
            }
        }
        br.close();

        System.out.println((x_max-x_min)*(y_max-y_min));
    }
}
  • 시간은 앞과 동일하지만, 메모리를 아주 살짝 적게쓴다! (배열에 저장을 하지 않기 때문!!)
  • 그전에, Math클래스에서 제공하는 max함수와 min함수를 쓰기도 해봤지만 if문보다 시간이 많이 소요되기 때문에, 코드 추가는 하지 않기로 했다!

      //배열에 저장하는 것이 메모리 낭비일 수도 있겠다는 생각!
      x_max = Math.max(x_max, x);
      x_min = Math.min(x_min, x);
      y_max = Math.max(y_max, y);
      y_min = Math.min(y_min, y);

결과

  • 맨위가 마지막코드 (if문쓴거)이고 아래가 마지막 코드 if문을 Math클래스의 max()와 min()함수를 쓴 것이다!

느낀점

  • 여러가지 방법으로 시간과 메모리를 줄여볼려고 했지만, 거기서 거기인 느낌으로 끝이 났다.
  • 백준에서 이 문제의 1위분 코드가 아래와 같아서

    1 43845033 2 uhuru0614 12428 120 Java 8 807 10달 전

  • 이해 해보려고 했지만, 다소 생소해서 이해하는데는 시간이 좀 걸릴 것 같다... (아직 부족한 점이 많은 것 같다)
profile
Ga0
이전 포스트

백준 3009 네 번째 점[JAVA]

다음 포스트

백준 10101 삼각형 외우기[JAVA]

0개의 댓글