풀이

DP배열을 생성해, Bottom Up방식으로 풀이.

dp[0]=1이 왜 1인가에 대해 고민을 좀 많이 했던 문제였다.

문자열의 길이가 0인게 없지않나?? 라는 생각을 많이했다.

1. 문자열의 길이가 0인 경우가 ""의 경우가 존재할 수도 있겠구나라는 생각

2. dp[0]을 1로 설정해주지 않으면 문제 풀이자체가 되지않겠구나. dp[i]=0일테니까.

고민을해서 위와 같은 결론을 내렸다.

위의 그림은, 해당 문제의 Solution 탭의 그림의 일부인데.

문제에서 말하는 좋은 문자열이 되기 위해서는

1. 마지막에 해당 숫자만큼 붙였을때 알맞은 길이의 숫자가 되는것

2. 그러기 위해서는 i가 zero, one보다 크거나 같을때 : 해당 dp[i]가 ++될 것이다.

까지 생각을 할 수 있었다.

이게 무슨말인고? 하니

위의 그림에서 자세하게 idx = 5까지가는 과정을 살펴보자.

모든 dp[idx]배열의 값에, 들어갈 수 있는 경우의 수는

dp[idx-zero]나, dp[idx-one] 두 경우에서 만족하는 경우의 배열들을 추가해준 값이 해당 dp[idx]에 들어갈 수 있는 총 문자열의 개수가 될 수밖에 없다.

class Solution {
    public int countGoodStrings(int low, int high, int zero, int one) {
    	int answer = 0;    	    	
    	int[] dp = new int[high+1];
    	dp[0] = 1;

    	for(int i=1; i<=high; ++i) {
    		if(i>=zero) dp[i] += dp[i-zero];
    		if(i>=one) dp[i] += dp[i-one];
    		
    		dp[i] %= 1_000_000_007;
    	}
    	
    	for(int i=low; i<=high; i++) {
    		answer += dp[i];
    		answer %= 1_000_000_007;
    	}
    	
        return answer;
    }
}

O(n) (n=high)의 시간복잡도를 가지는 코드가 완성됐다.

풀이

DFS를 이용해서, 해당 칸을 탐색할 수 있을 경우 탐색해서 모든 경우의수를 구한다음 최대값을 구하는 단순 DFS문제라고 생각했다.

class Solution {
	public static long max = -1;
	
    public long mostPoints(int[][] questions) {
       	if(questions.length==1) return questions[0][0];

        boolean[] bl = new boolean[questions.length];
        
        for(int i=0; i<questions.length; i++) {
        	dfs(questions[i][0], i, questions[i][1]+1, questions, bl);
        }        
    	return max;
    }
    
    public void dfs(long sum, int idx, int tmp, int[][] questions, boolean[] bl) {
    	if(idx >= questions.length) {
    		max = Math.max(max, sum);
    		return;
    	}    	
    	
    	for(int i=idx; i<questions.length; i++) {    		    		
    		if(tmp != 0) {
    			tmp--;
    			continue;
    		}
    		if(bl[i]) return;
    		bl[i]=true;
    		dfs(sum+questions[i][0], i+1, tmp+questions[i][1]+1, questions, bl);
    		bl[i]=false;
    	}
		max = Math.max(max, sum);
    }
}

분명 IDE의 콘솔에서는 정답이 출력되는데 왜 틀렸다고 하는지 모르겠다. 나는 100이 나오는데 ㅡㅡ

머리 환기시키고 재도전해봐야겠다..

풀이

DP배열의 idx의 값은 해당 idx까지 서로 탐색을했을때, 겹치지 않는 최대 경우의 수를 나타낸다.

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;

        int[] dp = new int[m+1];
        for (int i=1; i<=n; i++) {
        	int prev = 0;
            for (int j=1; j<=m; j++) {
                int curr = dp[j];
                if (nums1[i-1] == nums2[j-1]) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j-1], curr);
                }
                prev = curr;
            }
        }
        return dp[m];
    }
}

https://leetcode.com/problems/spiral-matrix-ii/

풀이

방향에 대한 변수와, 한 칸씩 체크해줄 변수를 지정해 준 뒤, 카운팅만 잘 해주면 되는 문제였다.

class Solution {		
	
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int top = 0;
        int bottom = n-1;
        int left = 0;
        int right = n-1;
        int cnt = 1;
        while(cnt <= n*n) {
        	for(int i=left; i<=right; i++) {
        		matrix[top][i] = cnt;
        		cnt++;
        	}
        	top++;
        	  
        	for(int i=top; i<=bottom; i++) {
        		matrix[i][right] = cnt;
        		cnt++;
        	}
        	right--;
        	
        	for(int i=right; i>=left; i--) {
        		matrix[bottom][i] = cnt;
        		cnt++;
        	}
        	bottom--;
        	
        	for(int i=bottom; i>=top; i--) {
        		matrix[i][left] = cnt;
        		cnt++;
        	}
        	left++;
        	
        }
        return matrix;
    }
}

https://leetcode.com/problems/spiral-matrix/

첫번째풀이

두통이 조금 심한 날이라 깊게 생각하기 싫었다.
처음 생각난게 DFS, 두번째로 생각난건 while문으로 때려풀기였다.
하나하나 진행해보자

class Solution {		
	
    public List<Integer> spiralOrder(int[][] matrix) {    	
    	List<Integer> list = new ArrayList<>();    	
    	int sum = 0;
    	
    	for(int[] m : matrix) {
    		for(int n : m) {
    			sum++;
    		}
    	}
    	
    	dfs(list, matrix, 0, 0, sum);    	
    	return list;
    }
    
    public void dfs(List<Integer> list, int[][] matrix, int i, int j, int sum) {
    	if(sum == list.size()) return;
    	if(i < 0 || i >= matrix.length) return;
    	if(j < 0 || j >= matrix[0].length) return;
    	if(matrix[i][j]==-101) return;
    	
    	list.add(matrix[i][j]);
    	matrix[i][j] = -101;
    	
    	dfs(list, matrix, i, j+1, sum);
    	dfs(list, matrix, i+1, j, sum);
    	dfs(list, matrix, i, j-1, sum);
    	dfs(list, matrix, i-1, j, sum);    	
    }
}

 
재귀호출의 순서를 어떻게 바꿔도, 시계방향으로 한 방향씩 끝까지 탐색한 후에 다른방향으로의 탐색이 어려운 것 같다.
 

실패

두번째 풀이

그냥 while문안에 cnt와 idx를 올려가며 때려박아서 풀었다. 설명이 굳이 필요없다. 시계방향으로 돌리는 것을 직접 노가다로 구현..

import java.util.ArrayList;
import java.util.List;

class Solution {		
	
    public List<Integer> spiralOrder(int[][] matrix) {    	
    	List<Integer> list = new ArrayList<>();    	
    	int sum = matrix.length * matrix[0].length;   	
    	int cnt = 0;
    	int idx = 0; 
    	while(cnt<sum) {
    		for(int i=idx; i<matrix[0].length; i++) {
    			if(matrix[idx][i] != 101) {
    				list.add(matrix[idx][i]);
    				cnt++;
        			matrix[idx][i] = 101;
    			}
    		}
    		for(int i=idx; i<matrix.length; i++) {
    			if(matrix[i][(matrix[0].length-1)-idx] != 101) {
    				list.add(matrix[i][(matrix[0].length-1)-idx]);
    				cnt++;
    				matrix[i][(matrix[0].length-1)-idx] = 101;
    			}    			
    		}
    		for(int i=matrix[0].length-1; i>=idx; i--) {
    			if(matrix[(matrix.length-1)-idx][i] != 101) {    				
    				list.add(matrix[(matrix.length-1)-idx][i]);
    				cnt++;
    				matrix[(matrix.length-1)-idx][i] = 101;
    			}    			
    		}
    		for(int i=matrix.length-1; i>=idx; i--) {
    			if(matrix[i][idx] != 101) {
    				list.add(matrix[i][idx]);
    				cnt++;
    				matrix[i][idx] = 101;
    			}    			
    		}
    		idx++;
    	}
    	return list;
    }
}

https://leetcode.com/problems/minimum-path-sum/

풀이

이차원배열 grid에서, 오른쪽, 아래로만 이동할 수 있을 때, 모든 숫자의 합을 최소화 하는 경로를 찾는 dp문제.
 
오른쪽, 아래로만 이동할 수 있으므로, i나 j가 0일때만 고려해주면 됐다.

class Solution{
	 
    public int minPathSum(int[][] grid) {
	        
	    for(int i=0; i<grid.length; i++) {
	    	for(int j=0; j<grid[i].length; j++) {	    		
	    		dp(grid, i, j);
	    	}
	    }
	    
	    return grid[grid.length-1][grid[0].length-1];
    	
	}
    
    public void dp(int[][] grid, int i, int j) {
    	if(i==0 && j==0) return;
    	else if(i==0) grid[i][j] += grid[i][j-1];
    	else if(j==0) grid[i][j] += grid[i-1][j];
    	else grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
    	
    }
}