전체 글 (42) 썸네일형 리스트형 [leetcode 75] 438. Find All Anagrams in a String 문제 해석 문자열 s와 p가 주어졌을 때 p가 s의 anagram인 위치들을 반환하기 위치들의 순서는 상관없음. anagram이란? 모든 원래 문자를 정확히 한 번만 사용하여 재배열해 형성된 단어 또는 구 예시 "abc"의 anagram은 "cba", "abc", "bca"등을 말함 정답 예 public List findAnagrams(String s, String p) { List output = new ArrayList(); // p의 길이 int pLength = p.length(); // s의 길이 int sLength = s.length(); if (pLength > sLength) { return output; } // p의 문자 개수를 기록할 배열 int[] pLetters = new int.. [leetcode 75] 409. Longest Palindrome 문제해석 소문자 혹은 대문자로 이루어진 문자열 s가 주어졌을 때 가장 긴 palindrome 문자열을 만들수 있는 길이를 반환 문자들은 대소문자를 구분한다 예를들어 "Aa"는 palindrome이 아니다. 정답 예 public int longestPalindrome(String s) { int[] chars = new int[128]; // 각 character를 아스키코드로 저장 후 횟수를 기억 for (int i=0; i [leetcode 75] 733. Flood Fill 문제해석 m x n 배열의 각 픽셀정보가 들어있는 image가 주어질 때 sr, sc, color가 주어진다. image[sr][sc]에 위치에 flood fill이라는 동작을 시킨다. flood fill을 하게되면 시작 픽셀이 되어서 해당 픽셀을 주어진 color로 변경하고 인접한 4방향의(위,아래,오른쪽,왼쪽) 픽셀 또한 color로 변경 시킨다. 변경된 4방향의 픽셀과 인접한 동일한 기존 픽셀들 또한 모두 주어진 color로 변경한다. 그리고 변경된 이미지를 반환 쉽게 말해서 그림판 색채우기를 떠올리면 될 것 같다. 정답 예 public int[][] floodFill(int[][] image, int sr, int sc, int color) { int existColor = image[sr][sc.. [leetcode 75] 98. Validate Binary Search Tree 문제해석 이진트리의 root가 주어졌을 때 유효한 이진탐색트리인지 반환 유효한 이진탐색트리란? 노드의 왼쪽 서브트리는 반드시 노드의 키값보다 작아야 한다 노드의 오른쪽 서브트리는 반드시 노드의 키값보다 작아야 한다 왼쪽과 오른쪽 서브트리 모두 이진탐색트리여야 한다 정답 예 1) 이진트리 inorder순회시 값이 정렬되는 특성을 이용한 풀이 List inorderVals = new ArrayList(); public boolean isValidBST(TreeNode root) { // inorder로 순회해서 inorderVals에 값을 담으면 // 정상적인 이진탐색트리의 경우 오름차순 정렬이 된다 inorder(root); for (int i = 0; i < inorderVals.size() - 1; i.. [leetcode 75] 102. Binary Tree Level Order Traversal 이진트리의 root가 주어지는 경우 level order 순회하기 level order란 각 트리의 level순으로 왼쪽부터 오른쪽 노드를 순차로 나열한 것 정답 예1) 재귀 List output = new ArrayList(); public List levelOrder(TreeNode root) { if (root == null) { return new ArrayList(); } recursive(root, 0); return output; } public void recursive(TreeNode node, int level) { if (node == null) { return; } List row; if (output.size() == level) { // level의 row를 처음 추가하는 경우 .. [leetcode 75] 704. Binary Search 문제해석 정렬된 숫자가 들어있는 배열 nums가 주어졌을 때 정수 target의 위치를 반환하기. 알고리즘의 시간복잡도는 O(log n)이어야 한다. 정답 예 public int search(int[] nums, int target) { int start = 0, end = nums.length - 1; int mid; while (start nums[mid]) { start = mid + 1; } else if (target < nums[mid]) { end = mid - 1; } else { return mid; } } return -1; } 이진탐색 기본 문제 [leetcode 75] 589. N-ary Tree Preorder Traversal 문제해석 n-ary 트리의 root가 주어졌을 때 preorder 순으로 방문해서 출력하기 preorder(전위순회)란 1. root를 방문한 뒤 2. 왼쪽 자식 노드를 반복해서 방문 3. 그 후 거슬러 올라가면서 오른쪽 자식노드를 방문 그 뒤는 2~3을 반복한다. 정답 예 public List preorder(Node root) { if (root == null) { return new ArrayList(); } List output = new ArrayList(); recursive(root, output); return output; } public void recursive(Node root, List output) { output.add(root.val); if (root.children == .. [leetcode 75] 121. Best Time to Buy and Sell Stock 문제해석 각 i번째 날의 주가가 들어있는 배열 prices가 주어졌을 때 가장 큰 수익이 날 수 있는 값을 반환하기 주식은 무조건 산 이후 날만 판매가 가능함 정답 예 public int maxProfit(int[] prices) { int length = prices.length; if (length == 1) { return 0; } int min = prices[0]; int maxProfit = 0; for (int i = 1; i price) { min = price; } int profit = price - min; // 현재가로 팔았을 경우 가격 비교 if (maxProfit < pr.. 이전 1 2 3 4 5 6 다음
