관리 메뉴

공부공간

BOJ - 2493 ) 탑 본문

구현,시뮬

BOJ - 2493 ) 탑

SangwonSeo 개발자가될수있을까? 2020. 8. 5. 00:49
728x90


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

 

2493번: 탑

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 ��

www.acmicpc.net

 


Stack 자료구조를 사용하여 현재까지의 탑의 높이를 저장하여 

 

내 왼쪽의 탑들중 신호를 수신하는 탑을 찾는 문제이다.

 

수신되는 탑을 찾기위하여 현재까지 저장된 높이가 내높이보다 크면 add연산을 진행하고

 

작다면 나보다 큰 높이가 나올때까지 poll연산을 진행한다.


package algorithm;

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

public class 탑 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<Integer> s = new Stack<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int arr[] = new int[n+1];
		StringBuilder sb = new StringBuilder();
		st = new StringTokenizer(br.readLine());
		for(int i = 1 ; i <= n ; i++) arr[i] = Integer.parseInt(st.nextToken());
		for(int i = 1 ; i <= n ; i++) {
			if(s.isEmpty()) {
				sb.append(0+" ");
				s.add(i);
			} else {
				int now = arr[i];
				if(arr[s.peek()] > now) {
					sb.append(s.peek()+" ");
					s.add(i);
				} else {
					while(!s.isEmpty() && arr[s.peek()] < now) {
						s.pop();
					}
					if(s.isEmpty()) {
						sb.append(0+" ");
						s.add(i);
					} else {
						sb.append(s.peek()+" ");
						s.add(i);
					}
				}
			}
		} System.out.println(sb);
	}

}

728x90

'구현,시뮬' 카테고리의 다른 글

BOJ - 1560 ) 비숍  (0) 2020.08.12
BOJ - 1477 ) 휴게소 세우기  (0) 2020.08.06
BOJ - 2493 ) 탑  (0) 2020.08.05
BOJ - 17081 ) RPG Extreme  (0) 2020.08.02
BOJ - 1846 ) 장기  (1) 2020.07.29
BOJ - 18111 ) 마인크래프트  (0) 2020.07.22
0 Comments
댓글쓰기 폼