더 이상 물러설 곳이 없다

programmers.co.kr/learn/courses/30/lessons/68644

문제 설명

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers의 길이는 2 이상 100 이하입니다.
  • numbers의 모든 수는 0 이상 100 이하입니다.

입출력 예

numbersresult

입출력 예 설명

입출력 예 #1

• 2 = 1 + 1 입니다. (1이 numbers에 두 개 있습니다.)
• 3 = 2 + 1 입니다.
• 4 = 1 + 3 입니다.
• 5 = 1 + 4 = 2 + 3 입니다.
• 6 = 2 + 4 입니다.
• 7 = 3 + 4 입니다.
• 따라서 [2,3,4,5,6,7] 을 return 해야 합니다.

입출력 예 #2

• 2 = 0 + 2 입니다.
• 5 = 5 + 0 입니다.
• 7 = 0 + 7 = 5 + 2 입니다.
• 9 = 2 + 7 입니다.
• 12 = 5 + 7 입니다.
• 따라서 [2,5,7,9,12] 를 return 해야 합니다.

풀이 .

import java.util.ArrayList;
import java.util.Collections;

class Solution {
    ArrayList<Integer> answer = new ArrayList<>();

    public void dfs(int idx, int cnt, int sum, int[] numbers) {
        if(cnt == 2) {
            if(!answer.contains(sum)) {
                answer.add(sum);
            }
            return;
        }
        if(idx != numbers.length) {
            dfs(idx + 1, cnt + 1, sum + numbers[idx], numbers);
            dfs(idx + 1, cnt, sum, numbers);
        }
    }

    public ArrayList<Integer> solution(int[] numbers) {
        dfs(0, 0, 0, numbers);
        Collections.sort(answer);
        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] numbers = {2, 1, 3, 4, 1};
        ArrayList<Integer> ans = sol.solution(numbers);
        System.out.println(ans);
    }
}

DFS를 사용해 배열의 원소 2개에 대한 조합을 모두 구한다.

중복 값을 허용하지 않는 조건을 추가하여 정답 형식에 맞춰준다.

Set을 사용하려고 했는데 오름차순된 배열을 반환해야해서 ArrayList에서 contains로 검사했다.

programmers.co.kr/learn/courses/30/lessons/64061

문제 설명

게임개발자인 죠르디는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.
죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.

게임 화면은 1 x 1 크기의 칸들로 이루어진 N x N 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 5 x 5 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 1 x 1 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습입니다.

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• board 배열은 2차원 배열로 크기는 5 x 5 이상 30 x 30 이하입니다.
• board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
  • 0은 빈 칸을 나타냅니다.
  • 1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
• moves 배열의 크기는 1 이상 1,000 이하입니다.
• moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

입출력 예

boardmovesresult

입출력 예에 대한 설명

입출력 예 #1

인형의 처음 상태는 문제에 주어진 예시와 같습니다. 크레인이 [1, 5, 3, 5, 1, 2, 1, 4] 번 위치에서 차례대로 인형을 집어서 바구니에 옮겨 담은 후, 상태는 아래 그림과 같으며 바구니에 담는 과정에서 터트려져 사라진 인형은 4개 입니다.

풀이 .

import java.util.Arrays;
import java.util.Stack;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        int n = board.length;
        int[] topOfCol = new int[n];
        Arrays.fill(topOfCol, n);

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                // 각 열마다 인형이 처음 나오는 row 찾는다.
                // 끝까지 topOfCol[idx] == n 이면 비어있는 열
                if(board[i][j] != 0 && topOfCol[j] == n) {
                    topOfCol[j] = i;
                }
            }
        }

        Stack<Integer> stk = new Stack<>();
        for(int i = 0; i < moves.length; i++) {
            int col = moves[i] - 1;  // 열 인덱스 맞춰줘야 함
            if(topOfCol[col] == n) continue;  // 해당 열에 인형이 없는 경우
            int row = topOfCol[col];

            int doll = board[row][col];
            topOfCol[col] += 1;
            if(stk.isEmpty()) {
                stk.push(doll);
            }else {
                if(stk.peek() == doll) {
                    stk.pop();
                    answer += 2;
                }else {
                    stk.push(doll);
                }
            }
        }
        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        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 ans = sol.solution(board, moves);
        System.out.println(ans);
    }
}

각 열마다 가장 위에 있는 인형의 위치(row)를 표시하기 위해 int[] topOfCol를 사용했다.

스택을 사용해 해결.

programmers.co.kr/learn/courses/30/lessons/49189

노드의 개수 int n, 각 노드의 연결 상태 int[][] edge 가 주어진다. (edge의 각 행 [a, b] 는 노드 a, b 사이가 연결되어있음을 뜻한다.)

시작 노드를 1번으로 하였을 때, 1번 노드에서 가장 멀리 떨어진 노드의 개수를 반환해야한다.

풀이 .

import java.util.*;

class Solution {

    ArrayList<Integer>[] list = null;
    boolean[] check = null;
    int[] dist = null;

    public void bfs(int start) {
        Queue<Integer> que = new LinkedList<>();
        que.add(start);
        check[start] = true;
        dist[start] = 1;

        while (!que.isEmpty()) {
            int now = que.poll();
            for (int i = 0; i < list[now].size(); i++) {
                int next = list[now].get(i);
                if (check[next] == false) {
                    que.add(next);
                    check[next] = true;
                    dist[next] = dist[now] + 1;
                }
            }
        }
    }

    public int solution(int n, int[][] edge) {
        int answer = 0;

        // 0번 인덱스는 무시하고 1번부터 사용
        list = new ArrayList[n + 1];
        check = new boolean[n + 1];
        dist = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        for (int[] connect : edge) {
            int u = connect[0];
            int v = connect[1];
            list[u].add(v);
            list[v].add(u);
        }

        bfs(1);

        int max = 0;
        for(int d : dist) if(max < d) max = d;
        for(int d : dist) if(max == d) answer++;

        return answer;
    }
}

최단 거리, 최장 거리 문제는 웬만해선 BFS로 해결된다.

BFS 는 현재 노드에서 1만큼 떨어진 노드들을 우선적으로 탐색하기 때문에 시작 노드에서부터의 거리를 공평하게 잴 수 있다.

programmers.co.kr/learn/courses/30/lessons/43238

입국심사를 받아야 하는 사람 수 int n, 심사관 별 심사 소요시간 int[] times 가 주어진다.

모든 사람이 입국심사를 마치기까지 걸리는 최소시간을 반환해야한다.

1. 한 심사대에서는 동시에 한 명만 심사를 할 수 있다.

2. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

풀이 .

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);

        long answer = (long)times[times.length - 1] * n;  // 최악의 경우 : n명 모두 최대시간으로 검사
        long max = (long)times[times.length - 1] * n;  // 최악의 경우 : n명 모두 최대시간으로 검사
        long min = 1;  // 최고의 경우 : 1초만에 모든 검사 끝

        while(min <= max) {  // 시간 범위를 점점 좁히다가 엇길리게 되면 답을 찾은 것임
            long mid = (min + max) / 2;

            long sum = 0;
            for(int time : times) {  // 각 심사관별로 mid 시간동안 몇 명을 검사할 수 있는지의 총합
                sum += mid / time;
            }

            if(sum >= n) {
                answer = Math.min(answer, mid);
                max = mid - 1;  // n명 이상 해결이 가능하다 -> 시간을 줄인다
            }else {
                min = mid + 1;  // n명까지 해결하지 못한다 -> 시간을 늘린다
            }
        }

        return answer;
    }
}

비슷한 풀이법을 떠올리지조차 못했다. 구글링을 통해 다른이의 코드를 이해만 하고 넘어간 수준이다.

문제를 처음 봤을 때 했던 생각은..

그냥 단순하게 시간을 나타내는 변수를 두고 반복을 돌리면서,

각 심사관들이 다음 심사를 하려면 시간이 얼마나 지나야 하는가를 계산해서,

사람들을 어느 심사관에게 배치할 것인지를 고르려고 했다.

막상 곧이곧대로 구현해보려니 쉽지도 않았고 완성했어도 시간초과가 났을 거다.

(이분탐색이라고 분류가 돼있는데도 이런 방법 밖에 생각하지 못했다.)

n과 times[]의 최대 원소의 최대값이 10억인 걸 보고 이분탐색, DP 등 시간을 아낄 수 있는 방식을 떠올릴 수 있어야 한다.

(완전탐색은 택도 없이 시간초과)

1. 엄청나게 큰 n을 보고 이분탐색을 떠올린다

2. 심사에 걸리는 시간을 반환하는 것 -> 시간을 조정해가며 심사관들이 해당 시간 내에 몇명이나 심사할 수 있는지 확인

3. 이분 탐색을 통해 시간을 절반씩 줄여나간다.

아마 for each 부분을 생각 해내는 게 핵심이지 않았을까 싶다. (주어진 시간 내에 모든 심사관이 계속해서 심사를 이어간다면 몇 명의 심사를 마칠 수 있는지)

너무 어렵다.

객관적으로 그렇게까지 어려운 문제는 아닌 거 같은데 그냥 나한테는 어려운 거 같아서 더 짜증난다.

programmers.co.kr/learn/courses/30/lessons/43164

항공권의 배열 String[][] tickets 가 주어진다. (항공권은 [출발지, 도착지] 로 되어있다)

주어진 항공권을 모두 사용하는 여행경로를 담은 배열을 반환해야한다.

1. 맨 처음 시작은 ICN 에서만 한다.

2. 항공권을 모두 사용하는 경로가 여러 개일 경우 알파벳 순서가 빠른 것을 정답으로 한다.

3. 정답이 없는 경우는 없다.

풀이 .

import java.util.*;

class Solution {
    boolean[] check = null;
    String[] answer = null;
    ArrayList<String> temp = null;

    public void dfs(int dept, String now, String[][] tickets) {
        // dept == 방문한 장소 개수 == 다음 장소 입력할 인덱스
        if(dept == tickets.length + 1) {
            if(answer[0] == null) {
                answer = temp.toArray(new String[tickets.length + 1]);
                return;
            }

            for(int i = 0; i < tickets.length + 1; i++) {
                if(answer[i].compareTo(temp.get(i)) == 0) {
                    continue;
                }else if(answer[i].compareTo(temp.get(i)) < 0) {
                    return;
                }else if(answer[i].compareTo(temp.get(i)) > 0) {  // 새로운 정답이 더 빠르면 교체
                    answer = temp.toArray(new String[tickets.length + 1]);
                    return;
                }
            }
        }

        for(int i = 0; i < tickets.length; i++) {
            if(check[i] == false && now.equals(tickets[i][0])) {
                check[i] = true;
                temp.set(dept, tickets[i][1]);
                dfs(dept + 1, tickets[i][1], tickets);
                check[i] = false;
            }
        }
    }

    public String[] solution(String[][] tickets) {
        answer = new String[tickets.length + 1];
        check = new boolean[tickets.length];
        temp = new ArrayList<>();

        // add 없이 set 하면 에러남
        for(int i = 0; i < tickets.length + 1; i++) {
            temp.add("");
        }

        // ICN 에서만 출발 가능
        for(int i = 0; i < tickets.length; i++) {
            if(tickets[i][0].equals("ICN")) {
                check[i] = true;
                temp.set(0, tickets[i][0]);
                temp.set(1, tickets[i][1]);
                dfs(2, tickets[i][1], tickets);
                check[i] = false;
            }
        }

        return answer;
    }
}

'단어 변환' 문제와 거의 유사한 문제.

똑같이 DFS, 백트래킹을 사용해서 풀었다.

백트래킹 할 때 ArrayList에 집어넣었던 경로를 빼는 게 불편해서 스택으로 바꿀까 싶었지만 ArrayList.set() 으로 해결했다.

set() 을 사용하면 집어넣을 인덱스를 지정할 수 있기 때문에 굳이 remove() 를 하지 않아도 된다.

programmers.co.kr/learn/courses/30/lessons/43163

시작문자와 목표문자 String begin, target 과 사용할 수 있는 단어들의 배열 String[] words 가 주어진다.

begin을 시작으로 하여 words의 원소들로 적절히 단어를 바꿔가며 target에 도달할 수 있는 최소 변경 수를 반환해야한다.

단, 단어 변경은 알파벳이 하나 차이나는 단어로만 변경이 가능하며, target에 도달이 불가한 경우는 0을 반환한다.

풀이 .

import java.util.*;

class Solution {
    int answer = 51;
    boolean[] check = null;

    public boolean isPossible(String from, String to) {
        int cnt = 0, len = from.length();
        for(int i = 0; i < len; i++) {
            if(from.charAt(i) == to.charAt(i)) {
                cnt++;
            }
        }
        return cnt == len - 1 ? true : false;
    }


    public void dfs(int dept, String now, String target, String[] words) {
        if(now.equals(target)) {
            answer = Math.min(answer, dept);
            return;
        }

        for(int i = 0; i < words.length; i++) {
            String next = words[i];
            if(check[i] == false && isPossible(now, next)) {
                check[i] = true;
                dfs(dept + 1, next, target, words);
                check[i] = false;
            }
        }
    }

    public int solution(String begin, String target, String[] words) {
        check = new boolean[words.length];

        for(int i = 0; i < words.length; i++) {
            String next = words[i];
            if(check[i] == false && isPossible(begin, words[i])) {
                check[i] = true;
                dfs(1, next, target, words);
                check[i] = false;
            }
        }

        return answer == 51 ? 0 : answer;
    }
}

DFS로 풀었다.

words.length의 최대값이 50이므로 answer의 초기값을 51로 잡았다.

programmers.co.kr/learn/courses/30/lessons/43162

노드의 개수 int n, 노드 간 연결상태를 인접행렬로 나타낸 int[][] computers 가 주어진다.

component의 개수를 반환해야한다.

풀이 1.

import java.util.*;

class Solution {
    boolean[] check = null;

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

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

    public void bfs(int start, int[][] computers) {
        Queue<Integer> que = new LinkedList<>();
        que.add(start);

        while(!que.isEmpty()) {
            int node = que.poll();
            for(int i = 0; i < computers[node].length; i++) {
                if(computers[node][i] == 1 && check[i] == false) {
                    que.add(i);
                    check[i] = true;
                }
            }
        }
    }


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

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

        return answer;
    }
}

주어진 인접행렬을 그대로 사용했다.

풀이 2.

import java.util.*;

class Solution {
    ArrayList<Integer>[] list = null;
    boolean[] check = null;

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

        for (int i = 0; i < list[node].size(); i++) {
            int next = list[node].get(i);
            if (check[next] == false) {
                dfs(next);
            }
        }
    }

    public void bfs(int start) {
        Queue<Integer> que = new LinkedList<Integer>();
        que.add(start);
        check[start] = true;

        while (!que.isEmpty()) {
            int node = que.poll();
            for (int i = 0; i < list[node].size(); i++) {
                int next = list[node].get(i);
                if (check[next] == false) {
                    que.add(next);
                    check[next] = true;
                }
            }
        }
    }

    public int solution(int n, int[][] computers) {
        int answer = 0;
        list = new ArrayList[n + 1];
        check = new boolean[n + 1];

        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<Integer>();
        }

        for (int i = 0; i < computers.length; i++) {
            for (int j = 0; j < computers[i].length; j++) {
                if (computers[i][j] == 1) {
                    list[i + 1].add(j + 1);
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            if (check[i] == false) {
                dfs(i);
// 				bfs(i);
                answer++;
            }
        }

        return answer;
    }
}

인접리스트로 고쳐서 풀 수도 있다.

전형적인 DFS, BFS 문제라 딱히 쓸 말이 없다.

programmers.co.kr/learn/courses/30/lessons/43165

사용할 수 있는 숫자들의 배열 int[] numbers, int target 가 주어진다.

numbers 의 원소들을 사용해 덧셈, 뺄셈 연산을 적절히 수행했을 때 target을 만들어낼 수 있는 모든 경우의 수의 개수를 반환해야한다.

numbers의 원소는 모두 음이 아닌 정수이다.

풀이 1. (틀린 코드)

class Solution {
    // numbers의 원소들의 순서를 유지하지 않는 경우(모든 순열 구하는 방식)
    // 이 문제에선 틀린 코드임 (시간초과)
    
    int answer = 0;
    boolean[] check = null;
    
    public void DFS(int dept, int[] numbers, int target, int calc) {
        if(dept == numbers.length) {
            if(calc == target) {
                answer++;
            }
            return;
        }
        
        // 모든 순열을 구하기 위해 백트래킹 사용
        for(int i = 0; i < numbers.length; i++) {
            if(check[i] == false) {
                check[i] = true;
                DFS(dept + 1, numbers, target, calc + numbers[i]);
                DFS(dept + 1, numbers, target, calc - numbers[i]);
                check[i] = false;
            }
        }
    }
    
    public int solution(int[] numbers, int target) {
        check = new boolean[numbers.length];
        DFS(0, numbers, target, 0);
        return answer;
    }
}

문제의 조건이 제대로 명시되지 않아 틀린 코드를 작성했다.

numbers의 원소들이 사용되는 순서에 대한 아무런 언급이 없었기에 당연하게 원소들의 순서가 유지되지 않는, 즉, 모든 순열을 고려하는 방식으로 코드를 작성했다. 

그리고 시간초과를 맞이했다. numbers의 최대 길이는 20이다. + 연산만 하는 경우라고 해도 최대 20! 개의 식을 구하게 된다. 당연히 시간초과...

(물론 + 연산만 하면 모든 식의 결과가 같을 테니 무의미하긴 하지만 식의 개수에 대해 얘기하는 것이니..)

처음부터 이 계산을 해보고 뭔가 이상하단 걸 눈치 챘어야 했는데 무식하게 그냥 무작정 코딩했다. 

풀이 2. (정답 코드)

class Solution {
    int answer = 0;

    public void dfs(int dept, int calc, int[] numbers, int target) {
        if (dept == numbers.length) {  // 모든 원소를 반드시 전부 사용해야한다
            if (calc == target) {
                this.answer++;
            }
            return;
        }

        // 배열 내의 순서를 그대로 유지하며 +, - 연산을 이어나간다
        dfs(dept + 1, calc + numbers[dept], numbers, target);
        dfs(dept + 1, calc - numbers[dept], numbers, target);
    }

    public int solution(int[] numbers, int target) {
        dfs(0, 0, numbers, target);
        return this.answer;
    }
}

정답 코드이다.

아마 덧셈, 뺄셈은 항의 순서가 식의 결과에 영향을 미치지 않기 때문에 굳이 모든 순열을 구하지 않아도 되는 식으로 문제를 만든 것 같은데.. 그에 대한 설명이 너무 부실했다.

또, 배열의 모든 원소들을 반드시 다 사용하여야 한다는 규칙도 명시되지 않았다.

(이건 테스트 케이스에 간접적으로 드러나긴 했지만 그래도 따로 명시했어야 한다고 생각)

프로그래머스 문제는 이런 경우가 빈번히 발생하는 듯하다.