Stack(스택)
삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조
스택은 깊이 우선 탐색(DFS), 백트래킹 종류의 문제에 자주 사용한다.
Queue(큐)
삽입과 삭제 연산이 선입선출로 이뤄지는 자료구조
큐는 너비 우선 탐색(BFS)에서 자주 사용한다.
우선순위 큐
들어간 순서와 상관없이 우선순위가 높은 데이터가 머저 나오는 자요구조
큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다.
1874 : 스택 수열
문제
스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.
입력
첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.
출력
입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.
| 입력 | 출력 |
| 8 4 3 6 8 7 5 2 1 |
+ + + + - - + + - + + - - - - - |
| 5 1 2 5 3 4 |
NO |
문제 풀이
import java.util.Scanner;
import java.util.Stack;
public class P1874 {
public static void main(String[] args){
1. 검사할 배열 받기
2. 사용할 스택 만들기
3. 1부터 검사하기 위한 num = 1
4. '+', '-' 저장할 스트링 버퍼
5. 수열이 가능한지 여부
6. 배열 전체를 순회하며 검사
6-1. 현재 검사중인 수가 num(1부터 n까지)보다 크면
6-1-1. 스택에 num값을 검사중인 수와 같을때까지 쌓기
6-1-2. 스트링버퍼에 '+'담기
6-1-3. 마지막으로 담긴 stack값 빼기(검사중인 수 빼기)
6-1-4. 스트링버퍼에 '-'담기
6-2. 현재 검사중인 수가 num보다 작으면
6-2-1. 스택에 마지막 값 빼서 확인
(1) 마지막값이 검사할 값보다 크면 이 수열은 만들 수 없음
그러므로 "NO" 출력하고 result = false;처리 후
프로그램 종료
(2) 마지막값이 검사할 값과 같으면
pop을 수행했다는 의미인 '-'를 스트링 버퍼에 추가
7. 만약 result값이 true이면(수열이 만들어졌으면) 스트링버퍼에 있던 push, pop결과 값 출력
}
}
실행 코드
import java.util.Scanner;
import java.util.Stack;
public class P1874 {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] A = new int[N];
for(int i=0;i<N;i++){
A[i] = sc.nextInt();
}
Stack<Integer> stack = new Stack<>();
int num = 1;
StringBuffer sb = new StringBuffer();
boolean result = true;
for(int i = 0;i<N;i++){
int su = A[i];
if(su >= num){
while(su>=num){
stack.push(num++);
sb.append("+\n");
}
stack.pop();
sb.append("-\n");
}else{
int n = stack.pop();
if(n > su){
System.out.println("NO");
result = false;
break;
}else if(n==su){
sb.append("-\n");
}
}
}
if(result)
System.out.print(sb);
}
}
2164 : 카드2
문제
N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.
출력
첫째 줄에 남게 되는 카드의 번호를 출력한다.
| 입력 | 출력 |
| 6 | 4 |
실행 코드
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class P2164 {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
Queue<Integer> Que = new LinkedList<>();
for(int i=1;i<=N;i++){
Que.add(i);
}
while(Que.size()>1){
Que.remove();
int floor = Que.poll();
Que.add(floor);
}
System.out.print(Que.poll());
}
}
11286 : 절댓값 힙(우선순위 큐)
문제
절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.
- 배열에 정수 x (x ≠ 0)를 넣는다.
- 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
입력
첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.
- N값이 100,000이하이므로 O(nlogn)시간 복잡도를 가진 알고리즘으로 풀 수 있다.
출력
입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
| 입력 | 출력 |
| 18 1 -1 0 0 0 1 1 -1 -1 2 -2 0 0 0 0 0 0 0 |
-1 1 0 -1 -1 1 1 -2 2 0 |
문제 풀이
- 우선순위 큐의 정렬 규칙을 직접 작성해야함
PriorityQueue<Integer> que = new PriorityQueue<>((o1, o2)->{
// 정렬 로직
int first_abs = Math.abs(o1);
int second_abs = Math.abs(o2);
// 절댓값이 같으면 음수 우선
if(first_abs == second_abs){
return o1 > o2 ? 1 : -1;
}
// 절댓값 작은 데이터
return first_abs - second_abs;
});
🌀 우선순위 큐 규칙 실행 흐름
내부적으로 완전 이진 트리를 사용하여, 부모 노드와 비교를 통해 적절한 위치에 배치합니다. 이 때문에 필요한 경우에만 최소한의 비교를 통해 위치를 찾아간다.
- return 값이 음수이면: o1이 o2보다 우선순위가 높아서, o1이 o2 앞에 위치한다.
- return 값이 양수이면: o2가 o1보다 우선순위가 높아서, o2가 o1 앞에 위치한다.
- return 값이 0이면: o1과 o2는 우선순위가 같다고 판단하여 순서 변경이 없다.
실행 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class P11286 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
PriorityQueue<Integer> que = new PriorityQueue<>((o1, o2)->{
// 정렬 로직
int first_abs = Math.abs(o1);
int second_abs = Math.abs(o2);
// 절댓값이 같으면 음수 우선
if(first_abs == second_abs){
return o1 > o2 ? 1 : -1;
}
// 절댓값 작은 데이터
return first_abs - second_abs;
});
for(int i=0;i<N;i++){
int request = Integer.parseInt(br.readLine());
if(request == 0){
if(que.isEmpty())
System.out.println("0");
else
System.out.println(que.poll());
}else{
que.add(request);
}
}
}
}'[ STUDY ] > CodingTest' 카테고리의 다른 글
| [ 정렬 ] 삽입 정렬, 퀵 정렬(백준 11399, 11004) (0) | 2024.11.07 |
|---|---|
| [ 정렬 ] 버블 정렬, 선택 정렬 (백준 2750, 1427) (1) | 2024.11.06 |
| [ 자료구조 ] 슬라이딩 윈도우(백준 12891) (1) | 2024.10.31 |
| [ 자료구조 ] 투 포인터(백준 2018, 1940) (1) | 2024.10.29 |
| [ 자료구조 ] 구간 합(백준 11659) (3) | 2024.10.29 |