[BOJ알고리즘, C++]#2493_탑, 스택, 히스토그램 유형

2024. 3. 7. 11:59· 문제 풀이/BOJ 문제 풀이
목차
  1. #1. 문제
  2. #2. 풀이
  3. 1. 스택
  4. 2. 히스토그램 유형 문제는 스택으로 풀자!
  5. #3. 코드

 

#1. 문제

 

2493번: 탑

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

www.acmicpc.net

 


 

#2. 풀이

 

1. 스택

 

[자료 구조]#0_선형 자료구조

[자료 구조] #0_선형 자료구조 선형 자료구조에 대해 알아보겠습니다. Overview 개념 스택 큐 원형 큐 덱 배열 벡터 리스트 이중 연결 리스트 #0. 개념 1. 선형 자료구조? [정의] : 선형 자료구조는 데

webddevys.tistory.com

 

스택은 후입 선출 방식으로 동작하는 선형 자료구조로, 지정된 형식의 데이터를 한쪽 방향으로만 삽입하며, 제거 작업은 반대편 한쪽에서만 가능합니다.

 

2. 히스토그램 유형 문제는 스택으로 풀자!

 

  1. 각 송신탑의 높이 값을 차례대로 vector 컨테이너에 저장합니다. 그리고, 빈 스택 하나를 선언합니다.
  2. 높이 값을 저장한 vector 컨테이너를 차례대로 순회합니다. 이때, 스택의 top에 위치한 인덱스에 해당하는 높이 값과 현재 위치의 높이 값을 비교하고, 현재 높이 값이 크다면 현재 스택의 top 값을 pop 해줍니다. 이 과정은 stack이 동나거나, top에 위치한 인덱스에 해당되는 높이 값이 현재 위치의 값보다 클 때까지 반복됩니다.
  3. 마지막으로, stack이 비어있을 경우 현재 위치의 송신탑이 레이저를 발사하면 왼쪽에 위치한 어느 송신탑도 그 레이저를 받을 수 없습니다. 반면, stack이 비어있지 않을 경우, stack의 top에 위치한 인덱스에 해당되는 높이 값이 현재 송신탑의 레이저를 수신 받게됩니다!

 


#3. 코드

 

#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;

int N;
vector<int> v, ans;
stack<int> s;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    v.resize(N + 1);
    ans.resize(N+1);
    
    for (int i = 1; i <= N; ++i)
    {
        cin >> v[i];
    }

    for (int i = 1; i <= N; ++i)
    {
        while (!s.empty() && v[i] > v[s.top()])
        {
            s.pop();
        }

        if (s.empty())
            ans[i] = 0;
        else
            ans[i] = s.top();

        s.push(i);
    }

    for (int i = 1; i <= N; ++i)
        cout << ans[i] << ' ';

    return 0;
}

 


 

 

 

 

저작자표시 (새창열림)

'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글

[BOJ알고리즘, C++]#11437_LCA  (0) 2024.03.13
[BOJ알고리즘, C++]#3584_가장 가까운 공통 조상, 트리, LCA  (0) 2024.03.12
[BOJ알고리즘, C++]#9375_패션왕 신해빈, um, 경우의 수  (0) 2024.03.07
[BOJ알고리즘, C++]#1806_부분 합, Prefix Sum, 누적 합, 투 포인터  (0) 2024.03.03
[BOJ알고리즘, C++]#15681_트리와 쿼리, 트리, DFS, DP  (0) 2024.03.03
  1. #1. 문제
  2. #2. 풀이
  3. 1. 스택
  4. 2. 히스토그램 유형 문제는 스택으로 풀자!
  5. #3. 코드
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ알고리즘, C++]#11437_LCA
  • [BOJ알고리즘, C++]#3584_가장 가까운 공통 조상, 트리, LCA
  • [BOJ알고리즘, C++]#9375_패션왕 신해빈, um, 경우의 수
  • [BOJ알고리즘, C++]#1806_부분 합, Prefix Sum, 누적 합, 투 포인터
Hardii2
Hardii2
개발 블로그Hardii2 님의 블로그입니다.
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • C++
  • 트리
  • stl
  • 우선순위 큐
  • unreal
  • Unreal Blueprint
  • 디자인 패턴
  • set
  • DP
  • BOJ
  • 개발
  • dfs
  • 최단 경로
  • 정렬
  • BFS
  • 기술 질문
  • programmers
  • 그래프
  • Effective C++
  • 알고리즘

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#2493_탑, 스택, 히스토그램 유형
상단으로

티스토리툴바

개인정보

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

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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