[Baekjoon] 백준 2304 창고 다각형 (S2 / 구현) - Java

링크

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

2304번: 창고 다각형

 

 

 

 

문제 해석

막대기둥 N개
막대기둥을 잇는 지붕을 만들어야 함
지붕은 물이 고이지 않게 오목한 부분이 없어야 함
가장자리는 땅에 닿아야 함

이때 만들어지는 창고의 최소 크기를 구하라


- 입력
첫 번째 줄 : N
  N : 기둥의 개수
나머지 줄 : L H 
  L : 기둥 위치
  H : 높이


- 출력
창고의 최소 크기

 

 

 

 

풀이 & 코드 해석

스택으로 푸는 문제라고도 하는데 굳이 스택을 사용하지 않고도 구현으로 풀 수 있는 문제입니다.

 

 

https://angelplayer.tistory.com/492

[Baekjoon] 백준 11501 주식 (S1 / 그리디) - Java

며칠 전에 풀었던 주식과도 비슷한 문제이기도 한데요.

 

 

우선 각 위치의 기둥 높이를 입력 받을 때마다 배열에 저장해 줍니다.

그 중에서 가장 높은 기둥의 인덱스를 지속적으로 업데이트하여 저장합니다.

 

가장 높은 기둥을 기준으로 왼쪽에서는 한 칸씩 오른쪽으로 이동하면서, 현재까지 나온 기둥 중에서 가장 높은 기둥만큼 더해줍니다.

마찬가지로 가장 높은 기둥을 기준으로 오른쪽에서는 한 칸씩 왼쪽으로 이동하면서, 현재까지 나온 기둥 중에서 가장 높은 기둥만큼 더해줍니다.

 

마지막으로 가장 높은 기둥까지 더해주면 전체를 감싸는 최소 높이의 면적이 출력됩니다.

 

 

코드

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

public class boj2304 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        // 첫 번째 줄
        st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        int[] map = new int[1001];
        int biggest_pillar = 0; // 가장 높은 기둥 위치
        int last_pillar = 0; // 가장 마지막 기둥 위치

        // 나머지 줄
        for (int i = 0 ; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            int L = Integer.parseInt(st.nextToken());
            int H = Integer.parseInt(st.nextToken());

            map[L] = H;
            // 가장 높은 높이 비교
            if (map[biggest_pillar] < H) {
                biggest_pillar = L;
            }
            last_pillar = Math.max(last_pillar, L); // 가장 마지막 기둥 찾기

        }

        int answer = 0;
        int now_max = map[0]; // 현재 비교 중인 가장 큰 기둥
        // 가장 높은 기둥 기준 왼쪽을 탐색
        for (int i = 0; i < biggest_pillar; i++) {
            // 현재 기준 높은 기둥보다 더 높은 기둥이라면
            if (map[i] > now_max) {
                answer += map[i];
                now_max = map[i];
            } else {
                answer += now_max;
            }
        }

        now_max = map[last_pillar];

        // 가장 높은 기둥 기준 오른쪽 탐색
        for (int i = last_pillar; i > biggest_pillar; i--) {
            // 현재 기준 높은 기둥보다 더 높은 기둥이라면
            if (map[i] > now_max) {
                answer += map[i];
                now_max = map[i];
            } else {
                answer += now_max;
            }
        }

        // 가장 높은 기둥 합산
        answer += map[biggest_pillar];

        System.out.println(answer);


    }
}

 

 

 

 

발생한 문제 & 해결 방안

입력 받을 때 값을 비교하고 나서 큰 값의 인덱스를 저장해야 하는데, 아무 생각 없이 값을 저장해버려서 결과가 이상하게 나왔다.

 

정신차리고 풀자..

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java