kwang2134 님의 블로그

[Grind75-LeetCode] Word Search - Medium접근dfs풀이2차원 배열에 문자들이 저장되어 있고 문자들을 이어 주어진 단어를 만들 수 있는지 검사하는 문제이다. 상하좌우로 단어를 연결할 수 있기 때문에 dfs를 사용해 풀어주었다. private static final int[] dx = {-1, 1, 0, 0}; private static final int[] dy = {0, 0, -1, 1}; public boolean exist(char[][] board, String word) { for (int i = 0; i 상하좌우 이동을 위한 배열을 만들고 2차원 배열을 순회하며 주어진 단어의 첫 번째 문자와 배열에 들어있는 문자가 같을 때 dfs를 시작한..

[Grind75-LeetCode] Letter Combinations of a Phone Number - Medium접근dfs풀이휴대폰 자판에 있는 알파벳을 가지고 나올 수 있는 모든 조합을 구하는 문제이다. 입력으로 여러 개의 숫자가 문자열로 주어지고 해당 숫자칸에 있는 알파벳들의 조합을 구해야 한다. 문자열이 "23"으로 주어졌을 때 2에 해당하는 a, b, c와 3에 해당하는 d, e, f를 조합하는데 각각 번호의 알파벳을 한 개씩 사용해서 조합을 만들어야 한다. 즉 2번과 3번의 알파벳이 한 개씩 사용된 ad, ae, af는 가능하지만 각 번호의 알파벳을 두 번 사용한 ab, de 같은 경우는 불가능하다.  private static final String[] DIGITS_MAP = { ..

[Grind75-LeetCode] Container With Most Water - Medium 접근투 포인터풀이수직선의 길이가 들어있는 배열이 주어지고 수직선 두 개를 선택해 컨테이너를 만들 때 가능한 컨테이너의 넓이 중 가장 큰 넓이를 반환하는 것이다. 그러기 위해선 기둥이 될 두 수직선을 골라야 하는데 투 포인터를 사용해 최댓값을 찾는다. public int maxArea(int[] height) { int start = 0; int end = height.length - 1; int maxArea = 0; while (start 시작과 끝에서 각 포인터가 시작되고 각 포인터가 만날 때까지 모든 넓이를 찾게 된다. 현재 포인터를 기준으로 넓이를..

[Grind75-LeetCode] Construct Binary Tree from Preorder and Inorder Traversal - Medium접근dfs풀이전위 순회, 중위 순회 순서가 담긴 배열을 통해 이진트리를 만들어내는 문제이다. 전위 순회의 경우 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 순회가 되고 중위 순회의 경우 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순서로 순회가 된다. 즉 전위 순회 배열을 루트로 사용하고 중위 순회 배열을 통해 양쪽 서브트리를 찾는 방식으로 진행해야 한다. public TreeNode buildTree(int[] preorder, int[] inorder) { return treeBuilder(preorder, inorder,..

[Grind75-LeetCode] Unique Paths - Medium접근dp조합풀이m x n 좌표 평면 위에서 왼쪽 상단 (0,0)에서 출발해 오른쪽 하단 (m-1, n-1)까지 갈 수 있는 고유의 경로를 구하는 문제이다. 고유 경로는 겹치지 않는 모든 이동 경로를 말하며 이동은 오른쪽, 아래 방향으로만 가능하다. dfs를 통해서도 찾을 순 있지만 중복 계산이 많이 발생하고 모든 경로 탐색으로 최적화를 위해 메모이제이션 배열을 사용하게 될 텐데 그럼 그냥 처음부터 dp를 통해 푸는 것이 효율적이다.  public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for(int i = 0; i dp 배열을 생성하고 ..

[Grind75-LeetCode] Longest Palindromic Substring - Medium접근구현풀이펠린드롬에 관한 문제로 문자열에서 가장 긴 펠린드롬 부분 문자열을 찾아 반환하는 문제다. 이때까지 펠린드롬 문자인지 확인하고 가장 긴 펠린드롬 문자열의 길이를 반환하는 문제를 풀었었다면 부분 문자열 자체를 찾아 반환해야 하는 문제이다.  public String longestPalindrome(String s) { if (s == null || s.isEmpty()) { return ""; } int start = 0; int end = 0;문자열이 비어있는지 체크를 해 주고 부분 문자열 반환을 위해 펠린드롬의 시작 인..

[Grind75-LeetCode] Binary Tree Right Side View - Medium 접근dfs풀이이진트리를 오른쪽에서 바라봤을 때 보이는 노드들을 루트에서 바닥까지의 순서로 반환하는 문제이다. 즉 트리의 제일 오른쪽 노드들을 순서대로 반환하면 된다. 각 레벨의 노드를 오른쪽에서 봤을 때 제일 먼저 만나는 노드를 반환하는 문제이기 때문에 오른쪽 서브트리의 노드만 해당하는 것이 아니라 해당 레벨에 맨 왼쪽 노드 하나만 존재한다면 해당 노드가 반환할 목표 노드가 된다.  public List rightSideView(TreeNode root) { List result = new ArrayList(); dfs(result, root, 0); return..

[Grind75-LeetCode] Subsets - Medium접근dfs풀이배열의 원소들을 중복 없이 조합 가능한 모든 조합을 찾는 문제이다. 비슷한 형태의 문제를 많이 풀었던 거 같은데 이 문제도 역시나 dfs를 사용해 모든 조합을 찾아주면 된다.  public List> subsets(int[] nums) { List> result = new ArrayList(); dfs(result, new ArrayList(), nums, 0); return result; }dfs 사용을 위해 결과 배열, 현재 사용 배열, 정수 배열, 시작 인덱스를 파라미터로 넘긴다. private void dfs(List> result, List current, int[] n..

[Grind75-LeetCode] Spiral Matrix - Medium접근구현풀이2차원 배열의 원소들을 나선형으로 접근할 때 원소 접근 순서를 List에 담아 반환하는 문제이다. 내용 자체는 정말 간단한 문제이기 때문에 예제 그림 한 번만 보면 바로 이해할 수 있는 문제이다. 내용 또한 크게 어려울 것 없기 때문에 쉽게 풀 수 있다. public List spiralOrder(int[][] matrix) { List result = new ArrayList(); int length = matrix.length * matrix[0].length; int xMax = matrix.length - 1; int yMax = matrix[0].length..

[Grind75-LeetCode] String to Integer - Medium접근구현풀이문자열을 정수로 변환하는 atoi 함수를 구현하는 문제이다. atoi는 C언어에 존재하는 ASCII to Integer로 문자열을 정수로 변환하는 자바의 parseInt와 같은 메서드이다. 기본적인 atoi 함수는 주어진 문자열을 정수로 변환하고 변환이 불가능한 경우 0을 반환한다. 그리고 범위 체크 부분이 존재하지 않기 때문에 범위를 벗어난 값이 들어오게 되면 의도치 않은 값이 반환되기도 한다. 반면 자바의 parseInt의 경우 똑같이 문자열을 정수로 변환하는 함수이지만 변환이 불가능한 경우 런타임 예외인 NumberFormatException를 던지게 되고 정수로 변환 가능한 범위인지도 체크하기 때문에 범위를..