Stack 6

HackerRank : Largest Rectangle

Largest Rectangle | HackerRank Given n buildings, find the largest rectangular area possible by joining consecutive K buildings. www.hackerrank.com 문제 요약 건물의 갯수와 각 건물의 높이가 주어집니다. 일렬로 나열된 건물에서 안정적인 사각형 지대를 찾으려고 합니다. 사각형의 값은 아래 공식으로 구합니다. k * min(h[i], h[i+1], ... , h[i+k-1]) 쉽게 말해 가장 큰 넓이를 가진 사각형이 안정적인 사각형 지대가 됩니다. 핵심 요약 위 문제는 stack, queue의 유형으로 분리되어있지만, 단순 Brute Force를 통해서도 접근이 가능합니다. 핵심을 요약하면 다..

HackerRank : A Tale of Two Stacks

Queues: A Tale of Two Stacks | HackerRank Create a queue data structure using two stacks. www.hackerrank.com 문제 요약 2개의 Stack을 이용해서 Queue와 동일한 로직을 만들어 보세요. input 값으로 다음과 같이 입력이 가능합니다 q : 쿼리의 갯수 (최초에 1회 입력) 1 x : x를 큐에 저장 2 : 큐의 맨 앞 (가장 오래된 값)을 제거 3 : 큐의 맨 앞 (가장 오래된 값)을 출력 핵심 요약 해당 LeetCode의 문제와 흡사한 문제 유형입니다. 필요한 기능은 크게 다음 3가지로, 각각을 2개의 Stack을 이용해 구현합니다. enqueue : 큐에 값을 저장 dequeue : 큐의 첫 번째 값을 제거 ..

백준 9935번 문자열 폭발 (C++)

문제 링크 : https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 요약 1. 첫 번째 문자열(길이 1이상, 1,000,000이하)과 폭발 문자열(1이상 36이하)이 주어진다. 2. 문자열에 폭발 문자열이 포함되어있을 경우, 해당 폭발 문자열은 폭파되어 사라진다. 3. 폭파 된 뒤 새로 생긴 문자열에서도 폭발 문자열이 생길 수 있다. 4. 폭발 문자열이 문자열에 없을때까지 계속 폭파된다. 핵심 포인트 이 문제는 스택의 개념으로 접..

백준 2493번 탑 (C++)

문제 링크 : https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 요약 1. N개의 탑의 높이가 1열로 주어집니다. 2. 각각의 탑은 자신의 왼쪽에 위치한 탑 중 자신보다 높은 탑에게 신호를 전달할 수 있습니다. 3. 각각의 탑이 신호를 전달할 수 있는 탑의 위치를 출력하세요. 신호를 전달할 수 있는 탑이 존재하지 않을 경우 0을 출력하세요. 핵심 포인트 N의 값이 최대 500,000이 주어지므로, 무턱대로 2중 for문을 사용했다가 시간초..

LeetCode 42. Trapping Rain Water

The link : https://leetcode.com/problems/trapping-rain-water/ Trapping Rain Water - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 요약 배열과 배열의 값이 주어졌을때, 배열의 값은 높이를 의미합니다. 위 그림과 같이 빗물이 고일 수 있는 면적을 구하세요. 핵심 포인트 크게 두 가지 유형으로 빗물의 면적을 구할 수 있습니다. (1) 시작지점의 기둥보다 높은 기둥이 존재 한다 (2) 시작지점의 ..

백준 17298번 오큰수 (C++)

문제 링크 : https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 요약 1. 어느 한 숫자의 오른쪽에 위치한 숫자 중, 가장 왼쪽에 위치한 큰 숫자가 해당 숫자의 오큰수가 됩니다. 2. 만약 오큰수가 존재하지 않을 경우, 해당 숫자의 오큰수는 -1이 됩니다. 3. 예시는 다음과 같습니다. ex) 3 5 8 -> (각 숫자의 오큰수의 값) : 5 8 -1 핵심 포인트 다음 문장을 순차적으로 이해하여 하나씩 구현하면 됩니다. 스택을 사용하면 쉽게 풀 수 있습니..