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

백준 실버 2 2304 창고 다각형

처음에는 맵이나 배열로 풀어나가려고 했다.
하지만 막히는 느낌이 들었고 힌트를 보니 스택이라 나와있었다.
엥...? 스택?

전에 있던 좌표를 저장하고 꺼내는 역할로 스택을 사용했다.

---

첫번째 접근 - 실패

우선 좌표를 최고점, 최고점 왼쪽, 최고점 오른쪽으로 나누었다.

최고점을 구해서 맨 왼쪽부터 최고점까지 stack을 사용해 현재보다 stack의 top이 더 작을 경우 넓이를 구하고 현재 좌표(x, y)를 stack에 넣는 방식으로 구현했다. (오른쪽도 마찬가지로 오른쪽부터 최고점 오른쪽까지)

하지만 실패하였다. 최고점이 여러개일 경우를 생각하지 못했기 때문.

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

public class Main {
    static class Node{
        int x, y;
        Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bufferedReader.readLine());

        int arr[] = new int[1001];
        String str;
        int max_x = 0, max_y = 0, L, H, max_L = 0, min_L = 1002;
        for(int i=0;i<N;i++){
            str = bufferedReader.readLine();
            L = Integer.parseInt(str.split(" ")[0]);
            H = Integer.parseInt(str.split(" ")[1]);

            arr[L] = H;

            if(max_y < arr[L]){
                max_x = L;
                max_y = arr[L];
            }
            max_L = Math.max(max_L, L);
            min_L = Math.min(min_L, L);
        }

        Stack<Node> stack = new Stack<>();
        int area = max_y; //최고점 넓이

        //최고점 왼쪽
        stack.push(new Node(min_L, arr[min_L]));
        for(int i=min_L+1;i<=max_x;i++){
            if(arr[i] > stack.peek().y){
                area += (i - stack.peek().x) * stack.peek().y;
                stack.pop();
                stack.push(new Node(i, arr[i]));
            }
        }
        stack.clear();

        //최고점 오른쪽
        stack.push(new Node(max_L, arr[max_L]));
        for(int i=max_L-1;i>=max_x;i--){
            if(arr[i] > stack.peek().y){
                area += (stack.peek().x - i) * stack.peek().y;
                stack.pop();
                stack.push(new Node(i, arr[i]));
            }
        }

        System.out.println(area);
    }
}

---

두번째 접근 - 실패

최고점이 여러 개인 경우도 대비해 최고점 사이는 x축이 가장 작은 최고점과 x축이 가장 큰 최고점 사이의 거리를 구하여 높이를 곱해서 넓이를 구했다.

• 어차피 최고점, 최고점 사이에 있는 경우 오목해지기 때문

그리고 최고점 왼쪽과 오른쪽 구분할 때도 최고점이 여러 개면 최고점 사이에서 x축이 가장 작은 것과 x축이 가장 큰 것을 나눠서 저장했다.

하지만 실패. 정말 이유를 모르겠어서 질문게시판도 남겼었다 ㅠㅠ 하지만 너무 어이없었던 실수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class Main {
    static class Node{
        int x, y;
        Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bufferedReader.readLine());

        int arr[] = new int[1001];
        String str;
        int max_y = 0, L, H, max_L = 0, min_L = 1002;

        ArrayList <Integer> arrayList = new ArrayList<>(); //최댓값 여러개일 때 대비

        for(int i=1;i<=N;i++){
            str = bufferedReader.readLine(); //입력
            L = Integer.parseInt(str.split(" ")[0]);
            H = Integer.parseInt(str.split(" ")[1]);

            arr[L] = H;

            if(max_y < arr[L]){ //최고점 찾기
                max_y = arr[L];
                arrayList.clear();
                arrayList.add(L);
            } else if(max_y == arr[L]){
                //최고점 같을 경우
                arrayList.add(L);
            }

            max_L = Math.max(max_L, L); //x축 마지막
            min_L = Math.min(min_L, L); //x축 처음
        }

        Stack<Node> stack = new Stack<>();

        int area; //최고점 넓이
        int len = arrayList.size() - 1;
        if(arrayList.size() >= 2){ //최고점이 여러개일 경우
            area = (arrayList.get(len) - arrayList.get(0) + 1) * max_y; //최고점 중 x축 가장 큰 거에서 가장 작은거 빼고 * 높이
        } else{ //최고점 하나일 경우
            area = max_y;
        }

        //최고점 왼쪽
        stack.push(new Node(min_L, arr[min_L]));
        for(int i=min_L+1;i<=arrayList.get(0);i++){
            if(arr[i] > stack.peek().y){
                area += (i - stack.peek().x) * stack.peek().y;
                stack.pop();
                stack.push(new Node(i, arr[i]));
            }
        }
        stack.clear();

        //최고점 오른쪽
        stack.push(new Node(max_L, arr[max_L]));
        for(int i=max_L-1;i>=arrayList.get(len);i--){
            if(arr[i] > stack.peek().y){
                area += (stack.peek().x - i) * stack.peek().y;
                stack.pop();
                stack.push(new Node(i, arr[i]));
            }
        }
        System.out.println(area);
    }
}

---

3번째 시도 - 성공

흑흑 완전 실수였다.
입력 순서는 좌표 순서가 아니기 때문에
최고점도 x좌표 순서대로 입력되지 않아 정렬을 해줬어야 됐다.
정렬 하나 해주니까 바로 성공

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;

public class Main {
    static class Node{
        int x, y;
        Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bufferedReader.readLine());

        int arr[] = new int[1001];
        String str;
        int max_y = 0, L, H, max_L = 0, min_L = 1002;
        ArrayList <Integer> arrayList = new ArrayList<>(); //최댓값 여러개일 때 대비

        for(int i=1;i<=N;i++){
            str = bufferedReader.readLine(); //입력
            L = Integer.parseInt(str.split(" ")[0]);
            H = Integer.parseInt(str.split(" ")[1]);

            arr[L] = H;

            if(max_y < arr[L]){ //최고점 찾기
                max_y = arr[L];
                arrayList.clear();
                arrayList.add(L);
            } else if(max_y == arr[L]){
                //최고점 같을 경우
                arrayList.add(L);
            }

            max_L = Math.max(max_L, L); //x축 마지막
            min_L = Math.min(min_L, L); //x축 처음
        }

        Stack<Node> stack = new Stack<>();

        int area; //최고점 넓이
        
        Collections.sort(arrayList); // 정렬!!!

        int len = arrayList.size() - 1;
        if(arrayList.size() >= 2){ //최고점이 여러개일 경우
            area = (arrayList.get(len) - arrayList.get(0) + 1) * max_y; //최고점 중 x축 가장 큰 거에서 가장 작은거 빼고 * 높이
        } else{ //최고점 하나일 경우
            area = max_y;
        }

        //최고점 왼쪽
        stack.push(new Node(min_L, arr[min_L]));
        for(int i=min_L+1;i<=arrayList.get(0);i++){
            if(arr[i] > stack.peek().y){
                area += (i - stack.peek().x) * stack.peek().y;
                stack.pop();
                stack.push(new Node(i, arr[i]));
            }
        }
        stack.clear();

        //최고점 오른쪽
        stack.push(new Node(max_L, arr[max_L]));
        for(int i=max_L-1;i>=arrayList.get(len);i--){
            if(arr[i] > stack.peek().y){
                area += (stack.peek().x - i) * stack.peek().y;
                stack.pop();
                stack.push(new Node(i, arr[i]));
            }
        }
        System.out.println(area);
    }
}

---

문제 잘 읽어보기!!!

문제를 보면 어떤 자료구조가 필요한지 아직 잘 감이 안오는 것 같다. ㅠㅠ
그래도 내 코드에서 어떻게든 답 찾아가려고 질문까지 했던건 잘한 것 같다. :D