석유 시추(https://school.programmers.co.kr/learn/courses/30/lessons/250136)

문제 설명

세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다.

예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다.

시추관은 위 그림처럼 설치한 위치 아래로 끝까지 뻗어나갑니다. 만약 시추관이 석유 덩어리의 일부를 지나면 해당 덩어리에 속한 모든 석유를 뽑을 수 있습니다. 시추관이 뽑을 수 있는 석유량은 시추관이 지나는 석유 덩어리들의 크기를 모두 합한 값입니다. 시추관을 설치한 위치에 따라 뽑을 수 있는 석유량은 다음과 같습니다.

석유가 묻힌 땅과 석유 덩어리를 나타내는 2차원 정수 배열 land가 매개변수로 주어집니다. 이때 시추관 하나를 설치해 뽑을 수 있는 가장 많은 석유량을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 500
  • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
  • land[i][j]는 i+1행 j+1열 땅의 정보를 나타냅니다.
  • land[i][j]는 0 또는 1입니다.
  • land[i][j]가 0이면 빈 땅을, 1이면 석유가 있는 땅을 의미합니다.
    정확성 테스트 케이스 제한사항
• 1 ≤ land의 길이 = 땅의 세로길이 = n ≤ 100
  • 1 ≤ land[i]의 길이 = 땅의 가로길이 = m ≤ 500
    효율성 테스트 케이스 제한사항
• 주어진 조건 외 추가 제한사항 없습니다.

입출력 예

land	result
[[0, 0, 0, 1, 1, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1, 1, 0], [1, 1, 1, 0, 0, 0, 0, 0], [1, 1, 1, 0, 0, 0, 1, 1]]	9
[[1, 0, 1, 0, 1, 1], [1, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 1], [1, 0, 0, 1, 0, 0], [1, 0, 0, 1, 0, 1], [1, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1]]	16
#### 입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2

시추관을 설치한 위치에 따라 뽑을 수 있는 석유는 다음과 같습니다.

풀이

문제 파악

• 석유 덩어리에 포함된 칸의 수는 1의 값을 가지는 인접한 칸의 수이다.
• 시추관이 각 열마다 지나가기 때문에 석유 덩어리의 칸 수가 가장 많이 위치하는 열을 찾고 해당 열에서 얻을 수 있는 석유량을 반환

1. 각 열 별로 지나가는 칸 중 석유가 존재하는 칸에서 시작하는 DFS를 통해 열 별로 획득할 수 있는 총 석유량을 구하고 최대치를 갱신
2. 각 열 별로 지나가는 칸 중 석유가 존재하는 칸에서 시작하는 BFS를 통해 해당 칸으로부터 얻을 수 있는 총 석유량을 구하고 각 열을 Set에 저장하여 열 인덱스 별로 얻을 수 있는 총량을 Map에 저장
   

접근 방법

풀이1

1. column 별로 석유가 존재하는 칸(1인 칸)에서 dfs를 시행하기 위해 이중 for문의 첫 변수를 column으로 두고 column 별로 visited와 count 초기화
2. column 별 dfs() 시행:
   • 시작점에서부터 인접한 칸이 유효한 칸이면서 방문하지 않은 석유 칸이라면 해당 칸에서 시작하는 dfs() 재귀 호출 -> 이 부분에서 효율성 문제가 발생한 듯?
   • 재귀 호출된 함수 종료시, 1을 반환하고 재귀 호출 횟수만큼(탐색한 칸의 횟수만큼) count에 더해진 후 해당 count를 최초 dfs를 시행한 solution 함수 내의 count에 저장
3. column 별로 구한 석유 칸 수를 기존 최대 석유 칸 수 maxCount와 비교 후 갱신하고 최종적으로 maxCount를 답으로 반환

• 로직은 맞았는데 효율성에서 떨어졌다...

풀이2

1. land 내의 모든 칸 중 석유가 존재하고 아직 방문하지 않은 칸에서 시작하는 bfs 시행
2. bfs():
   • bfs() 로직을 통해 해당 칸에서 상하좌우 방향으로 인접하는 석유 칸을 구하되 총 석유 칸 수와 지나는 열 저장
   • 모든 탐색 종료 후 시작 칸과 인접한 총 석유 칸 수 count 반환
3. totalCount에 column 별로 bfs를 통해 구한 석유 칸을 저장하되 기존에 저장된 값이 있으면 해당 값에 추가
4. 모든 칸에 대해 bfs와 totalCount의 갱신이 끝났다면, column 별로 저장된 석유 칸의 값을 비교/갱신하여 answer에 저장하고 답으로 반환

• 성공!
  

코드 구현

코드1(column 별 DFS - 효율성 테스트 실패)

class Solution {
    public static int[] dc = new int[] {0, 0, 1, -1};
    public static int[] dr = new int[] {1, -1, 0, 0};

    public int solution(int[][] land) {
        boolean[][] visited;
        int maxCount = 0;

        for(int c = 0; c < land[0].length; c++) {
            visited = new boolean[land.length][land[0].length];
            int count = 0;
            for(int r = 0; r < land.length; r++) {
                if(land[r][c] == 1 && !visited[r][c]) {
                    count += dfs(r, c, land, visited);
                }
            }
            maxCount = Math.max(maxCount, count);
        }

        return maxCount;
    }

    private int dfs(int r, int c, int[][] land, boolean[][] visited) {
        visited[r][c] = true;
        int count = 1;

        for(int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if(nr >= 0 && nc >= 0 && nr < land.length && nc < land[0].length && !visited[nr][nc] && land[nr][nc] == 1) {
                count += dfs(nr, nc, land, visited);
            }
        }

        return count;
    }
}

코드2(BFS)

import java.util.*;

public class Solution {
    public static boolean[][] visited;
    public static int[] dr = {1, 0, -1, 0};
    public static int[] dc = {0, 1, 0, -1};

    public int solution(int[][] land) {
        visited = new boolean[land.length][land[0].length];
        Map<Integer, Integer> totalCount = new HashMap<>();

        int answer = 0;

        for (int r = 0; r < land.length; r++) {
            for (int c = 0; c < land[0].length; c++) {
                if (land[r][c] == 1 && !visited[r][c]) {
                    Set<Integer> cols = new HashSet<>();
                    int count = bfs(r, c, land, cols);

                    for (int col : cols) {
                        totalCount.put(col, totalCount.getOrDefault(col, 0) + count);
                    }
                }
            }
        }

        for (int value : totalCount.values()) {
            answer = Math.max(answer, value);
        }

        return answer;
    }

    private int bfs(int r, int c, int[][] land, Set<Integer> cols) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{r, c});
        visited[r][c] = true;

        int count = 0;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int cr = cur[0];
            int cc = cur[1];
            count++;
            cols.add(cc);

            for (int i = 0; i < 4; i++) {
                int nr = cr + dr[i];
                int nc = cc + dc[i];
                if (nr >= 0 && nr < land.length && nc >= 0 && nc < land[0].length && land[nr][nc] == 1 && !visited[nr][nc]) {
                    queue.offer(new int[]{nr, nc});
                    visited[nr][nc] = true;
                }
            }
        }
        return count;
    }
}

전력망 둘로 나누기(https://school.programmers.co.kr/learn/courses/30/lessons/86971)

문제 설명

n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.

송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 2 이상 100 이하인 자연수입니다.
• wires는 길이가 n-1인 정수형 2차원 배열입니다.
  • wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과 v2번 송전탑이 전선으로 연결되어 있다는 것을 의미합니다.
  • 1 ≤ v1 < v2 ≤ n 입니다. 전력망 네트워크가 하나의 트리 형태가 아닌 경우는 입력으로 주어지지 않습니다.

입출력 예

n	wires	result
9	[[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]	3
4	[[1,2],[2,3],[3,4]]	0
7	[[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]]	1
#### 입출력 예 설명
입출력 예 #1

• 다음 그림은 주어진 입력을 해결하는 방법 중 하나를 나타낸 것입니다.
  

• 4번과 7번을 연결하는 전선을 끊으면 두 전력망은 각 6개와 3개의 송전탑을 가지며, 이보다 더 비슷한 개수로 전력망을 나눌 수 없습니다.
• 또 다른 방법으로는 3번과 4번을 연결하는 전선을 끊어도 최선의 정답을 도출할 수 있습니다.
  입출력 예 #2
• 다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.
  

• 2번과 3번을 연결하는 전선을 끊으면 두 전력망이 모두 2개의 송전탑을 가지게 되며, 이 방법이 최선입니다.
  입출력 예 #3
• 다음 그림은 주어진 입력을 해결하는 방법을 나타낸 것입니다.
  

• 3번과 7번을 연결하는 전선을 끊으면 두 전력망이 각각 4개와 3개의 송전탑을 가지게 되며, 이 방법이 최선입니다.

풀이

문제 파악

• 트리 구조로 연결된 송전탑을 최대한 비슷하게 2개의 부분으로 나누어야 함
• 간선 하나를 제거하였을 때 2개의 부분을 구성하는 노드의 개수 차이가 최소한으로 나도록 하는 경우의 수를 도출
• 트리 구조에서 탐색을 수행하면 부모 노드에서 자식 노드 순으로 탐색이 된다는 특징을 이용하여 간선을 제거하고 DFS를 수행하여 해당 부분의 노드 개수를 도출

접근 방법

• 주어진 간선에 대한 배열 wires를 해시맵 형태의 인접 리스트로 변형
• 각 경우의 수 도출을 위한 DFS 수행

1. 인접 리스트 내 각 노드에 접근하여 간선을 직접 제거 후 dfs 실행
2. dfs 내에서 방문 여부를 체크하며 다음 노드를 방문하며 count++
3. dfs에서 계산한 count와 (전체 노드(n) - count)의 차이를 계산하고 기존의 min과 비교하여 갱신
   • 이 때, 간선을 제거해도 두 묶음으로 나뉘지 않는다면, dfs는 모든 노드를 다 돌고 count는 9가 됨
4. 제거한 간선 복구 후 다음 간선 제거(간선 개수 만큼 반복)

• 모든 노드에 대해 위 과정을 반복 후 최종적으로 갱신된 min을 답으로 반환
  

코드 구현

import java.util.*;

class Solution {
    public int solution(int n, int[][] wires) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int min = n;

        for (int i = 1; i <= n; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] e : wires) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }

        for (int[] e : wires) {
            int v1 = e[0];
            int v2 = e[1];

            boolean[] visited = new boolean[n + 1];

            graph.get(v1).remove(Integer.valueOf(v2));
            graph.get(v2).remove(Integer.valueOf(v1));

            int count = dfs(graph, 1, visited);

            int diff = Math.abs(count - (n - count));
            min = Math.min(min, diff);

            graph.get(v1).add(v2);
            graph.get(v2).add(v1);
        }
        return min;
    }

    private int dfs(Map<Integer, List<Integer>> graph, int v, boolean[] visited) {
        visited[v] = true;
        int count = 1;

        for (int next : graph.get(v)) {
            if (!visited[next]) {
                count += dfs(graph, next, visited);
            }
        }

        return count;
    }
}

Coin Change(https://leetcode.com/problems/coin-change)

문제 설명

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

문제 해석

여러 종류의 동전을 나타내는 정수 배열 coins가 주어집니다. 또한, amount라는 총 금액이 주어집니다.

이 금액을 만들기 위해 필요한 최소 동전의 수를 반환하세요. 만약 이 금액을 주어진 동전으로 만들 수 없다면 -1을 반환하세요.

각 동전의 개수는 무한히 많다고 가정할 수 있습니다.

제한사항

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

입출력 예

Example 1:

• Input: coins = [1,2,5], amount = 11
• Output: 3
• Explanation: 11 = 5 + 5 + 1

• Example 2:*
• Input: coins = [2], amount = 3
• Output: -1

• Example 3:*
• Input: coins = [1], amount = 0
• Output: -1

풀이

문제 파악

• 동전의 종류(coins)와 목표 금액(amount)이 주어졌을 때, 목표 금액을 만들기 위해 필요한 최소 동전 개수를 구하는 문제
• 주어진 동전 내의 조합으로 목표 금액을 만들 수 없을 경우 -1을 반환

접근 방법

• 문제의 답은 목표 금액을 만들 수 있는 동전의 조합 중 동전의 개수가 최소가 되는 값이며, 이를 위해 특정 금액 별 구성 동전의 개수가 최소인 경우 구하는 점화식을 구해야 한다. 이 경우, 다음과 같은 점화식을 유도할 수 있다.

$$ F(n) = \min\left(…\mathrm{F}(n-\mathrm{coins}[i])\right) + 1 \ F(0) = 0 $$

• 해당 점화식을 바탕으로 Bottom-Up 방식의 코드를 구현하면 다음과 같다.

1. 금액을 가리키는 인덱스에 값으로 동전 개수를 저장하는 배열 생성하고 모든 값을 Integer.MAX_VALUE로 초기화. 0번째 값에는 0을 저장
2. for 문 내에서 목표 금액까지의 각 금액을 만들 수 있는 최소 동전 개수를 각각 저장/갱신함
   • 조합 가능한 금액(인덱스)와 해당 금액을 만들 수 있는 최소 동전 개수(값)으로 이루어진 배열 dp 완성
3. 배열[목표 금액]의 값이 Integer.MAX_VALUE가 아닐 경우(값이 갱신되었을 경우), 해당 값이 목표 금액을 만들기 위해 필요한 최소 동전 개수가 됨
   • 배열[목표 금액]의 값이 Integer.MAX_VALUE일 경우, -1 반환

코드 구현

import java.util.*;

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < amount; i++) {
            if (dp[i] == Integer.MAX_VALUE) continue;
            for (int coin : coins) {
                // Prevent overflow by checking if i + coin will overflow
                if (coin > 0 && i <= amount - coin) {
                    dp[i + coin] = Math.min(dp[i + coin], dp[i] + 1);
                }
            }
        }
        return (dp[amount] == Integer.MAX_VALUE) ? -1 : dp[amount];
    }
}

네트워크(https://school.programmers.co.kr/learn/courses/30/lessons/43162)

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

n	computers	return
3	[[1, 1, 0], [1, 1, 0], [0, 0, 1]]	2
3	[[1, 1, 0], [1, 1, 1], [0, 1, 1]]	1
#### 입출력 예 설명
예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2 아래와 같이 1개의 네트워크가 있습니다.

풀이

문제 파악

• 노드의 개수와 간선의 정보가 주어진 문제에서 개별 네트워크의 개수를 구하라
  • 간선으로 연결되지 않은 노드의 집합을 개별 네트워크로 본다.
• dfs을 통해 연결된 모든 노드에 방문했음에도 방문하지 않은 노드가 존재한다면 다른 네트워크가 존재한다는 의미
  • 방문하지 않은 노드로부터 dfs 추가 실행

접근 방법

1. 방문 여부를 저장할 visited 배열을 초기화 후 false로 다 채움. for문 내 dfs 실행
2. dfs(): 현재 노드에 방문 여부를 true로 저장하고, 해당 노드와 연결된 다른 노드에 방문 여부를 확인하고 dfs 함수의 인자로 전달. 완전 탐색 후 solution 함수로 돌아감
3. for문 내에서 방문을 안 한 노드가 아직도 존재한다면, 네트워크의 개수를 1 추가하고, 해당 노드에 대해 dfs 추가로 실행
4. 방문을 안 한 노드가 없을 때까지 로직 반복 후 네트워크 개수인 answer를 반환
   

코드 구현

import java.util.*;

class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[computers.length];

        Arrays.fill(visited, false);

        for(int i = 0; i < computers.length; i++){
            if(visited[i] == false){
                answer++;
                dfs(i, visited, computers);
            }
        }
        return answer;
    }

    public void dfs(int node, boolean[] visited, int[][] computers){
        visited[node] = true;

        for(int i = 0; i < computers.length; i++){
            if(visited[i] == false && computers[node][i] == 1){
                dfs(i, visited, computers);
            }
        }
    }
}

Network Delay Time(https://leetcode.com/problems/network-delay-time)

문제 설명

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = ($$u_{i}$$, $$v_{i}$$, $$w_{i}$$), where $$u_{i}$$ is the source node, $$v_{i}$$ is the target node, and $$w_{i}$$ is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

문제 해석

• 1~n개의 노드로 구성된 네트워크가 제공된다.
• [출발 노드 번호, 도착 노드 번호, 걸리는 시간]이 저장된 2차원 배열 times도 제공된다.
• 노드 k에서 신호를 보낼 때, 모든 노드에 신호가 도달하는 최소 시간을 반환하라. 만약 모든 노드에 신호가 도달하는 것이 불가능하면 -1을 반환하라.

제한사항

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 0 <= wi <= 100
• All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

입출력 예

Example 1:

• Input: times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4, k = 2
• Output: 2

• Example 2:*

• Input: times = [[1, 2, 1]], n = 2, k = 1
• Output: 1

• Example 3:*

• Input: times = [[1, 2, 1]], n = 2, k = 2
• Output: -1

풀이

문제 파악

• times 배열은 노드와 노드 간의 간선에 대한 이동시간을 담은 배열
  • 해당 배열을 인접 리스트로 변환해 노드 별 정보를 저장하도록 한다.
• 문제에서 요구하는 최소 시간은 다익스트라로 구한 노드 별로 도달하는 모든 시간 중 최대 시간과 같음
  • 다익스트라로 도출된 최대 시간이 모든 노드에 도달할 경우의 시간이 됨

접근 방법

1. 출발/도착 노드와 이동 시간에 대한 배열을 인접 리스트로 변환
2. 다익스트라 실행 시 먼저 각 노드에 도달할 때 걸리는 시간을 저장할 time 배열을 선언하고 모든 값을 Integer.MAX_VALUE로 초기화
3. 우선 순위 큐를 초기화하고 큐에 시작 노드와, 소요시간 0을 주고 다익스트라 로직 시작
   • dijkstra(): 현재 노드의 정보를 저장하고 현재 노드에서 접근할 수 있는 노드들에 대해 걸리는 시간이 기존에 저장한 시간보다 적게 걸릴 경우 distance 배열의 값을 갱신하고 큐에 해당 노드를 add
4. 다익스트라 실행 루프가 끝났을 경우 find 함수에 distance 배열과 노드의 수 n를 주고 실행
   • find(): 배열 내에 MAX_VALUE 값이 있다면 -1(도달하지 못한 노드가 존재한다는 의미), 없다면 maxTime을 배열 내 최대값으로 갱신하고(배열이 모든 노드에 도달할 때 최소 시간을 저장해둔 것이므로 이 중 최대값은 모든 노드에 도달할 때의 시간을 의미) maxTime 반환

코드 구현

import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            graph.put(i, new ArrayList<>());
        }

        for(int[] time : times) {
            // u -> v 로 가는 경로와 가중치 w를 그래프에 추가
            graph.get(time[0]).add(new int[]{time[1], time[2]});
        }

        return dijkstra(graph, k, n);
    }

    private int dijkstra(Map<Integer, List<int[]>> graph, int start, int n) {
        int[] distance = new int[n + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(a -> a[1]));
        pq.add(new int[]{start, 0});

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int node = cur[0];
            int time = cur[1];

            if (time > distance[node]) continue;

            // 인접 노드 확인
            for (int[] edge : graph.get(node)) {
                int nextNode = edge[0];
                int nextTime = time + edge[1];

                if (nextTime < distance[nextNode]) {
                    distance[nextNode] = nextTime;
                    pq.add(new int[]{nextNode, nextTime});
                }
            }
        }
        return find(distance, n);
    }

    private int find(int[] distance, int n) {
        int maxTime = 0;
        for (int i = 1; i <= n; i++) {
            if (distance[i] == Integer.MAX_VALUE) {
                return -1;
            }
            maxTime = Math.max(maxTime, distance[i]);
        }

        return maxTime;
    }
}

미로 탈출(https://school.programmers.co.kr/learn/courses/30/lessons/159993)

문제 설명

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

제한사항

• 5 ≤ maps의 길이 ≤ 100
• 5 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
    • S : 시작 지점
    • E : 출구
    • L : 레버
    • O : 통로
    • X : 벽
  • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
  • 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

입출력 예

maps	result
["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]	16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]	-1
#### 입출력 예 설명
입출력 예 #1

주어진 문자열은 다음과 같은 미로이며

다음과 같이 이동하면 가장 빠른 시간에 탈출할 수 있습니다.

4번 이동하여 레버를 당기고 출구까지 이동하면 총 16초의 시간이 걸립니다. 따라서 16을 반환합니다.

입출력 예 #2

주어진 문자열은 다음과 같은 미로입니다.

시작 지점에서 이동할 수 있는 공간이 없어서 탈출할 수 없습니다. 따라서 -1을 반환합니다.

풀이

문제 파악

• 2번의 BFS 탐색이 필요
  1. 시작 지점에서 레버까지의 최단거리 구하기
  2. 레버에서부터 출구까지의 최단거리 구하기
  3. 구한 두 최단거리를 더한 뒤 답으로 반환
     

접근 방법

1. 인접한 상하좌우의 cell로 접근하기 위한 배열 dr/dc, map의 행열 길이 rowLength/colLength, 방문여부를 저장할 visited와 최단거리를 담을 answer 세팅
2. map 전체를 이중 for문으로 돌면서 시작 지점(’S’), 레버(’L’), 출구(’E’)의 좌표를 배열[row, col]로 저장하고 bfs()를 시작 지점부터 레버 위치까지 1번, 레버 위치부터 출구까지 1번 시행해서 각각의 최단 거리를 구함
3. bfs 내의 루프에서 현재 위치가 목표 지점인지 검사하고 인접한 상하좌우의 칸이 유효한 위치인지 벽(’X’)인지 여부와 해당 칸에 대한 방문여부를 검사하고 해당 조건을 모두 통과했을 경우 큐에 해당 칸을 예약
4. 3번을 반복하여 목표 지점에 도달할 경우 거리 dist를, 도달할 수 없다면 -1을 반환
   • 반환된 -1은 그대로 main 함수에서 -1로 반환됨
5. 시작 지점부터 레버 위치까지의 최단 거리와 레버 위치부터 출구까지의 최단 거리를 더한 값을 답으로 반환
   

코드 구현

import java.util.*;

public class Solution {
    int[] dr = {-1, 1, 0, 0};
    int[] dc = {0, 0, 1, -1};
    int rowLength = 0;
    int colLength = 0;
    boolean[][] visited;
    int answer = 0;

    public int solution(String[] maps) {
        rowLength = maps.length;
        colLength = maps[0].length();
        int[] startLocation = new int[2];
        int[] leverLocation = new int[2];
        int[] endLocation = new int[2];

        for(int i = 0; i < rowLength; i++) {
            for(int j = 0; j < colLength; j++) {
                char ch = maps[i].charAt(j);
                if (ch == 'S') {
                    startLocation[0] = i;
                    startLocation[1] = j;
                } else if (ch == 'L') {
                    leverLocation[0] = i;
                    leverLocation[1] = j;
                } else if (ch == 'E') {
                    endLocation[0] = i;
                    endLocation[1] = j;
                }
            }
        }

        int leverDist = bfs(maps, startLocation, leverLocation);
        if (leverDist == -1) return -1; // 레버에 도달할 수 없는 경우

        int exitDist = bfs(maps, leverLocation, endLocation);
        if (exitDist == -1) return -1; // 출구에 도달할 수 없는 경우

        answer = leverDist + exitDist;
        return answer;
    }

    private int bfs(String[] maps, int[] start, int[] target) {
        visited = new boolean[rowLength][colLength];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{start[0], start[1], 0});
        visited[start[0]][start[1]] = true;

        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0];
            int c = cur[1];
            int dist = cur[2];

            if(r == target[0] && c == target[1]) {
                return dist;
            }

            for(int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if(0 <= nr && nr < rowLength && 0 <= nc && nc < colLength && maps[nr].charAt(nc) != 'X' && !visited[nr][nc]) {
                    queue.offer(new int[]{nr, nc, dist + 1});
                    visited[nr][nc] = true;
                }
            }
        }
        return -1; // 목표 지점에 도달할 수 없는 경우
    }
}

소수 찾기(https://school.programmers.co.kr/learn/courses/30/lessons/42839)

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2
#### 입출력 예 설명
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2 [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

풀이

문제 파악

• 숫자들을 조합하여 만들 수 있는 소수가 몇개인지 알아내는 문제

1. 숫자를 조합하기 : 재귀를 이용하여 순열 구하는 방식으로 구현
2. 소수를 판별하기 : $2$ ~ $\sqrt{M}$ 사이의 값들로 숫자 $M$을 나눠서 하나라도 나누어 떨어지는 숫자가 있는지 확인하는 방식으로 구현

접근 방법

• 방문 여부 판단하는 visited, 조합할 수 있는 모든 수를 저장하는 ans 선언

1. solution 함수: visited, ans, 소수의 수를 저장할 answer를 초기화. dfs를 통해 ans를 완성하고 ans 전체 수에 대해 소수인지 isPrime으로 검사하고 소수이면 answer++.
2. dfs 함수: numbers의 길이 만큼 for문을 돌리면서 해당 index의 자리 수를 더한 문자열을 int 타입으로 바꾸고 ans에 중복없이 추가. dfs를 재귀호출하며 끝까지 수행 후 방문여부를 false로 바꾸고 backTracking. 재귀 호출 종료 조건으로 dfs의 호출횟수(즉, 문자열 자리수 추가 횟수) > numbers 문자열의 길이를 둠
3. isPrime 함수: 주어진 수 num에 대해 소수인지 판단 → 2보다 작다면 소수x, 2부터 √num보다 작은 자연수 i까지의 범위에 대해 num이 i로 나머지 없이 나눠진다면 소수x. 위 조건을 통과하면 true 반환
   

코드 구현

import java.util.ArrayList;

class Solution {
    public static boolean[] visited;
    public static ArrayList<Integer> ans;
    public int solution(String numbers) {
        visited = new boolean[7];
        ans = new ArrayList<>();
        int answer = 0;

        dfs(0, numbers, "");

        for (Integer num : ans) {
            if (isPrime(num)) {
                answer++;
            }
        }
        return answer;
    }

    public void dfs(int depth, String numbers, String s) {
        if (depth > numbers.length()) {
            return;
        }

        for (int i = 0; i < numbers.length(); i++) {
            if(!visited[i]) {
                visited[i] = true;
               int next = Integer.parseInt(s + numbers.charAt(i));
                if (!ans.contains(next)) {
                    ans.add(next);
                }
                dfs(depth + 1, numbers, s + numbers.charAt(i));
                visited[i] = false;
            }
        }
    }

    private boolean isPrime(int num) {
        if (num < 2) {
            return false;
        }
         for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }

        return true;
    }
}

후보키(https://school.programmers.co.kr/learn/courses/30/lessons/42890)

문제 설명

프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.

그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.

후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.

• 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
  • 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
  • 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.
    제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.
    
    위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 "학번"을 가지고 있다. 따라서 "학번"은 릴레이션의 후보 키가 될 수 있다. 그다음 "이름"에 대해서는 같은 이름("apeach")을 사용하는 학생이 있기 때문에, "이름"은 후보 키가 될 수 없다. 그러나, 만약 ["이름", "전공"]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다. 물론 ["이름", "전공", "학년"]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다. 따라서, 위의 학생 인적사항의 후보키는 "학번", ["이름", "전공"] 두 개가 된다.
    릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

제한사항

• relation은 2차원 문자열 배열이다.
• relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
• relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
• relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
• relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

입출력 예

relation	result
[["100","ryan","music","2"], ["200","apeach","math","2"], ["300","tube","computer","3"], ["400","con","computer","4"], ["500","muzi","music","3"], ["600","apeach","music","2"]]	2
#### 입출력 예 설명
입출력 예 #1
문제에 주어진 릴레이션과 같으며, 후보 키는 2개이다.

풀이

문제 파악

• 후보키 ⇒ 유일성과 최소성을 만족하면서, 관계 데이터베이스에서 릴레이션의 튜플을 유일하게 식별할 수 있는 속성 또는 속성의 집합
  • 유일성 ⇒ 릴레이션에 있는 모든 튜플이 유일하게 식별되도록하는 특성
  • 최소성 ⇒ 후보키의 한 속성이라도 제외될 경우 유일성이 깨지는 특성
• 주어진 릴레이션에서 유일성과 최소성을 만족하는 후보키의 최대 개수를 찾아라
  

접근 방법

• 방문여부, 릴레이션의 행열의 길이, 키의 모든 조합을 저장할 list, list의 요소들에 대해 유일성과 최소성 검사를 하고 난 최종 후보키를 저장할 list2를 선언 및 초기화

1. 행의 길이 만큼 combine 메서드와 validate 메서드를 실행

2. combine(): dfs를 백트래킹하여 속성키가 될 수 있는 모든 index의 조합을 list에 저장

3. validate(): 개별 index 조합을 분리하여 조합 내 각 index를 저장하는 배열 생성. set을 생성하고 해당 배열을 이용하여 해당 조합에 모든 릴레이션의 값을 문자열로 만들어 set에 저장하고 모든 값을 저장했을 때 set의 길이와 실제 열의 길이(릴레이션 개수)와 비교

   → 길이가 다를 경우 중복된 데이터가 존재한다는 의미 → 해당 속성키 조합으로는 유일성 충족x

   • 유일성 조건을 통과할 경우, list2에 있는 후보키의 index 조합을 가져와 분리하고 유일성 조건을 통과한 data와 비교하고 각 요소가 포함되어 있을 때마다, cnt++.

     → cnt와 가져온 후보키의 index 조합을 분리한 배열의 길이가 같을 경우 최소성 검사 flag를 true

     → 위의 경우 data의 속성키 조합이 가져온 후보키의 속성 조합 +a라는 의미이므로 최소성 충족x

   • 최소성 조건도 통과했을 경우 해당 index 조합을 list2에 추가

4. 후보키 조합들을 모두 저장한 list2의 길이를 답으로 반환

   
   

코드 구현

import java.util.*;

class Solution {
    public static boolean[] visited;
    public static int colLength;
    public static int rowLength;
    public static Set<String> list = new HashSet<>();
    public static List<String> list2 = new ArrayList<>();

    public int solution(String[][] relation) {
        colLength = relation[0].length;
        rowLength = relation.length;
        visited = new boolean[colLength];

        for (int i = 1; i <= colLength; i++) {
            combine(0, i, relation);
            validate(relation);
            list.clear();
        }

        return list2.size();
    }

    public void combine(int start, int combNum, String[][] relation) {
        if (combNum == 0) {
            String temp = "";
            for (int i = 0; i < colLength; i++) {
                if (visited[i]) {
                    temp += i;
                }
            }
            list.add(temp);
        }

        for (int i = start; i < colLength; i++) {
            if (!visited[i]) {
                visited[i] = true;
                combine(start + 1, combNum - 1, relation);
                visited[i] = false;
            }
        }
    }

    public void validate(String[][] relation) {
        //유일성 판단하기
        for (String data : list) {
            String[] temp = data.split("");
            int[] arr = new int[temp.length];
            for (int i = 0; i < temp.length; i++) {
                int c = Integer.parseInt(temp[i]);
                arr[i] = c;
            }
            //유일성 판단하기위한 set
            Set<String> set = new HashSet<>();
            for (int i = 0; i < rowLength; i++) {
                String cdd = "";
                for (String data2 : temp) {
                    int c = Integer.parseInt(data2);
                    cdd += relation[i][c];
                }
                set.add(cdd);
            }
            //만약 유일하다면 최소성 검사
            if (set.size() == rowLength) {
                boolean flag = false;
                for (String data3 : list2) {
                    int cnt = 0;
                    String[] temp3 = data3.split("");
                    for (String data4 : temp3) {
                        if (data.contains(data4)) {
                            cnt++;
                        }
                    }
                    if (cnt == data3.length()) {
                        flag = true;
                    }
                }
                if (!flag) {
                    list2.add(data);
                }
            }
        }
    }
}

보물 지도(https://school.programmers.co.kr/learn/courses/15009/lessons/121690)

문제 설명

진수는 보물이 묻힌 장소와 함정이 표시된 보물 지도를 이용해 보물을 찾으려 합니다. 보물지도는 가로 길이가 n, 세로 길이가 m인 직사각형 모양입니다.

맨 왼쪽 아래 칸의 좌표를 (1, 1)으로, 맨 오른쪽 위 칸의 좌표를 (n, m)으로 나타냈을 때, 보물은 (n, m) 좌표에 묻혀있습니다. 또한, 일부 칸에는 함정이 있으며, 해당 칸으로는 지나갈 수 없습니다.

진수는 처음에 (1, 1) 좌표에서 출발해 보물이 있는 칸으로 이동하려 합니다. 이동할 때는 [상,하,좌,우]로 인접한 네 칸 중 한 칸으로 걸어서 이동합니다. 한 칸을 걸어서 이동하는 데 걸리는 시간은 1입니다.

진수는 보물이 위치한 칸으로 수월하게 이동하기 위해 신비로운 신발을 하나 준비했습니다. 이 신발을 신고 뛰면 한 번에 두 칸을 이동할 수 있으며, 함정이 있는 칸도 넘을 수 있습니다. 하지만, 이 신발은 한 번밖에 사용할 수 없습니다. 신비로운 신발을 사용하여 뛰어서 두 칸을 이동하는 시간도 1입니다.

이때 진수가 출발점에서 보물이 위치한 칸으로 이동하는데 필요한 최소 시간을 구해야 합니다.

예를 들어, 진수의 보물지도가 아래 그림과 같을 때, 진수가 걸어서 오른쪽으로 3칸, 걸어서 위쪽으로 3칸 이동하면 6의 시간에 보물이 위치한 칸으로 이동할 수 있습니다. 만약, 오른쪽으로 걸어서 1칸, 위쪽으로 걸어서 1칸, 신비로운 신발을 사용하여 위로 뛰어 2칸, 오른쪽으로 걸어서 2칸 이동한다면 총 5의 시간에 보물이 위치한 칸으로 이동할 수 있으며, 이보다 빠른 시간 내에 보물이 있는 위치에 도착할 수 없습니다.

진수의 보물지도가 표현하는 지역의 가로 길이를 나타내는 정수 n, 세로 길이를 나타내는 정수 m, 함정의 위치를 나타내는 2차원 정수 배열 hole이 주어졌을 때, 진수가 보물이 있는 칸으로 이동하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 단, 보물이 있는 칸으로 이동할 수 없다면, -1을 return 해야 합니다.

제한사항

• 1 ≤ n, m ≤ 1,000
  • 단, n * m이 3 이상인 경우만 입력으로 주어집니다.
• 1 ≤ hole의 길이 ≤ n * m - 2
  • hole[i]는 [a, b]의 형태이며, (a, b) 칸에 함정이 존재한다는 의미이며, 1 ≤ a ≤ n, 1 ≤ b ≤ m을 만족합니다.
  • 같은 함정에 대한 정보가 중복해서 들어있지 않습니다.
• (1, 1) 칸과 (n, m) 칸은 항상 함정이 없습니다.

입출력 예

입출력 예 설명

입출력 예 #1

• 본문의 예시와 같습니다.
  입출력 예 #2
• 보물지도를 그림으로 나타내면 아래와 같으며, 보물이 위치한 칸으로 이동할 수 없습니다. 따라서, -1을 return 해야 합니다.

풀이

문제 파악

• [n x m] 크기의 보물지도에서 (1, 1)에서부터 (n, m)까지 최단거리를 구하라
  • 최단거리를 구하는 문제이므로 bfs를 사용하여 풀이
• 한 방향으로 한 번에 2칸을 이동할 수 있는 신발을 탐색하는 동안 한 번 사용 가능하다.
  • 함정으로 인해 도착까지 신발을 사용할 수 없는 경우가 아니라면 신발이 무조건 사용될 것이다.
  • 신발 사용 여부에 따라 이동 범위가 달라지므로 신발 사용 여부를 저장하고 bfs 내에서 전달해야 한다.
• 함정이 있는 칸은 기본적으로 지나갈 수 없지만, 신비로운 신발을 사용하면 1칸의 함정은 뛰어넘을 수 있다.
• bfs 내에서 신발의 이동 범위를 포함한 경우의 수를 모두 실행하여 최단거리 도출
  

접근 방법

• bfs 내에서 다음 칸에 함정이 위치하는지 여부를 확인하기 위해서 함정의 위치 배열(int[][] hole)을 위치 별 함정 여부를 나타내는 배열(boolean[][] trap)로 변환
• visited는 3차원 배열로 선언하여 방문 여부와 신발 사용 여부를 모두 저장한다.(같은 칸에 방문하더라도 신발 사용 여부에 따라 다른 경우의 수가 됨)
• dr, dc 배열은 신발의 이동 범위까지 고려하여 다음 칸을 상하좌우로 1 ~ 2칸으로 설정할 수 있도록 초기화한다.
• bfs():
  • 시작점 정보를 queue에 add하며 bfs 실행 시작
  • 현재 위치 정보를 저장하고, 신발을 사용했는지 여부에 따라 다음 칸을 지정하는 for문 내 인덱스 범위를 4 또는 8로 설정
    • 해당 인덱스 범위에 따라 다음 칸에 저장될 신발 사용 여부(nj)도 달라짐
  • 다음 칸이 지도 내의 범위에 존재하고 방문 여부와 함정이 없다면 다음 칸에 대한 방문 여부를 true로 저장하고 queue에 다음 칸을 add
  • bfs 루프의 종료 조건은 현재 칸이 도착점(n, m)일 경우이며 해당 칸까지의 거리(dist)를 반환한다.
  • 도착점에 도착하지 못할 경우(= 종료 조건에 도달하지 못하고 queue가 빌 경우) -1을 반환한다.

코드 구현

import java.util.*;

class Solution {
    public int solution(int n, int m, int[][] hole) {
        boolean[][] trap = new boolean[n+1][m+1];
        for (int[] h : hole) {
            trap[h[0]][h[1]] = true;
        }

        boolean[][][] visited = new boolean[n+1][m+1][2];
        Queue<int[]> queue = new ArrayDeque<>();
        visited[1][1][0] = true;
        queue.add(new int[]{ 1, 1, 0, 0 });

        int[] dr = { 0, 1, 0, -1, 0, 2, 0, -2 };
        int[] dc = { 1, 0, -1, 0, 2, 0, -2, 0 };

        while (!queue.isEmpty()) {
            int[] cur = queue.remove();
            int r = cur[0], c = cur[1], jumped = cur[2], dist = cur[3];

            if (r == n && c == m) return dist;

            for (int d = 0; d < ((jumped == 1) ? 4 : 8); d++) {
                int nr = r + dr[d], nc = c + dc[d];
                int nj = (jumped == 1) ? 1 : (d / 4);

                if (nr >= 1 && nr <= n && nc >= 1 && nc <= m) {
                    if (!visited[nr][nc][nj] && !trap[nr][nc]) {
                        visited[nr][nc][nj] = true;
                        queue.add(new int[]{ nr, nc, nj, dist + 1 });
                    }
                }
            }
        }
        return -1;
    }
}

거리두기 확인하기(https://school.programmers.co.kr/learn/courses/30/lessons/81302)

문제 설명

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.
   예를 들어,
   
   5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한사항

• places의 행 길이(대기실 개수) = 5
  • places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P,O,X로 이루어진 문자열입니다.
  • places 원소의 길이(대기실 가로 길이) = 5
  • P는 응시자가 앉아있는 자리를 의미합니다.
  • O는 빈 테이블을 의미합니다.
  • X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
• return 값 형식
  • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
  • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
  • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

입출력 예

입출력 예 설명

입출력 예 #1 첫 번째 대기실

두 번째 대기실

세 번째 대기실

네 번째 대기실

다섯 번째 대기실

두 번째 대기실을 제외한 모든 대기실에서 거리두기가 지켜지고 있으므로, 배열 [1, 0, 1, 1, 1]을 return 합니다.

풀이

문제 파악

• 주어진 대기실 5개는 [5 x 5] 사이즈이며, 대기실 하나는 P, X, O로만 이루어진 문자열 5개가 저장된 배열로 주어진다.
  • 대기실의 행 길이 = places[i].length = 5(배열의 길이)
  • 대기실의 열 길이 = places[i][j].length() = 5(문자열의 길이)
• 각 대기실에 대해 응시자("P") 간 맨해튼 거리(|가로 거리| + |새로 거리|)가 2 이하가 되지 않도록 모두 지켜지고 있으면 1을, 아니라면 0을 답으로 반환한다.
• 응시자("P") 간 거리의 측정에는 빈 테이블(”O”)로 뚫려있는 범위만 계산하고 파티션(”X”)으로 막혀있으면 계산되지 않는다.
• 5개의 대기실에 대한 거리두기 준수 여부를 0, 1로 이루어진 배열로 도출한다.
  

접근 방법

• Solution(): 모든 대기실에 대해 각각 check 함수를 실행하고 0 또는 1의 값을 answer 배열에 저장하고 반환
• check(): for 문 내에서 대기실 내 응시자("P")를 찾고 응시자의 수 만큼 bfs를 실행하고 실행 결과로 false가 반환되면 0을, false가 반환되지 않고 반복문이 끝나면 1을 반환
• bfs(): 대기실 내 응시자("P")의 위치를 시작점으로 거리(dist)가 2 이내의 접근가능한 모든 칸을 확인하고 해당 거리 내에 다른 응시자("P")가 있다면 false, 없다면 true 반환
  • 다음 칸에 대한 접근가능 조건

      1. 대기실 범위 내에서 현재 칸의 상하좌우에 위치한 칸

    2. 파티션("X")로 막혀있지 않은 칸
    3. 탐색되지 않은(visited[nr][nc] == false) 칸
    4. 탐색 시작 위치에서 거리가 2이내인 칸
       

코드 구현

import java.util.*;

public class Solution {
    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        for (int i = 0; i < 5; i++) {
            answer[i] = check(places[i]);
        }
        return answer;
    }

    private int check(String[] place) {
        for (int i = 0; i < 5; i++) {
            if (place[i].contains("P")) {
                for (int j = 0; j < 5; j++) {
                    if (place[i].charAt(j) == 'P') {
                        if (!bfs(i, j, place)) return 0;
                    }
                }
            }
        }
        return 1;
    }

    private boolean bfs(int sr, int sc, String[] place) {
        int[] dr = {0, 0, 1, -1};
        int[] dc = {1, -1, 0, 0};

        Queue<int[]> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[5][5];
        queue.offer(new int[]{sr, sc, 0});
        visited[sr][sc] = true;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0];
            int c = cur[1];
            int dist = cur[2];

            if (dist > 0 && place[r].charAt(c) == 'P') return false;

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nc >= 0 && nr < 5 && nc < 5 && !visited[nr][nc]) {
                    if (dist + 1 <= 2 && place[nr].charAt(nc) != 'X') {
                        queue.offer(new int[]{nr, nc, dist + 1});
                        visited[nr][nc] = true;
                    }
                }
            }
        }
        return true;
    }
}

게임 맵 최단거리(https://school.programmers.co.kr/learn/courses/30/lessons/49189)

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

풀이

문제 파악

• 문제에서 주어진 정보는 노드의 개수(n)과 간선의 정보를 담은 배열(edge)
• 간선의 배열(edge)을 노드 간의 연결 정보를 담은 배열로 변환하여 인접 리스트로 문제를 풀이
• 1번 노드를 출발점이라고 가정할 때 출발점에서 각 노드까지의 최단거리를 구해야 하므로 bfs로 풀이
• 각 노드까지의 최단거리를 모두 구하고 이 중 가장 큰 값이 몇 개 존재하는지 count하고 반환

접근 방법

• 인접 리스트를 담을 graph와 방문여부를 담을 visited를 해시맵으로 초기화
• 노드의 개수(n)과 간선의 배열(edge)를 이용하여 graph에 각 노드 별 정보를 추가하여 인접 리스트로 변환 후 bfs 실행
• bfs:
  1. queue와 최대 거리를 저장할 변수 maxDist, 최대 거리인 노드의 개수를 저장할 변수 count를 초기화
  2. 시작 노드인 1과 현재 거리인 0을 queue에 예약하고 방문 표시 후 bfs 루프 시작
  3. 현재 노드까지의 거리(dist)가 최대 거리(maxDist)보다 크다면, maxDist를 dist로 갱신. maxDist와 dist가 같다면, count를 1 증가
  4. 인접 리스트에서 현재 노드와 인접한 노드에 방문한 적 있는지 확인 후 방문한 적이 없다면 방문 표시 후 queue에 해당 노드와 거리 + 1을 예약
     5. 모든 노드를 탐색 후 루프가 종료되면 count를 return

코드 구현

import java.util.*;

public class Solution {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    Map<Integer, Boolean> visited = new HashMap<>();

    public int solution(int n, int[][] edge) {
        for (int i = 1; i <= n; i++) {
            graph.put(i, new ArrayList<>());
            visited.put(i, false);
        }
        for (int[] e : edge) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }

        return bfs(1);
    }

    private int bfs(int node) {
       Queue<int[]> queue = new ArrayDeque<>();
       queue.offer(new int[]{node, 0});
       visited.put(node, true);

       int maxDist = 0;
       int count = 0;

       while (!queue.isEmpty()) {
           int cur[] = queue.poll();
           int curVertex = cur[0];
           int dist = cur[1];

           if(maxDist < dist) {
               maxDist = dist;
               count = 1;
           } else if(maxDist == dist) count ++;

           for(int nextVertex: graph.get(curVertex)) {
               if(!visited.get(nextVertex)) {
                   visited.put(nextVertex, true);
                   queue.offer(new int[]{nextVertex, dist + 1});
               }
           }
       }

       return count;
    }
}

게임 맵 최단거리(https://school.programmers.co.kr/learn/courses/30/lessons/1844)

문제 설명

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

• 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.

• 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.
  위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.
  만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.
  
  게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

입출력 예

입출력 예 설명

입출력 예 #1 주어진 데이터는 다음과 같습니다.

캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.

따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.

입출력 예 #2 문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.

풀이

문제 파악

• 주어진 진영 maps는 [n x m]의 2차원 배열이고, 1 <= n, m <= 100의 범위 내 자연 수
• (1, 1)에서 출발하고 (n, m)에 도착할 때까지 최단거리를 구하는 문제
  • 최단거리 문제이므로 bfs를 사용해서 접근. 거리만 계산하면 되므로 2차원 배열에서 계산의 편의성을 위해 (0, 0)에서 (n-1, m-1)까지의 최단거리를 구하자.

접근 방법

• 현재 위치에서 인접한 상하좌우 칸으로 접근하기 위한 방향 계산용 배열 dr/dc, maps의 행열 길이를 저장할 rowLength/colLength, 해당 칸의 방문여부를 저장할 2차원 배열 visited를 초기화
• 시작점 정보(행 좌표: 0, 열 좌표: 0, 거리: 1)를 queue에 예약하고 방문 표시 후 bfs 시작
• 루프 내에서 현재 위치의 상하좌우 칸이 유효한지 검사하고 방문한 적이 없는 칸이라면 해당 칸을 다음 칸으로 하는 bfs 실행을 위해 queue에 예약하고 방문 표시
• bfs 루프의 종료 조건은 queue가 빌 경우 또는 도착점에 도착했을 경우
  • queue가 비어있을 경우 접근할 수 있는 다음 칸이 없다는 의미이므로 루프에서 벗어나 -1을 return
  • 현재 위치가 도착점이라면 현재 위치까지의 거리를 계산한 dist를 return -> bfs로 실행했으므로 제일 먼저 도착한 시점의 dist가 최단거리가 됨

코드 구현

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, 1, -1};
        int rowLength = maps.length;
        int colLength = maps[0].length;
        boolean[][] visited = new boolean[rowLength][colLength];

        Queue<int[]> queue = new ArrayDeque();
        queue.offer(new int[]{0,0,1});
        visited[0][0] = true;

        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0];
            int c = cur[1];
            int dist = cur[2];

            if(r == rowLength - 1 && c == colLength - 1) {
                return dist;
            }

            for(int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                if(0 <= nr && nr < rowLength && 0 <= nc && nc < colLength && maps[nr][nc] == 1) {
                    if(!visited[nr][nc]) {
                        queue.offer(new int[]{nr, nc, dist + 1});
                        visited[nr][nc] = true;
                    }
                }
            }
        }
        return -1;
    }
}

괄호 회전하기(https://school.programmers.co.kr/learn/courses/30/lessons/76502)

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
  대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.

입출력 예

입출력 예 설명

입출력 예 #1

• 다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.

  x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열?
  0	"[](){}"	O
  1	"](){}["	X
  2	"(){}[]"	O
  3	"){}[]("	X
  4	"{}[]()"	O
  5	"}[](){"	X

• 올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.
  입출력 예 #2
• 다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다

  x	s를 왼쪽으로 x칸만큼 회전	올바른 괄호 문자열?
  0	"[](){}"	O
  1	"](){}["	X
  2	"(){}[]"	O
  3	"){}[]("	X
  4	"{}[]()"	O
  5	"}[](){"	X

• 올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.
  입출력 예 #3
• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.
  입출력 예 #4
• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

풀이

문제 파악

• stack을 이용하여 모든 괄호에 대해 쌍을 맞춰 pop시키고, stack을 모두 비울 수 있는지 여부에 따라 올바른 괄호 문자열인지 확인
• 주어진 괄호 문자열(s)의 길이는 1 <= s <= $10^3$ 이고 문자열의 회전은 s.length번 하게되므로 올바른 괄호 문자열인지 s.length번 검사하게 됨

접근 방법

• solution 함수: 괄호 문자열 s를 왼쪽으로 한 칸씩 회전시킬 때마다 isValid 함수를 통해 유효한 괄호 문자열인지 검사하고 유효한 괄호 문자열일 경우, answer에 +1을 해줌. s.length번 반복하고 answer를 return
• isValid 함수:
  1. s를 한 글자씩 순회하며 해당 글자가 열린 괄호([ "(", "{", "[" ])라면 stack에 push.
  2. 닫힌 괄호([ ")", "}", "]" ])라면, stack이 비었는지 먼저 확인
     • stack이 비어있는데 닫힌 괄호가 나왔다는 것은 유효한 괄호 문자열이 아니라는 것을 의미
  3. stack의 top에 저장된 요소가 같은 쌍의 열린 괄호인지 확인하고, 맞다면 pop
  4. 모든 문자열에 대한 검사가 끝난 후 stack이 비어있는지 여부를 반환
     • stack이 비어있다면, 모든 괄호가 쌍을 이루었다는 의미이므로 유효한 괄호 문자열이라고 판단하여 true 반환. 반대의 경우 false 반환.

코드 구현

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;

        for (int i = 0; i < s.length(); i++) {
            if (isValid(s)) answer += 1;
            s = s.substring(1) + s.charAt(0);
        }

        return answer;
    }

    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) return false;
                if ((stack.peek() == '(' && ch == ')') ||
                    (stack.peek() == '[' && ch == ']') ||
                    (stack.peek() == '{' && ch == '}')) {
                    stack.pop();
                }
            }
        }
        return stack.isEmpty();
    }
}

주식가격(https://school.programmers.co.kr/learn/courses/30/lessons/42584)

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

풀이

문제 파악

• 주어진 배열 prices에 대해: 1 <= prices[i] <= $10^4$, 2 <= prices.length <= $10^5$
• 이중 for문으로 접근할 경우: 각 초별 시점(index)에서의 가격을 서로 비교하고 비교 횟수만큼 count한 값을 배열로 저장하고 반환한다.
• stack으로 접근할 경우: 각 초별 시점(index)에서의 가격을 앞 순번부터 stack에 저장하고 다음 시점의 가격과 크기 비교 후 시점 차이(stack 내의 index 차이)에 대한 값을 배열에 저장하고 반환한다.

접근 방법

이중 for 문

• 이중 for문 내에서 각 초별 시점을 index(i, j)로 가정하고 해당 시점의 가격을 for문을 돌며 서로 비교
• 가격하락이 없는 기간을 초로 표현하기 위해 answer[i]에 값을 증가
• j시점의 가격이 i시점의 가격보다 낮아질 경우 break를 통해 가격이 떨어지지 않은 기간을 현재 값으로 확정

stack 활용

• for문 내에서 각 초별 시점을 index(i)로 가정하고 0을 push하고 반복문 시작
• 반복문의 이전 단계에서 push된 stack의 맨 위 index(j)의 가격과 i번째 index의 가격을 비교하고 stack 맨 위 저장된 index의 가격이 더 클 경우 i와 j의 차이를 answer 배열에 저장하고 stack.pop(). 아니라면 while 문을 빠져나와 for문의 다음 단계로 이동
• for문 종료 후에도 stack이 비어있지 않으면 stack에 저장된 남은 index 값들에 대해 계산 후 answer 배열에 저장

코드 구현

이중 for문

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];

        for (int i = 0; i < prices.length; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                answer[i]++;
                if (prices[i] > prices[j]) {
                    break;
                }
            }
        }
        return answer;
    }
}

stack 활용

import java.util.*;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < prices.length; i++) {
            while (!stack.isEmpty()) {
                int j = stack.peek();
                if (prices[j] > prices[i]) {
                    answer[j] = i - j;
                    stack.pop();
                } 
                else break;
            }

            stack.push(i);
        }

        while (!stack.isEmpty()) {
            int i = stack.pop();
            answer[i] = prices.length - i - 1;
        }

        return answer;
    }
}

타겟 넘버(https://school.programmers.co.kr/learn/courses/30/lessons/43165)

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

입출력 예

입출력 예 설명

• 입출력 예 #1
  문제 예시와 같습니다.

• 입출력 예 #2

• 4+1-2+1 = 4
• 4-1+2-1 = 4 총 2가지 방법이 있으므로, 2를 return 합니다.

풀이

문제 파악

• numbers 배열 내의 숫자와 덧셈/뺄셈연산자를 사용해서 연산 수행
• 2 <= numbers.length <= 20, 1 <= numbers[i] <= 50, 1 <= target <= 1000
• 모든 연산 결과를 경우의 수로 나타내면 경우의 수는 $2^n$(n은 numbers.length)
• dfs를 사용해서 모든 경우의 수를 완전 탐색
  • dfs를 사용해서 완전탐색을 할 경우 최대 경우의 수는 $2^{20}$
  • 모든 연산 결과에 대해 target과 일치하는지 확인하고 일치하는 수를 계산

접근 방법

• 숫자 배열, 타겟 넘버, 깊이, 연산 결과를 매개변수로 받는 dfs 실행
  • dfs 내에서 덧셈과 뺄셈 연산에 대해 각각 dfs를 재귀적으로 호출
  • 재귀 호출의 종료 조건은 dfs의 탐색 깊이가 숫자 배열의 길이와 같을 경우(depth == numbers.length)
    • 이 때, 연산 결과와 타겟 넘버가 같은지 확인하고 같다면 1을, 다르다면 0을 return
  • return 된 값은 dfs를 탈출하며 계속해서 count에 전달되어 더해짐
  • 최초 호출된 dfs가 종료되면 모든 경우의 수에 대한 count를 답으로 return

코드 구현

class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }

    private int dfs(int[] numbers, int target, int depth, int sum) {
        if(depth == numbers.length) {
            return (target == sum) ? 1 : 0;
        }

        int count = 0;
        count += dfs(numbers, target, depth + 1, sum + numbers[depth]);
        count += dfs(numbers, target, depth + 1, sum - numbers[depth]);

        return count;
    }
}

참고

경우의 수	count 반환

마크다운(Markdown)은 일반 텍스트 기반의 경량 마크업 언어다. 일반 텍스트로 서식이 있는 문서를 작성하는 데 사용되며, 일반 마크업 언어에 비해 문법이 쉽고 간단한 것이 특징이다. HTML과 리치 텍스트(RTF) 등 서식 문서로 쉽게 변환되기 때문에 응용 소프트웨어와 함께 배포되는 README 파일이나 온라인 게시물 등에 많이 사용된다. - 위키백과

마크다운의 장단점

&nbsp&nbsp장점

1. 쉽고 직관적이다.
2. 가독성이 좋다.
3. 다양한 플랫폼에서 지원된다.
4. 버전 관리 시스템과 호환성이 좋다. (git/gitHub)

&nbsp&nbsp단점

1. 다른 마크업 언어에 비해 제한된 기능으로 복잡한 레이아웃이나 스타일의 표현이 어렵다.
    -> 이로 인해 HTML을 완전히 대체하기는 어렵다.
2. 표준이 없기 때문에 각 플랫폼 또는 소프트웨어마다 약간의 차이가 있을 수 있다.

2. 마크다운 문법

제목

h1 ~ h6까지 표현할 수 있다. #의 개수를 다르게 하여 작성 가능하다.

#        h1
##        h2     
###        h3
####    h4
#####    h5
######    h6

강조

글자 강조 표현은 굵게(Bold), 이텔릭(Italic), 취소선이 있다.

입력

**굵게**
_이텔릭_
~~취소선~~

출력

굵게 이텔릭 취소선

체크박스

체크박스는 [ ]의 형태로 표현가능하다. 체크표시를 넣으려면 [x]로 표기해야되며 대괄호 앞뒤로 한 칸씩 여백을 입력해야 한다.

수평선

문단 간 구분선으로 사용되는 수평선은 <hr/> 태그를 직접 입력하여 표현할 수 있으며, ***, ---, ___의 기호로도 표현가능하다.

입력

문단1

<hr/>
문단2

***
문단3

---
문단4

___

출력

문단1

문단3

문단4

블럭인용

>을 인용된 내용을 다루는 문단 앞에 입력한다. 여러 개 중첩이 가능하다.

입력

> 인용 문단
>> 1개 중첩
>>> 2개 중첩

출력

인용 문단

1개 중첩

2개 중첩

코드블럭

코드블럭은 tab 또는 ```으로 작성할 수 있다. 코드가 한 줄이라면 tab 뒤에(앞 줄 개행이 필요함), 코드가 여러 줄이라면 ``` 사이에 작성한다. 코드가 여러 줄일 경우, 사용하는 언어를 기입하여 해당 언어의 syntax highlighting을 반영할 수 있다. 인라인에도 코드 삽입이 가능하다. 코드를 인라인으로 표기하면,

출력문은 print('Hello World!') 형태이다.

처럼 표기된다.

한 줄 예시

입력

(tab) print('Hello World!') ;

출력

print('Hello World!') ;

여러 줄 예시

입력

``` javascript
let sayHi = function () {
    console.log('Hello World!');
    }
sayHi(); ```

출력

let sayHi = function () {
    console.log('Hello World!');
    }
sayHi();

목록

순서 있는 목록

순서 있는 목록은 글머리에 숫자 + . 으로 작성한다. 순서 있는 목록의 경우 작성한 순서에 상관없이 숫자의 내림차순으로 정렬된다. 소항목의 경우 숫자 + ) 으로 작성한다.

입력

1. 첫번째 목록
1) 첫번째 소항목
2) 두번째 소항목
2. 두번째 목록
3. 세번째 목록

출력

1. 첫번째 목록 1) 첫번째 소항목 2) 두번째 소항목
2. 두번째 목록
3. 세번째 목록

순서 없는 목록

순서 없는 목록은 글머리에 - / * / +으로 작성한다.

입력

* 치킨
    + 피자
        - 햄버거

출력

• 치킨
  • 피자
    • 햄버거

표(테이블)

<table>태그와 같은 표를 작성하기 위해서는 |과 줄바꿈을 통해 행과 열을 구분한다. ---을 통해 헤더를 구분하고 해당 줄에 :을 좌측에 삽입하면 좌측 정렬, :을 우측에 삽입하면 우측 정렬, 양쪽 모두 삽입하면 중앙 정렬이 된다. 셀 내부의 내용에 글자 강조 표시도 적용 가능하다.

|구문        |설명   |비고 |
|:---       |:---:  |---:|
|**Header** |_Title_|1   |
|`Paragraph`|Text   |2   |

이미지 삽입

이미지 삽입은 ![이미지 설명](이미지 소스 URL "이미지 설명")의 형식으로 입력한다.

입력

![이미지 미리보기](https://velog.velcdn.com/images/gener-lst/post/image.png "이미지 미리보기")

출력

링크 삽입

링크 삽입은 바로 링크를 삽입하는 방식과 텍스트에 링크를 거는 방식으로 나뉜다. 이 때, 링크 주소 뒤에 "" 내부에 추가 설명을 작성할 수 있다.

입력

https://velog.io/@gener-lst
[내 velog 바로가기](https://velog.io/@gener-lst "개발자 지망생")

출력

https://velog.io/@gener-lst 내 velog 바로가기