[백준] 2493 탑 java

2022. 5. 24. 18:24· Dev/PS

import java.io.*;
import java.util.*;


class Top {
    int loc;
    int len;
    Top(int loc, int len) {
        this.loc = loc;
        this.len = len;
    }
}

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int n;
    static int[] tops;
    static Stack<Top> s = new Stack<>();
    static StringBuilder ans = new StringBuilder();

    public static void main(String[] args) throws IOException {
        input();
        solve();
        System.out.println(ans.toString());
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        tops = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            tops[i] = Integer.parseInt(st.nextToken());
        }
    }

    static void solve() {
        ans.append("0 ");
        s.push(new Top(1, tops[0]));
        for(int i = 1; i < n; i++) {
            while(true) {
                if(s.isEmpty()) {
                    ans.append("0 ");
                    s.push(new Top(i+1, tops[i]));
                    break;
                }
                if(tops[i] < s.peek().len) {
                    ans.append(s.peek().loc + " ");
                    s.push(new Top(i+1, tops[i]));
                    break;
                }
                else {
                    s.pop();
                }
            }
        }
    }
}

스택을 이용한 문제였다.

 

스택이 비어있다면 현재 위치의 탑보다 큰 탑이 없으므로 0을 출력한다.

 

그 외의 2가지 케이스로는 현재 위치의 탑이 peek한 탑의 높이보다 높거나 같은 경우 스택에서 pop한다.

반대로 현재 위치의 탑이 peek한 탑의 높이보다 작을 경우 peek한 탑의 위치를 출력하고 현재 위치의 탑을 push한다.

저작자표시 (새창열림)

'Dev > PS' 카테고리의 다른 글

[SWEA] 백만 장자 프로젝트 1859 java  (0) 2022.05.27
[백준] 1918 후위 표기식 java  (0) 2022.05.26
[백준] 2800 괄호 제거 java  (0) 2022.04.25
[백준] 14502 실험실 java  (0) 2022.04.25
[백준] 2632 피자 판매 java  (0) 2022.04.16
'Dev/PS' 카테고리의 다른 글
  • [SWEA] 백만 장자 프로젝트 1859 java
  • [백준] 1918 후위 표기식 java
  • [백준] 2800 괄호 제거 java
  • [백준] 14502 실험실 java
풋데브
풋데브
지속가능한 삶
풋데브
지루함에 익숙해지자
풋데브
전체
오늘
어제
  • 분류 전체보기 (90)
    • 일상 (4)
    • 후기 (2)
    • 운동 (0)
    • Dev (84)
      • PS (72)
      • CS (0)
      • Java (1)
      • Spring (0)
      • DB (4)
      • Test (2)
      • Web (0)
      • 트러블 슈팅 (2)
      • Etc (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 투포인터
  • 너비우선탐색
  • 코테
  • BOJ
  • 백트래킹
  • 자바
  • BFS
  • 백준
  • 완전탐색
  • 백엔드
  • java
  • algorithm
  • codingtest
  • bruteforce
  • 구현
  • programming
  • 개발자
  • 깊이우선탐색
  • 다이나믹프로그래밍
  • 그래프
  • Implement
  • 코딩테스트
  • graph
  • combination
  • Developer
  • DP
  • 조합
  • DFS
  • 알고리즘
  • 자료구조

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
풋데브
[백준] 2493 탑 java
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.