기록방

👉 문제링크 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 🔸 문제 분석 🔸 중위 표기식을 후위 표기식으로 변환해 출력한다. 입력되는 피 연산자는 알파벳 대문자, 연산자는 "+-*/()"의 6가지가 사용된다. 스택 자료구조를 사용해서 후위 표기식으로 변환할 수 있다. 🔸 코드 🔸 import java.io.*; public class Main { private static class MyStack { private int pointer; private char[] stack; public MyStack(..

👉 문제링크 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 🔸 문제 분석 🔸 주어진 기둥들을 사용해 창고를 지을때 만들 수 있는 면적 중 최소값을 출력한다. 조건들을 맞춰서 최소면적을 구하는 방법은 다음과 같다. 가장 높은 기둥을 중심으로 왼쪽 오른쪽으로 낮아지는 지붕 오목한 부분이 없어야 하므로 끝에서 가장 높은 기둥까지 다가오며, 더 큰 기둥을 만날때만 높이를 높임 🔸 코드 🔸 import java.util.Arrays; import java.util.Comparator; import j..

👉 문제링크 23253번: 자료구조는 정말 최고야 위 그림처럼 책이 쌓여 있으므로, 첫 번째 더미 - 두 번째 더미 - 첫 번째 더미 - 두 번째 더미 순으로 꺼내면 책 번호순으로 나열할 수 있다. www.acmicpc.net 🔸 문제 분석 🔸 여러개의 스택형식 책더미에서 번호 순서대로 책을 뽑을 수 있는지 판별한다. 스택과 책의 개수가 최대 20만이므로 pop을 반복해서 탐색하는건 시간초과가 난다. 각 책 무더기가 내림차순으로 정렬되어 있으면 문제 조건을 만족하므로, 정렬을 확인한다. 🔸 코드 🔸 import sys input = sys.stdin.readline n, m = map(int, input().split()) for _ in range(m): book = int(input()) books ..

👉 문제링크 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 🔸 문제 분석 🔸 배열arr을 입력받으면, 한 인덱스 i의 오른쪽으로 처음 등장하는 arr[i] 보다 큰 값(오큰수)을 정답 배열 answer[i]에 저장한다. n이 1,000,000(백만)이므로 인덱스마다 오른쪽 탐색을 진행하면 O(n^2)로 시간초과가 난다. 스택을 이용해서 오큰수를 찾지 못한 인덱스만 스택에 남기며 계산을 진행한다. 스택의 arr[top]이 push하려는 arr[i]보다 작다면, 인덱스 top의 오큰수는 arr[i]이다. 배열 순회가 끝나도..

👉 문제링크 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 🔸 문제 분석 🔸 스택의 pop, push 연산과 후입 선출 개념을 정확하게 알고 있는지 묻는 문제이다. 스택에 넣는 자연수 값은 오름 차순 정렬이다. 현재 수열 값 >= 자연수 자연수가 현재 수열 값과 같아질 때 까지 자연수를 1증가시키며 스택에 push한다. 마지막은 출력하기 위해 1번 pop한다. 현재 수열 값 < 자연수 pop해서 스택의 가장 위 값을 확인한다...