백준 2636, 1339, 2110

🧀 백준 2636 : 치즈

https://www.acmicpc.net/problem/2636

2636번: 치즈

 

🧀 공기를 기준으로 탐색 수행, 치즈를 만나면 해당 치즈를 녹이고 방문처리, 공기를 만나면 해당 칸을 탐색후보에 넣고 수행한다.

🧀 아이디어는 나름 금방 생각했는데 생각보다 구현이 오래 걸렸다. 

🧀 재귀말고 stack 방식으로 구현해서 풀었다. 

🧀 tmi. 카페에서 이거 풀었는데 치즈가 먹고 싶었다. 하지만 그 카페는 치즈가 들어간 것을 팔지 않았다. 

 

🧀 전체 코드

import java.util.*;
import java.io.*;
public class p2636 {
    private static int row, col;
    private static int[][] map;
    private static boolean[][] visited;
    private static int[] dirX = { -1, 1, 0, 0 };
    private static int[] dirY = { 0, 0, -1, 1 };
    private static int cheese = 0;
    private static int temp;
    private static int time = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        row = Integer.parseInt(st.nextToken());
        col = Integer.parseInt(st.nextToken());
        map = new int[row][col];
        visited = new boolean[row][col];

        for (int i = 0; i < row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < col; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) {
                    cheese++;
                }
            }
        }

        while (cheese > 0) {
            temp = cheese;
            find();
            visited = new boolean[row][col];
            time++;
        }

        System.out.println(time);
        System.out.println(temp);
    }

    private static void find() {
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[] {0, 0});

        while (!stack.isEmpty()) {
            int[] pop = stack.pop();
            visited[pop[0]][pop[1]] = true;
            for (int i = 0; i < 4; i++) {
                int nextX = pop[0] + dirX[i];
                int nextY = pop[1] + dirY[i];

                if (!isValid(nextX,nextY)) {
                    continue;
                }

                if (visited[nextX][nextY]) {
                    continue;
                }

                if (map[nextX][nextY] == 0) {
                    stack.push(new int[] {nextX, nextY});
                } else if (map[nextX][nextY] == 1) {
                    map[nextX][nextY]--;
                    cheese--;
                    visited[nextX][nextY] = true;
                }
            }

        }
    }

    private static boolean isValid(int x, int y) {
        if (x < 0 || x >= row || y < 0 || y >= col) {
            return false;
        }
        return true;
    }

}

 

---

🗒 백준 1339 : 단어 수학 

 

https://www.acmicpc.net/problem/1339

1339번: 단어 수학

🗒 처음엔 문자의 빈도수 + 최대 자릿수를 저장해둔 다음 최대 자릿수 -> 빈도수 순으로 큰 값을 배정하도록 생각을 했었다.

🗒 그런데 다음과 같은 상황에선 반례가 된다. 처음 내가 생각했던 로직대로면 A에 9가 배정되어 1771이 답으로 나오는데, B에 9가 배정되는 것이 1772로 더 최대값이다. (계속 틀리길래 질문게시판에서 반례를 찾아봤는데, 이런 경우도 있다)

10
ABB
BC
BC
BC
BC
BC
BC
BC
BC
BC

🗒 그러므로, 그냥 알파벳 가중치를 담는 배열을 만들고, 문자열 하나 읽을때마다 해당 자릿수에 해당하는 사이즈만큼 배열 위치에 가중치를 넣어준다. 

🗒 ex ) ABBB : A 자리엔 1000, B자리엔 111 

🗒 그 다음 가중치 내림차순으로 배열을 탐색하면서 9 ~ 0까지 곱해서 계산해주고, 정답에 더해주면 된다. 

 

 

🗒 전체 코드

import java.util.*;
import java.io.*;
public class p1339 {
    private static int[] weight;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int index = 9;
        int sum = 0;
        weight = new int[26];

        for (int i = 0; i < n; i++) {
            calculate(br.readLine());
        }

        Arrays.sort(weight);

        for (int i = 25; i >= 0 && index >= 0; i--) {
            sum += (weight[i] * index);
            index--;
        }

        System.out.println(sum);
    }

    private static void calculate(String str) {
        int len = str.length();
        for (int i = 0; i < len; i++) {
            int index = str.charAt(i) - 65;
            weight[index] += Math.pow(10, len - i - 1);
        }
    }
}

 

---

📡백준 2110 : 공유기 설치

 

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

 

📡 공유기 간 최소 거리에 대해 설치 가능한 공유기 => 최소 거리가 X라면, 공유기 C대 설치 가능한가? 이렇게 바꿔서 생각 

📡 최소거리를 계속 계산해나가며 공유기 설치 가능하면 최소거리를 늘리고(아래 코드에서 mid 값이 최소 거리 의미, left를 mid + 1로 만든다.) , 설치 불가능하면 최소거리를 줄이는 방식으로 탐색한다. 

📡 이분 탐색을 활용하는 문제

 

📡 전체 코드 

import java.util.*;
import java.io.*;
public class p2110 {
    private static int house, wifi;
    private static int[] housePos;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        house = Integer.parseInt(st.nextToken());
        wifi = Integer.parseInt(st.nextToken());

        housePos = new int[house];
        for (int i = 0; i < house; i++) {
            housePos[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(housePos);

        int left = 1;
        int right = housePos[house-1] - housePos[0] + 1;

        while (left < right) {
            int mid = (left + right) / 2;
            int count = calculate(mid);
            if (count >= wifi) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        System.out.println(left-1);

    }

    private static int calculate(int minDis) {
        int count = 1;
        int before = housePos[0];
        for (int i = 1; i < house; i++) {
            if (before + minDis <= housePos[i]) {
                before = housePos[i];
                count++;
            }
        }
        return count;
    }
}