백준 17608번: 막대기 [JAVA]

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

17608번: 막대기

• 풀이

마지막 막대기부터 세야하기 때문에 스택을 사용한다. 오른쪽부터 보이는 막대기를 세는데, 보였던 막대기보다 큰 막대기가 나올 때마다 카운트를 증가시키고, 막대기의 최대값이 나오면 종료한다.

• 코드

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		// 막대기 개수 N 입력
		int N = Integer.parseInt(bf.readLine());
		Stack <Integer> stack = new Stack <Integer>();
		
		int max = 0; // 가장 높은 블럭 높이
		
		// 각 막대기 높이 h 입력
		for (int i=0; i<N; i++) {
			stack.push(Integer.parseInt(bf.readLine()));
			if(max<stack.peek()) max=stack.peek();
		}
		
		int s = 0; // 보이는 블럭 높이
		int result = 0; // 결과값

		for (int i=0; i<N; i++) {
			int p = stack.pop();
			if(s<p) { // 보이는 블럭 높이보다 블럭이 크면 결과값++, 보이는 블럭 높이 변경
				s=p;
				result++;
			}
			if (p == max) break; // 최대 블럭 높이 만나면 break
		}
		
		// 결과 출력
		System.out.println(result);
	}

}

---

• 다른 풀이 참고

왼쪽에 있는 막대기부터 입력을 할 때, 더 큰 막대기가 들어오면 기존 막대기는 의미가 없어진다. 따라서 더 큰 막대기가 들어올 때마다 기존 값 pop() 시키고 더 작은 막대기일 때만 계속 push()한다. 결과적으로는 보이는 막대기만 스택에 쌓이게 되므로 size()를 출력하면 된다.

• 코드

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		// 막대기 개수 N 입력
		int N = Integer.parseInt(bf.readLine());
		Stack <Integer> stack = new Stack <Integer>();
		
		for (int i = 0; i<N; i++) {
				int h = Integer.parseInt(bf.readLine());
				while (!stack.isEmpty()&&h>=stack.peek()) stack.pop(); // 현재 값보다 작은 peek() 값 pop()
				stack.push(h);
			}
		
		// 출력
		System.out.println(stack.size());
	}
}

시간 복잡도

N * O(while) = O(N)