stack

Algorithm/Baekjoon Online Judge
[Java] 백준 6198 (옥상 정원 꾸미기) Gold 5
Problem : https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net Approach 스택Stack 자료구조를 잘 이용해야 하는 문제이다. 스택을 빌딩의 높이 기준 내림차순 상태를 유지시키도록 구성하는 것이 문제 풀이의 포인트이다. 주요 문제 풀이 로직은 빌딩을 순차적으로 접근함을 전제로 다음과 같다. 스택이 비어있지 않고 스택의 top이 현재 빌딩의 높이 이하면 pop을 진행하며, ans에 (현재 빌딩 idx) - (스택 top의 빌딩 i..
→2021.06.26
Algorithm/Baekjoon Online Judge
[Java] 백준 16638 (괄호 추가하기 2) Gold 1
Problem : https://www.acmicpc.net/problem/16638 16638번: 괄호 추가하기 2 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계 www.acmicpc.net Approach Backtracking 기법과 중위표기 -> 후위표기 를 위한 Priority, Stack 등을 사용해야 했던 문제이다. 중첩된 괄호는 사용할 수 없고, 괄호 안에는 하나의 연산자만 존재할 수 있다는 점을 활용하면, 연산자를 기준으로 괄호를 씌울 것인지 말 것인지를 결정하면 된다는 걸 알 수 있다. 따라서 brackets 배열을 두어 해당 연산자가..
→2021.06.18
Algorithm/Baekjoon Online Judge
[Java] 백준 1918 (후위 표기식) Gold 4
Problem : https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net Approach Stack을 이용하여 풀이하는 문제이다. 입력으로 주어진 문자열을 하나씩 읽으면서 각 문자에 대해 우선순위를 매겨서 하나씩 뽑는 형태이다. 다음과 같이 4개의 경우가 발생한다. 참고로 스택엔 여는괄호와 연산자만 들어가게끔 구현한다. 스택의 문자들은 각각 우선순위가 매겨져 있으며, (가 0, +-가 1, */가 2로 숫자가 높을수록 우선이 된다. stack..
→2021.04.18
Algorithm/Programmers
[java] 프로그래머스 (짝지어 제거하기) Level 2
Problem : https://programmers.co.kr/learn/courses/30/lessons/12973 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr Approach 2017 팀스타운 문제이다. 주어진 문자열을 처음부터 Stack에 넣고 빼기를 반복한다. 넣기 전에 stack의 top과 비교하여 만약 같다면 pop을 하고, 다르다면 push를 한다. 문자열의 끝까지 다 완료한 후, 스택이 비어있으면 문자열을 모두 제거할 수 있는 것이고, 스택이 비어있지 않다면 문자열을 모두 제거..
→2021.01.16
Algorithm/Programmers
[java] 프로그래머스 (올바른 괄호) Level 2
Problem : https://programmers.co.kr/learn/courses/30/lessons/12909 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 ()() 또는 (())() 는 올바른 괄호입니다. )()( 또는 (()( 는 올바르지 않은 괄호 programmers.co.kr Approach 괄호체크는 간단하게 Stack을 사용하여 확인할 수 있다. '('을 만나면 stack에 push를 하고, ')'를 만났을 땐 stack이 비어있거나 stack의 top이 '('이 아니면 false를 반환한다. 맞다면 stack에서 pop을 한다. 또, 문자열의 끝까지 위 과정을 반복해서 끝낸 ..
→2021.01.13
Algorithm/Baekjoon Online Judge
[java] 백준 17298 (오큰수) Gold 4
Problem : 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 Approach 배열에서 자신 기준 오른쪽에 있는 큰 값들 중 가장 가까운 값을 찾는 문제이다. 간단하게 생각할 수 있는 naive한 방법은 자신보다 큰 값이 나올 때까지 자신 기준 오른쪽 요소들을 모두 탐색하는 것이다. 하지만 이런 접근법은 최대 O(n^2)의 시간복잡도를 가지므로 효율성이 떨어진다. 다른 풀이법으로는 스택을 이용한 풀이법이 있다. 처음 시작점을 스택에 push 한다. 스택의..
→2021.01.08

• 이전
• 1
• 다음