[Algorithm] 백준 17608 막대기 java

leeinae·2020년 10월 13일
0

Algorithm

목록 보기
38/39

[문제] (https://www.acmicpc.net/problem/17608)


위 그림처럼 막대기가 일렬로 쭉 주어지고, 오른쪽에서 봤을 때 몇 개의 막대가 보이는지 개수를 출력하면 되는 문제이다.
나는 stack을 _사용해서 보일 수 있는 막대_를 저장하고, 길이를 출력하려고 했다.

풀이 방법

  1. stack을 하나 선언하고, 막대기를 하나씩 입력받는다.
  2. stack이 비지 않았고, 오른쪽에서 봤을 때 막대가 보일 수 있다면!
    기존 stack의 top에 있는 값을 pop()하고, 현재 들어온 막대기를 push()한다.
    현재 들어온 막대기의 길이가 stack.peek()를 통해 가져온 stack의 top의 값보다 크거나 같다면 오른쪽에서 봤을 때 보이는 막대기라고 할 수 있다.
    • pop을 하는 이유: 기존의 막대기는 더이상 보이지 않는 것이므로 삭제
    • while을 사용해서 직전에 들어온 막대뿐만 아니라 그 전에 들어온 막대와도 비교... (예를 들어 6-4-6의 순서로 들어온 경우)
  3. stack의 길이를 출력!

코드

import java.util.Scanner;
import java.util.Stack;

public class BOJ_17608 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Stack<Integer> stack = new Stack<>();

        int num = sc.nextInt();

        for (int i = 1; i <= num; i++) {
            int temp = sc.nextInt();

            while (!stack.empty() && isVisible(stack, temp)) {
                stack.pop();
            }
            stack.push(temp);
        }

        System.out.println(stack.size());
    }

    // 현재 막대기의 길이가 stack의 top에 들어있는 막대기보다 크거나 같아서
    // 왼쪽에서 봤을 때 막대기가 보이는지 여부를 리턴하는 함수
    public static boolean isVisible(Stack stack, int temp) {
        int top = (int) stack.peek();

        return temp >= top;
    }
}

흐흡,, 오랜만에 설명하려니까 횡설수설이다

0개의 댓글