스택8 [자료구조] 스택 & 큐 스택Stack 클래스에서 구현된 메서드는 다음과 같다. - `E push(E item)`: 스택의 맨 위에 요소를 추가한다. - `E pop()`: 스택의 맨 위 요소를 제거하고 제거된 요소를 반환한다. - `E peek()`: 스택의 맨 위 요소를 제거하지 않고 반환한다. - `boolean empty()`: 현재 스택에 요소가 존재하지 않을 경우 `true`, 그 외의 경우 `false`를 반환한다. - `int search(Object o)`: 스택의 상단부터 탐색하여 지정된 객체가 있는 요소의 위치를 반환한다. 없을 경우 `-1`을 반환한다. 스택은 먼저 들어온 데이터가 마지막에 나가는 구조이다. 페이지 뒤로가기, 실행 취소, 수식 괄호검사 등에서 응용된다. Stack 클래스는 .. 2024. 5. 18. [백준] 16120: PPAP - JAVA https://www.acmicpc.net/problem/16120 풀이문자열을 앞에서부터 보면서 'PPAP'가 되면 'P'로 바꿔준다. 최종적으로 'P'가 되면 성공. P가 들어오면 cnt를 1 늘려준다. A가 들어올 때 cnt가 2보다 작다면 PPAP를 만들수 없으므로 실패. cnt가 2이상이고, 다음 글자가 P라면 PPAP를 만들 수 있으므로, cnt를 1 줄여준다(P가 2개 빠지고 새로운 P가 들어오기 때문). 메모리: 20080KB시간: 260ms언어: Java 11import java.io.*;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new .. 2024. 5. 18. [백준] 22866: 탑 보기 - JAVA https://www.acmicpc.net/problem/22866 풀이N개의 건물의 높이가 주어진다. 각 건물의 옥상에서 양 옆을 볼 때, 현재있는 건물의 높이보다 큰 건물만 볼수있고, 큰 건물로 가려지면 볼 수 없다. 스택을 이용해 저장하면서 현재 빌딩보다 낮으면 없애주는 식으로 구현했다. 왼쪽부터, 오른쪽부터 두번에 걸쳐 스택에 저장하는 과정을 거쳤다. 왼쪽부터 진행할 때는 현재 건물의 왼쪽을 본다는 것이고 오른쪽부터 진행하면 오른쪽을 본다는 것이다. 메모리: 34648KB시간: 656ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Building { int idx; i.. 2024. 5. 17. [백준] 3025: 돌 던지기 - JAVA https://www.acmicpc.net/problem/3025 풀이주어진 조건에 맞게 위에서부터 돌을 떨어뜨려 최종 상태를 출력하는 문제였다. 단순한 구현으로 하나씩 진행하며 문제를 풀었을 때는 시간초과가 발생했다. 시간초과를 해결하기위해 메모이제이션을 해야했다. 처음 돌을 놓는 열 별로 stack을 만들어 돌이 이동하는 경로를 저장했다. 새로운 돌을 던질 때 stack에 경로가 들어있다면 마지막에서부터 진행하면 된다.1. 돌의 아랫칸이 벽으로 막혀있거나 가장 아랫줄이라면, 돌은 그 자리에 그대로 멈춰 있는다.2. 돌의 아랫칸이 비어있다면, 돌은 아랫칸으로 이동한다.3. 돌의 아랫칸에 돌이 있다면, 돌은 다음과 같이 미끄러진다. 1. 만약 돌의 왼쪽 칸과 왼쪽-아래 칸이 비어있다면, 돌은 왼쪽으.. 2024. 5. 14. [백준] 1725: 히스토그램 - JAVA https://www.acmicpc.net/problem/1725 풀이각 칸들의 높이가 주어지고, 내부에 가장 큰 직사각형을 구하는 문제이다. 아랫변을 구간으로 나눠 그 구간으로 이룰 수 있는 직사각형의 넓이를 비교해주었다. 세그먼트트리에는 구간별로 최소 높이를 갖는 인덱스를 저장해주었다. 구간으로 탐색할 때 인덱스를 기준으로 나누기 위함이다. (1, N)구간에서 넓이를 구하면 밑변은 (N - 1 + 1)이 되고, 높이는 해당 구간의 최소 높이를 세그먼트트리에서 찾아주면 된다. 이렇게 구한것이 해당 구간에서 만들수있는 직사각형의 최대이다. 위에서 찾은 최소 높이의 인덱스를 idx라고 하면 (1, idx - 1), (idx + 1, N)으로 나누어 계속 진행한다. 메모리: 39272KB시간: 356ms언.. 2024. 5. 14. [백준] 2812: 크게 만들기 - JAVA https://www.acmicpc.net/problem/2812 풀이스택을 이용하는 그리디 문제였다. N 자리 숫자에서 숫자 K 개를 지웠을 때의 최댓값을 구해야 한다. 숫자를 입력받으면서 stack에 하나씩 넣는다. 뺄 수 있는 개수(K)가 남아있고 stack의 끝값이 자신보다 작으면 그 값을 빼고 넣는다. 다만 N이 987654321과 같이 주어지면 stack에 들어가기만 하고 빠지는 숫자는 없다. 따라서 stack의 사이즈 - K 만큼 출력해 주어야 한다. 출력할 때 앞에서부터 빼기 위해서 stack 대신 deque을 이용했다. 메모리: 36464KB시간: 380ms언어: Java 11import java.io.*;import java.util.*;public class Main { pub.. 2024. 5. 13. [백준] 6198: 옥상 정원 꾸미기 - JAVA https://www.acmicpc.net/problem/6198 풀이그리디스러운 문제였다. 알고리즘 분류는 자료 구조, 스택. 자기보다 오른쪽에 있는 빌딩을 보는데 높이가 자기보다 낮은 빌딩을 볼 수 있다. 중간에 같거나 높은 빌딩을 만나면 그 다음부터 빌딩은 보지 못한다. 나는 현재 빌딩의 높이를 기준으로 이 빌딩을 볼 수 있는 왼쪽 빌딩들의 개수를 카운트했다. stack에 빌딩의 높이를 담으면서 진행하며 현재 빌딩보다 낮은 빌딩을 스택에서 빼줬다. stack의 사이즈를 답에 더해주고 현재 빌딩을 stack에 넣어주면 끝. 메모리: 24236KB시간: 324ms언어: Java 11import java.io.*;import java.util.*;public class Main { public s.. 2024. 5. 12. [백준] 2800: 괄호 제거 - JAVA https://www.acmicpc.net/problem/2800 풀이브루트포스 문제. 괄호의 쌍을 매칭하여 출력하거나 출력 안 하거나 하면 되는 문제였다. 서로의 짝을 매칭 시킬 방법으로 여는 괄호가 나오면 스택에 넣고, 닫는 괄호가 나오면 스택의 제일 위에 있는 괄호와 짝을 맺는다. 서로의 짝의 번호를 배열에 저장했다. 짝을 모두 저장한 후 dfs 탐색을 통해 해당 괄호를 boolean 배열에 true, false로 체크하여 출력할지 안 할지를 저장했다. 중복 식을 제거하기 위해, 사전 순으로 정렬하기 위해 TreeSet을 이용했다. 메모리: 24900KB시간: 280ms언어: Java 11import java.io.*;import java.util.*;public class Main { st.. 2024. 5. 12. 이전 1 다음