[Week37] 스터디 회고

슬슬 프로그래머스 LV2 문제 다 풀었지 싶어서 확인 했더니 아직도 52문제나 안풀었다...

LV3 넘어가긴 해야하는데, 지금도 간간히 풀긴 하지만 주로 푸는 문제는 LV2 라서 고민이 있다.

스터디 인원들이 슬슬 고착화 되면서 난이도는 계속해서 올라가는 기분은 들어서 문제 난이도가 올라간다고 쉽게 스터디가 와해되지는 않을 것 같은 느낌적인 느낌?

• LV2 - 지게차와 크레인
•  G2 - 칵테일
•  G5 - 1로 만들기 2

칵테일 문제는 개인적으로 조금 오랫동안 고생하고 결국 다른 풀이도 참조해서 풀었다 ㅎㅎ..

---

[ 📌 내 문제 풀이 with Java ]

👉 지게차와 크레인

그래프 문제인데 백준의 치즈나 빙산 같은 문제와 유사한 풀이이다.

삭제해야하는 노드를 바로 삭제하면 동작중인 로직에 영향을 주기 때문에 따로 저장 했다가 로직이 끝난 후에 일괄로 삭제 처리 되도록 구현 했다.

 

기본적인 그래프 문제라서 크게 어렵거나 시간을 사용하지는 않았다.

이제는 기계적으로 풀 수 있는 유형의 문제

/**
 * Author    : Lee In Bok
 * Date      : 2025.03.02(Sun)
 * Runtime   : 22.95 ms
 * Memory    : 94.9 MB
 * Algorithm : Graph Search
 */
package com.year2025.Week37;

import java.util.LinkedList;
import java.util.Queue;

public class LV2_388353 {
    public static void main(String[] args) {
        Solution sol = new Solution();

        System.out.println(
                sol.solution(
                        new String[]{"AZWQY", "CAABX", "BBDDA", "ACACA"},
                        new String[]{"A", "BB", "A"}
                )
        );
    }

    static class Solution {

        public static int N;
        public static int M;
        public static int ans;
        public static int[] dx = {0, 1, 0, -1};
        public static int[] dy = {1, 0, -1, 0};

        public int solution(String[] storage, String[] requests) {
            N = storage.length;
            M = storage[0].length();
            Node[][] board = new Node[N + 2][M + 2];
            ans = N * M;

            for(int i = 0; i < N; i++) {
                String[] container = storage[i].split("");

                for(int j = 0; j < M; j++) {
                    int x = i + 1;
                    int y = j + 1;

                    board[x][y] = new Node(x, y, container[j]);
                }
            }

            for(String request : requests) {
                String command = Character.toString(request.charAt(0));

                if(request.length() == 1) {
                    useForkLift(board, command);
                } else {
                    useCrane(board, command);
                }
            }

            return ans;
        }

        public static void useForkLift(Node[][] board, String request) {
            Queue<Node> q = new LinkedList<>();
            // 제거 목록을 임시 저장한다. (이유: 로직이 동작하는동안 컨테이너를 빼면 다른 컨테이너가 영향을 받음)
            Queue<Node> shipOutList = new LinkedList<>();
            boolean[][] visited = new boolean[N + 2][M + 2];

            q.add(new Node(0, 0));
            visited[0][0] = true;

            while(!q.isEmpty()) {
                Node curNode = q.poll();

                for(int i = 0; i < 4; i++) {
                    int nextX = curNode.x + dx[i];
                    int nextY = curNode.y + dy[i];
                    
                    if(isValid(nextX, nextY) && !visited[nextX][nextY]) {
                        visited[nextX][nextY] = true;
                        Node nextNode = new Node(nextX, nextY);
                        
                        // null(= empty)
                        if(board[nextX][nextY] == null) {
                            q.add(nextNode);
                        } else if(board[nextX][nextY].isShipOutTarget(request)) {
                            shipOutList.add(nextNode);
                        }
                    }
                }
            }

            // 제거 목록으로 저장된 컨테이너 좌표 삭제
            while(!shipOutList.isEmpty()) {
                Node target = shipOutList.poll();

                ans--;
                board[target.x][target.y] = null;
            }
        }

        // 크레인은 지형적인 영향을 안받기 때문에 컨테이너 전부 제거
        public static void useCrane(Node[][] board, String request) {
            for(int i = 0; i < board.length; i++) {
                for(int j = 0; j < board[i].length; j++) {
                    if(board[i][j] != null && request.equals(board[i][j].val)) {
                        ans--;
                        board[i][j] = null;
                    }
                }
            }
        }

        public static boolean isValid(int x, int y) {
            return 0 <= x && x < N + 2 && 0 <= y && y < M + 2;
        }
    }

    static class Node {
        int x;
        int y;
        String val;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public Node(int x, int y, String val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }

        public boolean isShipOutTarget(String val) {
            return this.val.equals(val);
        }
    }
}

---

👉 칵테일

 

혼자서 풀 수 있을거 같아서 혼자서 전전긍긍 하다가 최소공배수, 최대공약수 이용하는 문제라는걸 알게 되었다.

그래프 문제라는건 쉽게 알 수 있었는데, 그래프 내에서 각 노드간의 비율을 조율하는 과정이 쉽게 다가오지 않았었다.

 

특히 그래프 탐색을 시작할 때 비율이 정해져 있으니 임의의 노드로 시작할 때 최소 공배수로 값을 세팅하는 부분에서 나는 생각하지 못 했기 때문에 쉽게 풀지 못 했다.

/**
 * Author    : Lee In Bok
 * Date      : 2025.03.08(Sat)
 * Runtime   : 120 ms
 * Memory    : 15820 KB
 * Algorithm : Graph, Math
 */

package com.year2025.Week37;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class G2_1033 {

    public static List<Node>[] graph;
    public static boolean[] visited;
    public static long[] ratio;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        long lcm = 1;
        graph = new ArrayList[N];
        visited = new boolean[N];
        ratio = new long[N];

        for(int i = 0; i < N; i++) {
            graph[i] = new ArrayList<>();
        }

        for(int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            int q = Integer.parseInt(st.nextToken());

            // 최소 공배수 구하기 (각 노드간의 비율을 맞추기 위해서 필요)
            lcm *= p * q / gcd(p, q);
            graph[a].add(new Node(b, p, q));
            graph[b].add(new Node(a, q, p));
        }

        // 찾고자 하는 N 의 재료를 시작점으로 최소 공배수를 갖고 그래프 탐색을 통해서 노드간 비율에 따라서 조율
        long ggcd = ratio[N - 1] = lcm;
        dfs(N - 1);

        // 조율된 값을 최소 값으로 만들기 위해서 최대 공약수를 구한다.
        for(int i = 0; i < ratio.length; i++) {
            ggcd = gcd(ggcd, ratio[i]);
        }

        // 최대 공약수로 값을 나누어 출력
        for (int i = 0; i < N; i++) {
            System.out.print(ratio[i] / ggcd + " ");
        }
    }

    public static void dfs(int node) {
        visited[node] = true;

        for(Node next : graph[node]) {
            if(!visited[next.b]) {
                // 노드 사이의 정해진 비율에 따라서 값 조율
                ratio[next.b] = ratio[node] * next.q / next.p;
                dfs(next.b);
            }
        }
    }

    public static long gcd(long n1, long n2) {
        return n2 == 0 ? n1 : gcd(n2, n1 % n2);
    }

    static class Node {
       int b;
       int p;
       int q;

        public Node(int b, int p, int q) {
            this.b = b;
            this.p = p;
            this.q = q;
        }
    }
}

---

👉 1로 만들기2

 

큐랑 스택을 이용해서 문제를 풀었는데, 풀고 나니까 그래프 문제 같기도 하다.

그래프 문제를 풀 때 큐랑 스택을 자주 이요하기도 하니까 그렇게 느끼는 건가

 

중요한건 1에 도달하는 순간 왔던 경로를 되돌아갈 수 있는 코드를 만들어야 하는 것 이었고, 이런 비슷한 유형을 풀었던 경험이 있어서 배열에 각 노드 이전 노드를 기록 해두었다.

/**
 * Author    : Lee In Bok
 * Date      : 2025.03.04(Tue)
 * Runtime   : 180 ms
 * Memory    : 21672 KB
 * Algorithm : Queue, Stack
 */
package com.year2025.Week37;

import java.util.*;

public class G5_12852 {

    public static Queue<Integer> q = new LinkedList<>();
    public static int[] seq;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Stack<Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int N = sc.nextInt();

        seq = new int[N + 1];

        search(N);

        int temp = 1;
        stack.push(temp);

        // 역추적: 목표로 하는 1 번 배열방에서 이전 각 요소로 저장된 이전 노드 번호를 타고 간다.
        while(temp != N) {
            stack.push(seq[temp]);
            temp = seq[temp];
        }

        // 경로 사이즈 출력
        System.out.println(stack.size() - 1);

        while(!stack.isEmpty()) {
            sb.append(stack.pop()).append(" ");
        }

        // 경로 출력
        System.out.println(sb);
    }

    public static void search(int N) {
        q.add(N);

        while(!q.isEmpty()) {
            int cur = q.poll();

            if(cur == 1) {
                break;
            }

            if(cur % 3 == 0) {
                addAndCheck(cur, cur / 3);
            }

            if(cur % 2 == 0) {
                addAndCheck(cur, cur / 2);
            }

            addAndCheck(cur, cur - 1);
        }
    }

    // 경로 추적을 위해서 seq 배열에 이전 노드의 번호를 저장 후 다음 노드를 큐에 담는다.
    public static void addAndCheck(int cur, int next) {
        if(seq[next] == 0) {
            seq[next] = cur;  // 다음 숫자에 이전 숫자 기록
            q.add(next);
        }
    }
}

---

[📌 아쉬운 점...]

칵테일 문제가 혼자서 풀 수 있을 것 같은 느낌이 진짜 물씬 풍겨서 계속 잡고 있었는데, 결국 다른 풀이를 보고 말았다.

다른 풀이를 보고 푼 것은 아쉽지 않았는데, 오랫동안 잡고 있다가 포기 하니까 아쉬웠다.