kwang2134 님의 블로그

[NeetCode-LeetCode] Rotate Image - Medium접근행렬 회전풀이n x n 배열의 원소들을 90도로 회전한 결과를 반환하는 문제이다. 원소를 그대로 오른쪽 90도로 돌린 상태로 만들면 되는데 추가 적인 공간을 할당하지 않고 주어진 배열을 조작해서 변경해야 한다. 수학과 공간 지각 문제다 보니 조금 만나기 싫은 유형의 문제였다. public void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i 90도로 회전하는 방법은 행렬을 전치한 뒤에 각 행을 뒤집게 되면 90도로 전환이 된다고 한다. 위는 행렬을 전치하는 과정으로 행과 열의 위치를 바꾸는 것이다.  for (int i = 0..

[NeetCode-LeetCode] Non-overlapping Intervals - Medium접근그리디풀이구간이 주어지고 겹치는 구간을 제거해 총 제거된 구간이 몇 개인지 구하는 문제이다. 아래와 같은 구간이 주어질 때intervals = [[1,2],[2,3],[3,4],[1,3]][1,2]와 [2,3]은 2라는 구간이 접하긴 하지만 접하는 경계면은 겹치지 않는 것으로 넘어가게 되나 [1,2]와 [2,3]을 합친 구간인 [1,3]이 뒤에 존재하기 때문에 두 구간 중 겹치는 한 구간을 제거해야 하는데 문제에서 요구하는 것은 겹치는 구간을 제거하는 최소의 비용을 원하기 때문에 [1,2], [2,3]이 제거되는 것이 아닌 [1,3]이 제거되는 것이다. public int eraseOverlapInt..

[NeetCode-LeetCode] Jump Game - Medium접근dfsgreedy풀이배열이 주어지고 각 인덱스에는 점프할 수 있는 최댓값이 들어있다. 첫 인덱스에서 시작해 마지막 인덱스에 도달할 수 있는지 검사하는 문제이다. 인덱스의 값이 3이라면 1,2,3 세 가지 경우로 점프를 할 수 있다. 가장 간단하게 생각하면 dfs를 사용해 모든 경우를 수행해 도달이 가능한지 보면 된다. 이 문제는 그리디를 사용해 해결하는 문제로 dfs로 모든 경우를 탐색했을 때와 그리디를 사용했을 때의 성능 차이를 보려고 한다. public boolean canJump(int[] nums) { boolean[] visited = new boolean[nums.length]; ret..

[NeetCode-LeetCode] Longest Common Subsequence - Medium접근dp풀이가장 긴 공통 부분 수열의 길이를 구하는 문제이다. 바로 전에 풀었던 문제와 유사한 형태로 이번에는 숫자가 들어있는 배열이 아닌 문자열을 비교하여 구해야 한다. 예시를 보면 text1 = "abcde", text2 = "ace"라는 입력이 주어졌을 때 가장 긴 공통 부분 수열은 "ace"로 길이인 3이 정답이 된다. text1에서 순서대로 부분 수열을 만들었을 때 "ace"를 만들 수 있기 때문이다. 2차원 dp 카테고리의 문제인 만큼 dp를 사용해 풀면 된다. public int longestCommonSubsequence(String text1, String text2) { ..

[NeetCode-LeetCode] Longest Increasing Subsequence - Medium접근이진 탐색풀이가장 긴 증가하는 부분 수열의 길이를 구하는 문제이다. 그냥 증가하는 수열이 아니라 strictly increasing subsequence로 엄격한(?) 증가하는 부분 수열이다. 문제만 보고 이해가 잘 안 갔었는데nums = [0,1,0,3,2,3]위와 같은 배열이 있을 때 일반적인 증가하는 수열은 [0,1], [0,3], [2,3] 이렇게 최대 길이가 2인 부분 수열만 존재한다. 그러나 엄격하게 증가하게 증가하는 부분 수열의 경우 원소들을 증가하는 형태에 맞춰 삽입하여 수열을 만든다고 생각하면 된다. 예를 들어 [0,1]이라는 부분 수열이 만들어지고 그다음 0이 왔을 때 해당 원소..

[NeetCode-LeetCode] Maximum Product Subarray - Medium 접근dp풀이배열 내 연속된 원소들의 곱의 최댓값을 구하는 문제이다. 연속된 원소가 곱해졌을 경우에만 값으로 인정된다. [2, 3, -2, 4]라는 배열이 존재한다면 연속된 2, 3의 곱인 6은 값이 될 수 있지만 3, 4 사이엔 -2가 존재해 계산이 불가능하다. 원소는 음수 양수 모두 존재하기 때문에 가장 큰 값을 얻기 위해선 양수의 곱만 신경 쓸 것이 아니라 음수와 음수를 곱하는 경우도 신경을 쓰고 계산해야 한다.  public int maxProduct(int[] nums) { if (nums.length == 0) { return 0; } i..

[NeetCode-LeetCode] Decode Ways - Medium 접근dp풀이숫자를 문자로 해독할 때 해독한 문자열이 몇 가지로 표현할 수 있는지 구하는 문제이다. 숫자는 1부터 26까지 알파벳과 매칭되고 26을 넘어가는 경우 27이 아닌 2와 7로 나눠져 해석된다. 그렇다 보니 10~26 사이의 숫자들도 나눠서 해석될 수 있다. 17이라는 숫자가 있는 경우 17로 해석되어 q가 될 수 도 있고 1과 7로 나눠져 ag로 해석이 될 수 도 있기 때문에 이렇게 해석될 수 있는 모든 경우의 수를 구해야 한다.  dp 문제로 앞에서부터 체크하며 값을 쌓아나간다. public int numDecodings(String s) { if (s == null || s.isEmpty() || s...

[NeetCode-LeetCode] Palindromic Substrings - Medium 접근중심 확장풀이팰린드롬을 만족하는 부분 문자열을 찾는 문제이다. 문자열 내에 존재하는 모든 부분 문자열에 대해 팰린드롬을 검사하고 개수를 반환하여야 한다. 똑같은 문자라도 문자열 내 위치가 다르다면 한 개의 부분 문자열로 취급한다. 예시에 있는 "aaa" 문자열의 경우에도 첫 번째 두 번째 세 번째 a 모두 개별 문자로 취급하여 "aaa" 문자열의 총 부분 팰린드롬 문자열은 "a", "a", "a", "aa", "aa", "aaa"로 6개의 팰린드롬 부분 문자열을 가지고 있다.  팰린드롬이란 데칼코마니처럼 문자열을 앞으로 읽어도 뒤로 읽어도 동일한 문자열을 말한다. 팰린드롬 문자열인지 검사를 하기 위한 방법은 ..

[NeetCode-LeetCode] House Robber II - Medium접근dp풀이바로 전에 풀었던 집 터는 문제 2편이다. 연속된 집을 털 수 없는 규칙은 동일하나 이번엔 집이 원형으로 이루어져 있다는 점이다. 전 문제는 집이 직선 형태로 이루어져 있기 때문에 연속된 집만 털지 않고 처음부터 끝까지 진행하면 되었으나 이번에는 원형으로 첫 집과 마지막집이 연결되어 있기 때문에 해당 부분을 고려해야 한다.  원형으로 집이 연결되어 있다지만 첫 번째 집과 마지막 집만 연결되어 있는 거 기 때문에 특별히 추가로 신경 쓸 내용은 많지 않다. 첫 번째 집을 턴다면 마지막 집을 털지 않으면 되는 것이고 마지막 집을 턴다면 첫 번째 집을 털지 않으면 되는 것이기 때문이다. 이렇게 두 가지 케이스로 나눠서 이 ..

[NeetCode-LeetCode] House Robber - Medium접근dp풀이집을 약탈하여 최대한 많은 돈을 모으는 문제로 배열엔 집에서 약탈할 수 있는 돈의 금액이 들어있다. 조건으로 집을 연속하여 터는 경우 경보가 울려 경찰이 오기 때문에 연속되게 약탈을 할 수는 없다. dp를 사용하면 해결되는 문제이다. public int rob(int[] nums) { if (nums.length == 0) { return 0; } if (nums.length == 1) { return nums[0]; } int[] dp = new int[nums.length]; dp[0] = nums[..