📍문제 링크https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으www.acmicpc.net 📍알고리즘 분류- 자료구조 - 스택 📍문제 풀이문제 요구사항은 쉽지만, N이 최대 8만에 달하기 때문에, O(N^2) 로는 해결할 수 없다 - 시간복잡도를 낮추기 위한 방법이 필요하다 배열을 순회하며 stack 길이만큼 반복문 수행 스택의 최신 값이 현재값보다 같거나 작으면, pop 실행, 아니면(가려져서 안보이므로) 종료 반복문 종료후 스택의 길이를 답에 더한다 그리고 스택에 현재..

📍문제 링크 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 📍알고리즘 분류 - 자료구조 - 문자열 - 스택 📍문제 풀이 전체 문자열에서 특정 문자열(폭탄)을 제거하는데, 제거한 후에 폭탄이 남아있으면 없어질 때까지 계속 제거해야 한다 - replace 함수를 반복하면 간단히 해결될 것 같지만.. 시간초과가 발생한다 - 문자열 입력값의 길이가 100만이기 때문에, 전체 문자열을 반복해서 탐색하는 O(N^2) 복잡도로는 해결이 불가..

📍문제 링크 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 📍알고리즘 분류 - 자료 구조 - 스택 📍문제 풀이 - 중위 표기식을 후위 표기식으로 바꿔 출력하라 - 곱셈, 나눗셈은 덧셈, 뺄셈보다 우선순위가 높은 연산자이다 📍의사 코드 - 일반 배열과 스택 배열을 만든다 - 주어진 중위 표기식 문자열을 순회하며, 알파벳이면 : 일반 배열에 push ( 이면 : 스택에 push ) 이면 : 스택 배열의 마지막 원소가 (가 나올 때까지 일반 배..

📍문제 링크 https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 📍알고리즘 분류 - 자료 구조 - 스택 📍문제 풀이 - 후위 표기식을 순회하며, 알파벳인 경우 와 연산자인 경우로 나눠서 생각한다. - 알파벳인 경우 stack에 저장한다. - 연산자인 경우, stack에서 2개의 수를 꺼내어 연산한뒤 다시 stack에 넣어 준다. 📍의사 코드 - 각 알파벳에 숫자를 바인딩하여 객체로 저장한다. 이를 통해 쉽게 숫자를 꺼내 쓸 수 있다. -..