25/02/10 (월)
아.. 월...요..일..입니..다...
사실 월요일은 엄청 힘들지 않은데 금요일이 가장 힘든것같습니다.
이번주 토요일에 기사시험인데 공부를 많이 안해서 걱정입니다.
당분간 주짓수를 줄이고 기사와 알고리즘에 집중해야겠습니다.
1. 교재 강의
1.1. CH06 스택
1) 스택과 큐
스택과 큐
- Stack : FILO, Stack은 메소드의 호출과 기능이 비슷하여 재귀 호출을 통해 Stack, DFS를 구현
- Queue : FIFO, Interface 타입
Stack 구현
package basic.Ch10_StackQueue;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;
public class Test1{
public static void main(String[] args) {
//Stack
{
// Stack<Integer> stack = new Stack<>();
//
// stack.push(3);
// System.out.println(stack.peek());
// System.out.println(stack.size());
//
// stack.push(1);
// System.out.println(stack.peek());
// System.out.println(stack.size());
//
// stack.push(7);
// System.out.println(stack.peek());
// System.out.println(stack.size());
//
// Integer num = stack.pop();
// System.out.println(num);
// System.out.println(stack.peek());
// System.out.println(stack.size());
//
// while(!stack.isEmpty()){
// System.out.print(stack.pop()+" ");
// }
}
//Stack using Deque
{
Deque<Integer> stack = new ArrayDeque<>();
stack.push(3);
System.out.println(stack.peek());
System.out.println(stack.size());
stack.push(1);
System.out.println(stack.peek());
System.out.println(stack.size());
stack.push(7);
System.out.println(stack.peek());
System.out.println(stack.size());
Integer num = stack.pop();
System.out.println(num);
System.out.println(stack.peek());
System.out.println(stack.size());
while (!stack.isEmpty()) {
System.out.print(stack.pop() + " ");
}
}
}
}- Stack Method : push(e), pop(), peek()
- ArrayDeque가 더 성능이 좋음
Queue 구현
package basic.Ch10_StackQueue;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
public class Test2 {
public static void main(String[] args) {
//Queue
// {
// Queue<Integer> queue = new LinkedList<>();
//
// queue.offer(3);
// System.out.println(queue.peek());
// System.out.println(queue.size());
//
// queue.offer(1);
// System.out.println(queue.peek());
// System.out.println(queue.size());
//
// queue.offer(7);
// System.out.println(queue.peek());
// System.out.println(queue.size());
//
// Integer num = queue.poll();
// System.out.println(num);
// System.out.println(queue.peek());
// System.out.println(queue.size());
//
// while(!queue.isEmpty()){
// System.out.print(queue.poll()+" ");
// }
// }
//Queue using Deque
{
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(3);
System.out.println(queue.peek());
System.out.println(queue.size());
queue.offer(1);
System.out.println(queue.peek());
System.out.println(queue.size());
queue.offer(7);
System.out.println(queue.peek());
System.out.println(queue.size());
Integer num = queue.poll();
System.out.println(num);
System.out.println(queue.peek());
System.out.println(queue.size());
while (!queue.isEmpty()) {
System.out.print(queue.poll() + " ");
}
}
}
}- Queue Method : offer(e), poll(), peek()
사용자 정의 클래스 스택, 큐 활용
package basic.Ch10_StackQueue;
import java.util.ArrayDeque;
import java.util.Deque;
public class Test3 {
public static void main(String[] args) {
//사용자 정의 클래스를 stack, queue 활용
//stack
// {
// Deque<Node> stack = new ArrayDeque<>();
// stack.push(new Node(3, 0, 4));
// stack.push(new Node(2, 8, 1));
// stack.push(new Node(1, 6, 3));
// stack.push(new Node(5, 5, 10));
//
// System.out.println(stack.pop());
// System.out.println(stack.peek());
//
// stack.push(new Node(9, 0, 3));
//
// while(!stack.isEmpty()){
// System.out.print(stack.pop()+" ");
// }
// }
//queue
{
Deque<Node> queue = new ArrayDeque<>();
queue.offer(new Node(3, 0, 4));
queue.offer(new Node(2, 8, 1));
queue.offer(new Node(1, 6, 3));
queue.offer(new Node(5, 5, 10));
System.out.println(queue.poll());
System.out.println(queue.peek());
queue.offer(new Node(9, 0, 3));
while(!queue.isEmpty()){
System.out.print(queue.pop()+" ");
}
}
}
//현재 노드의 좌표(y, x)와 이 노드까지의 비용c
static class Node{
int y, x, c;
Node(int y ,int x, int c){
this.y = y;
this.x = x;
this.c = c;
}
@Override
public String toString() {
return "Node [y=" + y + ", x=" + x + ", c=" + c + "]";
}
}
}int[] 스택, 큐 활용
package basic.Ch10_StackQueue;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Queue;
public class Test4 {
public static void main(String[] args) {
//사용자 정의 클래스 대신 int[] stack, queue 활용
//stack
{
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[] {3, 0, 4});
stack.push(new int[] {2, 8, 1});
stack.push(new int[] {1, 6, 3});
stack.push(new int[] {5, 5, 10});
System.out.println(Arrays.toString(stack.pop()));
System.out.println(Arrays.toString(stack.pop()));
stack.push(new int[] {9, 0, 3});
while(!stack.isEmpty()){
int[] node = stack.pop();
// System.out.print(Arrays.toString(stack.pop()));
System.out.print(node[0] + " ");
System.out.print(node[1] + " ");
System.out.print(node[2] + " ");
System.out.println();
}
}
//queue
{
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[] {3, 0, 4});
queue.offer(new int[] {2, 8, 1});
queue.offer(new int[] {1, 6, 3});
queue.offer(new int[] {5, 5, 10});
System.out.println(Arrays.toString(queue.poll()));
System.out.println(Arrays.toString(queue.peek()));
queue.offer(new int[] {9, 0, 3});
while(!queue.isEmpty()){
System.out.print(Arrays.toString(queue.poll()));
}
}
}
}- 사용자 정의보다 성능 향상
관련 문제
https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=java
https://school.programmers.co.kr/learn/courses/30/lessons/64061
2. 문제 풀이
인형 뽑기
package basic.Ch10_StackQueue;
import java.util.ArrayDeque;
import java.util.Deque;
// board
/*
[0,0,0,0,0],
[0,0,1,0,3],
[0,2,5,0,1],
[4,2,4,4,2],
[3,5,1,3,1]
바깥 배열(board)의 맨 뒤행부터 처리
*/
public class 크레인인형뽑기게임2 {
public static void main(String[] args) {
int[][] board = {{0,0,0,0,0}, {0,0,1,0,3}, {0,2,5,0,1}, {4,2,4,4,2}, {3,5,1,3,1}};
int[] moves = {1,5,3,5,1,2,1,4};
int answer = new 크레인인형뽑기게임2().solution(board, moves);
System.out.println(answer);
}
public int solution(int[][] board, int[] moves) {
int[] col_top_idx = new int[board[0].length]; // 일차원 배열에 각 컬럼별 최상위 인형의 index 관리
// 컬럼 (옆) 이동하면서
for (int col = 0; col < col_top_idx.length; col++) {
// 맨 꼭대기부터 시작 0 이 아닌 첫 번째 index
int top_idx = 0;
while( top_idx < board.length - 1 && board[top_idx][col] == 0 ) top_idx++;
col_top_idx[col] = top_idx;
}
Deque<Integer> bucket = new ArrayDeque<>(); // Stack -> ArrayDeque
int answer = 0;
for (int move : moves) { // 1 기반 index
if( col_top_idx[move -1] > board.length - 1 ) continue; // 해당 열에서 꺼낼 인형 X
// 꺼낼 인형이 있다.
int doll = board[ col_top_idx[move -1] ][move-1];
col_top_idx[move -1]++; // 현재 최상 높이의 인형을 꺼내고 하나 밑으로 조정
if( ! bucket.isEmpty() && bucket.peek() == doll) { // 같은 인형
bucket.pop(); // 맨 꼭대기 인형 꺼낸다.
answer += 2;
}else {
bucket.push(doll);
}
}
return answer;
}
}
/*
테스트 1 〉 통과 (0.07ms, 73MB)
테스트 2 〉 통과 (0.09ms, 79.3MB)
테스트 3 〉 통과 (0.06ms, 72.4MB)
테스트 4 〉 통과 (0.73ms, 83.7MB)
테스트 5 〉 통과 (0.08ms, 83.6MB)
테스트 6 〉 통과 (0.09ms, 81MB)
테스트 7 〉 통과 (0.16ms, 75.5MB)
테스트 8 〉 통과 (0.51ms, 98.4MB)
테스트 9 〉 통과 (0.30ms, 70.1MB)
테스트 10 〉 통과 (0.42ms, 89.7MB)
테스트 11 〉 통과 (0.93ms, 81.3MB)
*/탑
package basic;
import java.io.*;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
public class G5_2493_top {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
//결과를 저장 할 배열
int[] result = new int[N];
//탑의 인덱스, 높이를 저장할 배열
Stack<int[]> stack = new Stack<>();
for (int i = 0; i < N; i++) {
int height = Integer.parseInt(st.nextToken());
//스택의 top에 있는 탑의 높이가 지금 들어온 탑의 높이보다 낮으면 제거
while (!stack.isEmpty() && stack.peek()[1] < height) {
stack.pop();
}
//스택이 비어있으면 수신할 탑이 없기 때문애 0
if(stack.isEmpty()) {
result[i] = 0;
//그게 아니라면 스택의 top에 있는 탑이 신호를 수신
} else {
result[i] = stack.peek()[0] + 1;
}
//현재 들어온 탑을 스택에 저장
stack.push(new int[] {i, height});
}
for (int i = 0; i < N; i++) {
bw.write(result[i] + " ");
}
bw.flush();
bw.close();
br.close();
}
}
3. 마무리
1) WorkShop
문제 풀기 : https://www.acmicpc.net/problem/2493
다른 문제 풀어보기 or 수업때 다룬 문제를 리팩토링
'LG 유플러스 유레카 > 알고리즘' 카테고리의 다른 글
| [12일 차] 알고리즘 (Basic4) (0) | 2025.02.11 |
|---|---|
| [10일 차] 알고리즘 (Basic2) (0) | 2025.02.07 |
| [9일 차] 알고리즘 (Basic) (0) | 2025.02.06 |