[Java] 브루트 포스 (창고 다각형)

https://www.acmicpc.net/problem/2304

2304번: 창고 다각형

 

받아온 x, y 좌표를 클래스 Point로 ArrayList에 저장 후 x좌표를 기준으로 오름차순 정렬한 후에

가장 큰 y 좌표 max_y를 기준으로 왼쪽의 넓이 + 오른쪽의 넓이 + max_y로 풀었다.

 

처음에 반례 가장 큰 y좌표가 여러 개인 경우를 생각 못해서 7번이나 틀렸음.

-> 만약 좌표가 (1,3) (2,3) (3,2) (4,3) 이런 식으로 온다면 틀린 답을 도출했다.

 

따라서 처음에는 왼쪽의 넓이를 구할 때 for문을 max_y의 x좌표까지 돌렸었는데 왼쪽 넓이와 오른쪽 넓이를 구하는 for문을 처음부터 끝까지 돌리고, 오른쪽 넓이를 구할 때 조건문에서 현재 y좌표와 같을 때에도 true로 바꾸어 주었더니 성공했음.

 

끝나고 정석 풀이를 보니 스택을 사용해서 했던데 나는 잘 모르겠다.

 

 

 

 

 

class Point{
    public int x;
    public int y;

    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main {

    public static int N, x, y, max_y=0, max_y_index=0;
    public static int result, now_x, now_y;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        ArrayList<Point> points = new ArrayList<>();

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());

            if(y>=max_y) max_y=y; //y좌표 최댓값 찾기

            points.add(new Point(x,y));
        }

        Collections.sort(points, new Comparator<Point>() { //x 좌표 순으로 정렬
            @Override
            public int compare(Point o1, Point o2) {
                return o1.x -o2.x;
            }
        });

        for(int i=0; i<N; i++){
            if(points.get(i).y == max_y) max_y_index=i; //arraylist에서 y좌표가 최대인 index 찾기
        }

        result=0;
        now_y=points.get(0).y; //현재 최고 높이
        now_x=points.get(0).x; //현재 최고 높이의 x좌표

        for(int i=1; i<N; i++){ //앞에서 부터 max_y 까지

            if(points.get(i).y > now_y) {
                result+= (now_y* (points.get(i).x - now_x));
                now_x = points.get(i).x;
                now_y = points.get(i).y;
            }
        }

        now_y=points.get(N-1).y;
        now_x=points.get(N-1).x;

        for(int i=N-2; i>-1; i--){ //뒤에서 부터 max_y 까지

            if(points.get(i).y >= now_y) {

                result+= (now_y* (now_x-points.get(i).x ));
                now_x = points.get(i).x;
                now_y = points.get(i).y;
            }
        }

         System.out.println(result+max_y);
    }
}