hades

🥅 문제https://www.acmicpc.net/problem/6198 🔍 설계처음에는 벡터에 높이들을 모두 저장하고, 이중 반복문을 수행하려고 했으나, 시간 복잡도 O(N^2)에 의해 시간 초과가 발생할 것이다. 건물 관리인들은 오른쪽만 보기 때문에, 반복문으로 건물 하나의 높이를 고려하면서, 스택에 그 건물을 볼 수 있는 다른 건물들을 저장한다.  만약, 새로운 건물의 높이보다 그 전에 있는 건물의 높이가 낮거나 같다면, 새로운 건물과 이후에 나오는 건물들을 볼 수 없으므로 이제 결과에 영향을 주지 않기 때문에 지운다. 만약, 새로운 건물의 높이보다 그 전에 있는 건물의 높이가 높다면, 그 건물에서 새로운 건물을 볼 수 있으므로 스택에 있는 건물의 개수를 추가한다. 👊 풀이#include #i..

🥅 문제https://www.acmicpc.net/problem/9935 🔍 설계문자열의 반복문을 돌리면서, 폭발 문자열과 일치하는 부분 문자열이 만들어지면, 맨 위부터 폭발시켜야 하므로, 스택을 이용한다는 것은 쉽게 파악할 수 있었다.  폭발 문자열과 일치하면 현재 인덱스에서 폭발 문자열에서 일치한 인덱스를 save에 저장하고, 다음 탐색할 인덱스(cur_idx)를 1 증가시키면서 폭발 문자열의 길이와 일치하면 폭발시키는 방식으로 설계했다. 초기 설계에서의 문제점은 스택에 문자만 담았기 때문에 폭발하고 난 후, 다음 탐색할 인덱스를 폭발 문자열이 완성된 위치에서 폭발 문자열의 길이를 뺀 인덱스에서의 save 값과 같이 잘 못 구했었다. 하지만 이런 경우,  abaabcdbcdcd abcd  와 같이..

🥅 문제https://www.acmicpc.net/problem/1918 🔍 설계후위 표기식을 나타내는 데는 스택을 사용한다. A+B-C의 경우, ABC-+ 인데, 출력 순서를 고려하면, 먼저 들어온 +가 나중에 출력되어야 하기 때문이다.  알파벳이면, 그냥 출력하여 스택에는 괄호와 연산자만 담기게 한다. 괄호 내부의 식을 고려하기 위해, 현재 문자가 '('이면 스택에 그냥 추가하고, ')'이면, 괄호 내부에서 아직 출력하지 않은 연산자를 출력하고, '('를 제거하여 괄호 내부의 식을 끝낸다. 현재 문자가 괄호가 아닌 연산자이면, 뒤에 괄호가 올 수 있으므로, 마지막에 스택에 추가해야 한다. 괄호에 대한 연산자를 먼저 출력하고, 그 이후에 출력해야 하기 때문이다. 마지막에 스택에 추가하기 전에 연산자..