더 이상 물러설 곳이 없다

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;
    }
}

정답 코드이다.

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

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

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

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

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

삼각형 모양으로 쌓여있는 수를 나타낸 이차원 배열 int[][] triangle이 주어진다.

맨 위 꼭지점을 시작 위치로 하여 삼각형 밑면에 도착할 수 있는 여러가지 경로가 존재한다.

각 경로별로 길을 지나며 마주치는 숫자들을 더해나갔을 때 만들 수 있는 가장 큰 수를 반환해야한다.

단, 현재 위치에서 왼쪽 아래, 오른쪽 아래 둘 중 하나의 길로만 내려갈 수 있다. 올라가거나 옆으로 가는 경로는 존재하지 않는다.

풀이 .

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;

        // 초기화
        int[][] dp = new int[triangle.length][triangle.length];
        dp[0][0] = triangle[0][0];
        for (int i = 1; i < triangle.length; i++) {
            dp[i][0] = dp[i - 1][0] + triangle[i][0];  // 왼쪽 빗변 경로
            dp[i][i] = dp[i - 1][i - 1] + triangle[i][i];  // 오른쪽 빗변 경로
        }

        for(int i = 2; i < triangle.length; i++) {
            for(int j = 1; j < i ; j++) {
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
            }
        }

        // 마지막 행만 검사하면 된다
        for(int i = 0; i < triangle.length; i++) {
            if(answer < dp[triangle.length - 1][i]) {
                answer = dp[triangle.length - 1][i];
            }
        }
        return answer;
    }
}

전형적인 DP문제이다. 브루트 포스로 풀려면 n중 for문을 사용해야 하는데 n은 최대 500이다. 무조건 시간초과.

dp[i][j] 는 [i][j] 까지 도착할 수 있는 모든 경로들 중 최대값을 저장하도록 한다.

주어진 그림은 정삼각형이지만 2차원 배열의 행들을 그대로 나열해보면 직각삼각형이 된다.

이 형태에서 힌트를 얻어 초기화를 할 수 있다.

정삼각형이라고 봤을 때 양 옆 빗면을 그대로 따라가는 경로 2가지를 dp를 돌리기 전에 바로 구할 수 있게 된다.

그 후 2중 for문을 통해 dp를 돌렸다.

이때 for ( int j ) 의 범위를 ( j < triangle.length ) 로 잡아도 잘 돌아가긴 하지만 그래도 최대한 시간을 단축시켜보려고    ( j < i ) 로 잡았다.

이제 모든 경로의 도착지점인 마지막 행의 열들을 검사하여 최대값을 알아낼 수 있다.

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

사용할 숫자 int N, 만들어야하는 숫자 int number 가 주어진다.

N을 사용해 만든 사칙연산 식의 결과가 number이 되도록 할 때 N의 최소 사용횟수를 반환해야한다.

1. NN의 형태는 N을 두 번 사용한 것이다. ex : 55 -> 5를 두 번 사용)

2. 최소값이 8보다 클 경우 -1을 반환한다.

풀이 .

class Solution {
    int answer = -1;

    public void dfs(int cnt, int calc, int N, int number) {
        if(calc == number) {
            if(answer == -1 || answer > cnt) {  // 정답이 한 번도 들어온 적이 없거나 최소값을 갱신한 경우
                answer = cnt;
            }
            return;
        }

        int temp = N;
        for(int i = 1; i <= 8 - cnt; i++) {  // N이 8개까지만 사용되도록 함
            dfs(cnt + i, calc + temp, N, number);
            dfs(cnt + i, calc - temp, N, number);
            dfs(cnt + i, calc * temp, N, number);
            dfs(cnt + i, calc / temp, N, number);

            temp = temp * 10 + N;  // N을 하나 더 붙임
        }
    }

    public int solution(int N, int number) {
        dfs(0, 0, N, number);
        return this.answer;
    }
}

분류는 DP이지만 DFS로 풀었다. 솔직히 어떻게 DP로 풀 수 있는지도 모르겠다.

int cnt를 사용해 반복문 내에서 사용할 수 있는 N의 개수를 제한했다.

정답 처리는 됐지만 사실 틀린 코드이다.

5*5+5/5 처럼 사칙연산의 규칙에 의해 연산자의 순서보다 *, / 연산자를 먼저 계산하는 경우는 고려할 수 없기 때문이다.

문제에 "연산자는 무조건 들어온 순서대로 계산된다." 라는 조건이 있어야만 온전히 정답일 수 있는 코드.

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

사람들의 몸무게가 담긴 int[] people, 구명보트가 버틸 수 있는 최대 무게 int limit 가 주어진다.

구명보트를 사용해 모든 사람을 옮기기 위해 최소 몇 번을 태워야 하는지 반환해야한다.

1. limit은 사람들 중 가장 무거운 사람보다 항상 크게 주어지기 때문에 모두 옮기는 것은 불가능한 경우는 없다.

2. 보트에는 한 번에 2명 까지만 탈 수 있다. (무게가 남더라도)

풀이 .

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        int min = 0;

        Arrays.sort(people);

        // 몸무게가 가장 무거운 사람부터 판단한다.
        for(int max = people.length - 1; min <= max; max--) {
            if(people[max] + people[min] > limit)  // 가장 작은 수와 함께 탈 수 없다면 가장 큰 수는 반드시 혼자 타야만 한다
                answer ++;  // 가장 큰 수 먼저 보낸다. min은 그대로 유지하면서 max만 변경한다
            else {
                answer ++;  // 둘을 같이 보낸다
                min ++;
            }
        }

        return answer;
    }
}

처음에 생각한 방식은 위 코드와 달랐다.

max 부터 검사를 실시하는 건 동일했지만 min과의 짝은 맨 마지막에 검사했다.

(max, max-1), (max, max-2), ... , (max, min) 순으로 검사했다는 이야기.

이유는, 가장 좋은 카드인 min을 처음부터 써버리는 것 보다는.. 무거운 쌍부터 검사해보고 전부 안 될 경우에서야 (max, min) 을 태워 보내는 것이 효율적일 거라고 생각했다. 

(가장 좋은 카드인 min을 최대한 아껴놨다는 느낌? min이 나중에 더 요긴하게 사용될 수도 있으니까)

하지만 이런식으로 짰더니 시간초과가 났다.

O(n^2) 이고 n=50,000 이기 때문에 가능할 거라고 생각했는데 아니었다.

(50,000 = 5 * 10^4 = 25 * 10^8 = 25 * 1억 이고 25를 상수로 날리면 1억은 1초에 들어오니까. 근데 이게 틀린 계산이었다. 식은 전개하기 전에 n 앞에 상수가 붙어있을때나 날릴 수 있는거지 전부 전개하고 나서 내 마음대로 25를 날려버린 게 틀렸다.)

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

위 코드는 O(n) 으로 무사히 통과가 가능하다.

처음부터 (max, min) 조합을 검사하면 min을 너무 빨리 낭비하는 것 아니냐는 처음의 생각은 틀렸다.

max 보다 큰 수는 없기 때문에 min 을 남겨둔다고 해도 더 유용하게 쓰일 때는 오지 않는다.

(max, min) <= limit 이라면 ( ?, min ) 에서 ? 자리에 max 가 아닌 다른 어떤 것이 오더라도 전부 ( ?, min ) <= limit 이다.

따라서 max와 min을 바로 같이 보내버려도 정답에 영향을 미치지는 않는다는 것.

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

숫자형 문자로 이뤄진 String number 과 int k가 주어진다.

number 에서 숫자를 k개 제거했을 때 나올 수 있는 수의 최대값을 String으로 반환해야한다.

(단, number 안에서 유지되는 숫자들의 순서가 바뀌면 안 된다. number의 수들로 가장 큰 조합을 찾아내는 게 아니라는 뜻)

풀이 1.

class Solution {
    public String solution(String number, int k) {
        // StringBuilder 안 쓰면 시간초과
        StringBuilder sb = new StringBuilder();

        // j의 범위에 1씩 증가하는 i를 더하는 이유는 뽑아야 하는 숫자가 number.length()-k개에서 하나씩 줄어들기 때문
        // 예를들어 length : 7, k : 3 이라면 새로 뽑아야 하는 수는 총 4개
        // 즉, 늦어도 [k] 에서는 첫번째 수를 뽑아야 하나는 것
        // 이는 다시말하면 뒤에서부터 3개(length - k - 1)는 남겨놓고 나머지 범위에서 하나를 뽑아야 한다는 것
        // 숫자를 하나씩 뽑을 때마다 뒤에 남겨놔야 하는 수의 개수도 하나씩 줄어든다.
        // 그래서 1씩 증가하는 i를 더해준다

        int next = 0;
        for(int i = 0; i < number.length() - k; i++) {
            char max = '0';
            for(int j = next; j <= k + i; j++) {
                if(max < number.charAt(j)) {
                    max = number.charAt(j);
                    next = j + 1;  // 다음 자리수를 선택할 범위의 시작점은 이전 자리수를 선택한 바로 다음으로 잡는다
                }
            }
            sb.append(max);
        }
        return sb.toString();
    }
}

혼자서 답을 생각하지 못하고 다른이의 코드를 참고했다.  ( O(n^2) 의 시간 복잡도 )

k개의 숫자를 제거해야한다. 다시말해 number.length - k 개의 숫자를 뽑아야 한다.

각 자리의 숫자를 어디에서 뽑을지 범위를 특정할 수 있다.

(특정 가능한 범위에서 그때마다 가장 큰 수를 뽑으면 되기 때문에 그리디)

첫번째 자리수를 뽑으려면 일단 뒤에서부터 number.length - k - 1 개는 남겨두어야 한다. 그렇지 않으면 남아있는 모든 수를 다 뽑아도 number.length - k 개를 채우지 못할 수도 있기 때문.

이를 풀어서 다시 말하면 첫번째 자리 수는 반드시 [0] ~ [k] 에서 나와야 한다.

이 범위에서 가장 큰 수를 골라 첫번째 자리수로 삼는다.

두번째 자리는 첫번째 자리를 뽑은 바로 다음 인덱스부터 탐색해야한다.(int next) 이번에는 뒤에서부터 number - k - 2 개를 남겨두어야 한다. (뽑은 숫자가 늘어날 때마다 뒤에서부터 남겨둬야 하는 숫자의 개수는 줄어든다)

즉, i 번째 수를 뽑는 반복 for ( int i ) 를 한 번 돌 때마다 그 안에서 실질적으로 i 번째 수를 찾는 역할을 하는 for ( int j )의 범위에 +i 를 해주어야 한다.

다시 말하면 탐색 범위의 끝 인덱스는 [k], [k+1], [k+2] ... 이렇게 늘어난다는 이야기.

풀이 2.

import java.util.Stack;

class Solution {
    public String solution(String number, int k) {
        char[] result = new char[number.length() - k];
        Stack<Character> stack = new Stack<>();

        for (int i=0; i<number.length(); i++) {
            char c = number.charAt(i);
            while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
                stack.pop();
            }
            stack.push(c);
        }
        for (int i=0; i<result.length; i++) {
            result[i] = stack.get(i);
        }
        return new String(result);
    }
}

'다른 사람의 풀이' 에서 보고 배운 코드이다.  ( O(n) 의 시간 복잡도 )

문자열을 반복을 돌면서 전부 스택에 집어넣는다. 

이때 새로 들어오는 문자가 가장 최근에 들어온 문자보다 크다면 최근에 들어온 문자는 빼버린다.

그 후 스택에서 필요한만큼의 문자를 꺼내 반환한다.

O(n^2) 에서 O(n) 으로 줄어들었다.

대체 어떻게 이런 생각을 하는거지..?