백준 6198 옥상 정원 꾸미기

드디어 실버를 넘어 골드에 도착했다
무려 골드5!!...
골드3까지는 잘풀어야 자유롭게 구현할것같다.

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

단순 스택이 아닌 CLASS 를 만들어서 비교해주었다

필자는 번호 & 높이로 하였으나!!!

입력순을 1 2 3 4 5 6이 아닌
거꾸로 5 4 3 2 1 0 번으로 (6개 입력시 설정해주었다..)

그래서 스택을 2개 저장해놓고 한스택이 비어있다면 가지고있는 인덱스만큼 관전이 가능하다고 판단이 가능하다
기존스택S1 , 옮겨진스택 S2라고하면
그래서
1. 첫입력케이스 (첫입력은 갯수안세줌) (S2에넣기)
2. S1에서 꺼낸값과 S2의 peek 비교
3.1 peek비교시 크다 => 빌딩을 넘어서 관찰이 가능하니까 s2에서 pop진행후 2번으로 이동
3.2 작다 => 더이상보지못한다 => peek와 index비교후 차이나는값만큼 더하고 s2에 s1에서 꺼낸값넣기
4. 만약 3.1과정을다하다가 s2가 비게된다면 모든 빌딩이 관찰이가능하니 현재 인덱스를 더해주고 s2에넣어줌

주요핵심 그림은 다음과같다.

코드는 다음과같다.

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

class building{
	long index;
	long high;
	public building(long high, long index) {
		this.index=index;
		this.high = high;
	}
}
public class 옥상정원꾸미기 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		long count = Integer.parseInt(br.readLine());
		long answer = 0;
		long bindex = count;
		Stack<building> s1 = new Stack<>();
		Stack<building> s2 = new Stack<>();
		for(int i=0;i<count;i++) {
			long number = Integer.parseInt(br.readLine());
			s1.add(new building(number,--bindex));
		}
		
		
		while(!s1.isEmpty()) {
			building current = s1.pop();
			if(s2.isEmpty()) { //맨처음 값추가
				s2.add(current);
				continue;
			}
			
			while(!s2.isEmpty()) {
				
				building s2c = s2.peek();
				
				if(s2c.high>= current.high) { //더이상 볼 빌딩이없음
					s2.add(current);
					answer += current.index-s2c.index-1;
					break;
				}
				
				s2.pop();
			}
			
			if(s2.isEmpty()) {
				s2.add(current);
				answer += current.index;
			}
			
	//		System.out.println(answer + " : " + current.index + " : " + current.high);
		}
		System.out.println(answer);
		
	}

}