[코딩테스트] 백준 17608번 막대기 - JAVA

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

문제 (브론즈2)

아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 6, 9, 7, 6, 4, 6 이다. 일렬로 세워진 막대기를 오른쪽에서 보면 보이는 막대기가 있고 보이지 않는 막대기가 있다. 즉, 지금 보이는 막대기보다 뒤에 있고 높이가 높은 것이 보이게 된다. 예를 들어, 그림과 같은 경우엔 3개(6번, 3번, 2번)의 막대기가 보인다.

N개의 막대기에 대한 높이 정보가 주어질 때, 오른쪽에서 보아서 몇 개가 보이는지를 알아내는 프로그램을 작성하려고 한다.

입력

첫 번째 줄에는 막대기의 개수를 나타내는 정수 N (2 ≤ N ≤ 100,000)이 주어지고 이어지는 N줄 각각에는 막대기의 높이를 나타내는 정수 h(1 ≤ h ≤ 100,000)가 주어진다.

 

출력

오른쪽에서 N개의 막대기를 보았을 때, 보이는 막대기의 개수를 출력한다.

 

 

 

문제해석

• 막대기가 왼쪽부터 일렬로 배치되어 있다.
• 맨 오른쪽에서 보았을 때, 맨 오른쪽 막대기를 포함하여 보이는 막대기의 개수를 센다.
• 보이는 기준: 이전에 보였던 막대기보다 더 높은 막대기만 보인다.
• 단, 맨 오른쪽보다 크더라도 앞에 더 높은 막대기가 있으면 보이지 않는다.

 

답안코드

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

public class B17608 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 막대기의 개수 입력

        Stack<Integer> stack = new Stack<>(); // 막대기를 저장할 스택
        for (int i = 0; i < n; i++) {
            stack.add(Integer.parseInt(br.readLine())); // 막대기 높이 입력
        }

        int visibleCount = 1; // 보이는 막대기의 수 (맨 오른쪽 막대기는 항상 보임)
        int tallestBar = stack.pop(); // 맨 오른쪽 막대기의 높이

        // 스택을 사용해 오른쪽에서 왼쪽으로 막대기를 확인
        while (!stack.isEmpty()) {
            int currentBar = stack.pop(); // 현재 확인 중인 막대기의 높이
            if (tallestBar < currentBar) { 
                // 현재 막대기가 이전에 확인한 가장 높은 막대기보다 높을 경우
                tallestBar = currentBar; // 가장 높은 막대기 갱신
                visibleCount++; // 보이는 막대기의 수 증가
            }
        }

        System.out.println(visibleCount); // 최종적으로 보이는 막대기의 개수 출력
    }
}

 

 

문제풀이

Stack<Integer> stack = new Stack<>();
int tallestBar = 0; // 현재까지 확인한 가장 높은 막대기
int visibleCount = 0; // 보이는 막대기의 수

while (!stack.isEmpty()) {
    int currentBar = stack.pop(); // 현재 확인 중인 막대기
    if (currentBar > tallestBar) { 
        tallestBar = currentBar; // 가장 높은 막대기 갱신
        visibleCount++; // 보이는 막대기 개수 증가
    }
}

1. 맨 오른쪽부터 체크를 해야됨으로 입력값에 역순으로 데이터를 호출할 수 있는 스택을 사용
2. 이전까지 확인한 가능 높은 막대기보다 높으면
   • 가장 높은 막대기를 갱신한다. 
   • 보이는 막대기 개수를 증가한다.
3. 끝날 때까지 반복