소소한 개발일지

문제

m x n의 integer 행렬이 있을때, 만약 어떤 원소의 값이 0이라면 해당 행과 열을 모두 0으로 만들어야 한다.

해당 변수에 직접 수정해야 한다.

예시

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

제약조건

m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

풀이 : 구현

쉬운 문제처럼 보이지만 살짝 함정이 있어 두 번 정도 고치면서 풀었다.

1. 0이 보이면 해당 행과 열을 모두 0으로 만들기

행렬의 모든 원소를 방문하다가 원소가 0이면 해당 원소의 행과 열을 0으로 만들었다.

하지만 이는 잘못된 논리였다.

방문하지 않은 원소를 0으로 만들어버리면 방문했을 때 해당 원소의 행과 열도 0으로 만들었다. 기각!

2. boolean 행렬으로 값이 변한 원소인지 확인하기

1번과 비슷하되 비교 연산을 하나 더했다.

boolean 행렬로 0으로 바뀐 원소인지 아닌지를 체크해서 원소가 0이라도 변한적이 있다면 다른 행과 열에 영향을 끼치지 않게 했다.

음, 작동이 잘 되었지만 조금 더 보완할 수 있을 것 같았다. 보류!

3. 0으로 바꿀 boolean 배열 확인하기

행렬의 모든 원소를 방문하다가 원소가 0이면 해당 행과 열에 해당하는 index에 true 값을 줬다.

그 후, 다시 모든 원소를 방문하고, 행이든 열이든 boolean 배열의 값이 true라면 해당 원소를 0으로 줬다. 통과!

코드는 아래와 같습니다.

class Solution {
    public void setZeroes(int[][] matrix) {
        boolean[] rowZero = new boolean[matrix.length];
        boolean[] colZero = new boolean[matrix[0].length];
        
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    rowZero[i] = true;
                    colZero[j] = true;
                }
            }
        }

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (rowZero[i] || colZero[j]) {
                    matrix[i][j] = 0;
                }
            }
        }        
    }
}

어렵진 않으나 실수하기 쉬운 구현 문제였습니다.

의견 및 질문은 늘 환영합니다 :)

문제

중복되지 않은 숫자 후보인 배열과 integer 타겟이 주어지고, 숫자 후보들을 선택해 만든 조합의 합이 타겟이 되는 중복되지 않는 조합들의 list를 반환해야 합니다. 조합은 어떤 순서로 반환해도 됩니다.

같은 숫자를 몇 번이든 선택해도 좋습니다. 두 조합이 있을 때, 선택된 숫자의 횟수가 다르다면 중복되지 않는 조합이라고 할 수 있습니다.

더해서 타겟이 되는 조합의 수는 150개 미만으로 테스트케이스가 주어집니다.

예시

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

2와 3이 후보라면, 2 + 2 + 3 = 7. 2가 여러 번 사용 되었습니다.
7이 후보라면, 7 = 7.
두 조합 밖에 없습니다.

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Input: candidates = [2], target = 1
Output: []

주어진 후보에서 1을 만들 수 있는 조합은 없습니다.

풀이 : Backtracking

문제를 봤을 때 직관적으로 푼다면 제일 작은 숫자를 최대한 선택하고 타겟이 되는지 확인하고, 된다면 해당 조합을 저장하면 될 것 같았다.

그 후 넣었던 작은 숫자를 빼고 그 다음 큰 숫자를 넣어보는 방식으로 처리하면 될 것 같다 생각했다.

물론 합이 타겟을 넘어도 다음 숫자를 넣을 만큼 기존 숫자를 빼야한다.

예시 1번 이라면 2를 4번까지 넣었을 때 8이기에 다음으로 큰 숫자인 3을 넣을 수 있게 2개를 뺀 후 넣으면 첫번째 조합인 [2, 2, 3]이 된다.

처음에는 for 문으로 작성하면 될려나 했지만, 가능은 하겠지만 조건식이 복잡할 것 같다는 생각이 들어 recursive한 방식으로 진행하는게 좋다고 생각났다. 처음 생각한 아이디어에서 크게 벗어나지 않고 깔끔하게 코드를 작성해 보았다.

recursive 하게 첫 숫자 후보부터 모든 숫자를 넣어 합이 타겟이 되는지 확인한다.

합이 타겟이 된다면 해당 조합을 저장한다.

합이 타겟보다 크면 해당 조합에서는 어떤 숫자를 더 넣어도 타겟보다 클테니 그 전의 조합으로 돌아간다.

합이 타겟보다 작으면 해당 조합에 숫자 후보를 한 번 더 넣어서 recursive 하게 조합을 추가한다.

코드는 아래와 같습니다.

class Solution {
    List<Integer> comb = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();

    public void combination(int[] candidates, int target, int idx) {
        if (target < 0) return ;
        if (target == 0) {
            ans.add(new ArrayList<>(comb));
            return ;
        }

        for (int i = idx; i < candidates.length; i++) {
            comb.add(candidates[i]);
            combination(candidates, target - candidates[i], i);
            comb.remove(comb.size() - 1);
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        combination(candidates, target, 0);
        return ans;
    }
}

참고로 조합의 합을 확인하는 방식이 아니라 처음 타겟에서 숫자 후보를 계속 빼서 0이 되는지 아닌지 확인하는 방식으로 진행했습니다.

모든 조합을 추출하되, 어떤 조건에서는 더 추출할 필요가 없는지 조건을 걸면 되는 전형적인 backtracking 문제였습니다.

의견 및 질문은 늘 환영합니다 :)

문제

당신은 계단을 오르고 있습니다. 정상까지 n개의 계단을 올라가야 합니다.

한 번 오를 때 1개나 2개의 계단을 올라갈 수 있습니다.

몇 개의 중복되지 않은 방법으로 정상에 올라갈 수 있을까요?

예시

Input : n = 2

Output : 2

1. 1계단 + 1계단

2. 2계단

Input : n = 3

Output : 3

1. 1계단 + 1계단 + 1계단

2. 1계단 + 2계단

3. 2계단 + 1계단

풀이 : DP

문제를 딱 보자마자 "아 이건 규칙이 있다!" 라고 생각했습니다.

쉽게 떠올릴 수 있는 피보나치 문제랑 비슷하다고 느꼈고 빠르게 풀었습니다.

1개의 계단일 경우는 1가지 방법 (1)

2개의 계단일 경우는 2가지 방법 (1 + 1, 2)

3개의 계단일 경우는 3가지 방법 (1 + 2 / 1 + 1 + 1, 2 + 1)

4개의 계단일 경우는 4가지 방법 (1 + 1 + 2, 2 + 2 / 1 + 2 + 1, 1 + 1 + 1, 2 + 1 + 1)

계속 이어가다 보면 n - 2의 가짓수와 n - 1의 가짓수를 더하면 계단이 n개일 때의 방법의 갯수를 알 수 있습니다.

$$ n = (n-1) + (n-2) $$

코드는 아래와 같습니다.

class Solution {
    public int climbStairs(int n) {
        if (n == 1)
            return 1;
        
        int[] ways = new int[n + 1];

        ways[0] = ways[1] = 1;

        for (int i = 2; i <= n; i++) {
            ways[i] = ways[i - 1] + ways[i - 2];
        }

        return ways[n];
    }
}

DP문제를 처음 접하기에 좋은 문제 같습니다.