[ Baekjoon - 10/03 ] - 2304번: 창고 다각형

• 문제 링크 : https://www.acmicpc.net/problem/2304

2304번: 창고 다각형

 

• 소요 시간 : 1시간

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 2초
     • 메모리 : 128MB
   • 문제
     • N개의 막대기둥(1≤N≤1,000), 기둥의 왼쪽면의 위치(1≤L≤1,000), 기둥 높이(1≤H≤1,000)
     • 지붕이 기둥을 전부 감싸면서, 중간에 오목하게 들어간 부분없이 딱 맞게 설계할때 창고의 면적을 구하는 문제 
   • 이해
     • 문제가 자세하게 설명되어 있어 크게 이해가 어렵진 않았다. 다만, 창고의 면적에 기둥이 포함된건지 아닌지를 바로 알기 어려워 조금 계산을 해서 이해했다.
2. 문제를 익숙한 용어로 재정의와 추상화
   • 문제에서 그림까지 잘 그려줘서 그려보지 않고 문제 이해는 가능했다.
3. 문제를 어떻게 해결할 것인가
   •  문제에서 그림을 주었지만.. 문제를 해결할 방법을 찾기위해선 그려봐야했다...(ㅜㅜ)

   

   • 문제예시는 기둥이 7개이지만, 시작점기준으로 높아질때 낮아질때 그리고 끝점 기준으로 높아질때 낮아질때만 고려하면 될것같아 5개만 그려보았다.
   • 1st 접근 - 시작점과 끝점 포인터를 잡아 동시에 움직이면 어떨까 )
     • 시작점과 끝점을 각각 기준으로 잡고 높은 기둥이 나타날때 낮은 기둥이 나타날때를 분석해보았다.
     • 사실상 기준점(출발점)만 다를뿐이지
       높은 기둥이 나타나면 전의 높이로 왔을테니 면적을 구할 수 있고,
       낮은 기둥이 나타나면 당장 결정하지 못하므로 pass 하는 방식으로 가능할거라 생각했다.
     • 투포인터에 꽂혀있었어서.. 둘다 낮은 기둥이 나타나면 어떻게 접근해야할지 난해했다.
       그나마 생각한 방법이 가장 높은 기둥의 높이를 미리 가지고 있어서, 포인터가 진행하다가 가장 높은 기둥을 만나면 멈추는 방식으로 생각했다. 하지만.. 가장 높은 기둥이 여러개라면? 
       
     • 처리가 꽤 복잡해지고 가독성이 사라진.. 코드가 될것같아 다른 방법을 생각했다.
   • 2st 접근 - 투포인터를 포기하자..)
     • 투포인터로 생각해 위와 같은 문제가 발생했으니 시작점에서 끝점까지 한번가고, 그 후에 끝점에서 시작점에서 한번오면 가능할것같았다.
     • 가장 높은 기둥이 여러개여도 어짜피 끝까지 가는것이므로 처리에 이상은 없을것이라 생각했다.
4. 위 계획을 검증
   • 시작점 -> 끝점, 끝점 -> 시작점 둘다 진행중인 높이보다 크거나 같은 기둥이 나타난다면 면적을 더하는 방식으로 진행하고, 둘다 끝까지 전부 간 뒤라면, 가장 높은 기둥(들) 중 단 하나의 면적만 더해지지 않은 상태이므로 이를 더하면 결국 전체 면적이다.
5. 계획 수행 (실제코드 작성) 
   1. Java 11

      • import java.util.*;
        import java.io.*;
        
        public class Main {
            static int N,area=0,maxHeightPosition=0;
            static List<Pillar> pillars;
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
                N = Integer.parseInt(br.readLine());
        
                pillars = new ArrayList<>();
                for (int n = 0; n < N; n++) {
                    StringTokenizer st = new StringTokenizer(br.readLine());
                    pillars.add(new Pillar(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
                }
        
                Collections.sort(pillars);
        
                // 진행하면서 이때까지의 기둥 중 가장 높은 기둥의 객체를 담음
                Pillar highestPillar = pillars.get(0);
                // 시작점 -> 끝점 이동
                for (int i = 1; i < pillars.size(); i++) {
                    Pillar curPillar = pillars.get(i);
                    // 가장 높았던 기둥의 높이보다 더 크거나 같은 기둥이 나타난다면
                    if (highestPillar.height <= curPillar.height) {
                        // 큰 높이가 나타나기 전까지의 위치까지, 작은 높이로 이어져야 하므로 면적을 구할 수 있음
                        area += (curPillar.position - highestPillar.position) * highestPillar.height;
                        highestPillar = curPillar;
                        maxHeightPosition = i;
                    }
                }
        
                // 끝점 -> 시작점 이동 (위와 같은 과정 그대로)
                highestPillar = pillars.get(pillars.size() - 1);
                for (int i = 1; i < pillars.size() - maxHeightPosition; i++) {
                    Pillar currentCol = pillars.get(pillars.size() - 1 - i);
                    if (highestPillar.height <= currentCol.height) {
                        area += (highestPillar.position - currentCol.position) * highestPillar.height;
                        highestPillar = currentCol;
                    }
                }
        
                // 가장 높았던 기둥의 면적을 마지막으로 추가
                area += pillars.get(maxHeightPosition).height;
                System.out.println(area);
            }
        }
        class Pillar implements Comparable<Pillar>{
            int position;
            int height;
        
            public Pillar(int position, int height) {
                this.position = position;
                this.height = height;
            }
        
            @Override
            public int compareTo(Pillar o) {
                // position 으로 오름차순하도록 기준 설정정
               return position-o.position;
            }
        
            @Override
            public String toString() {
                return "Pillar{" +
                        "position=" + position +
                        ", height=" + height +
                        '}';
            }
        }

 

• 결과