본문 바로가기
반응형

Algorithm66

32 : Longest Valid Parentheses ( leetcode / java ) * 해결 과정 괄호에 관한 문제이기 때문에 스택을 떠올렸고 스택을 이용하기로 생각했습니다. 그래서 저는 '(' 가 나오는 지점에서 검사를 시작하도록 했습니다. 그래서 ')'의 갯수에 따라 다시 변수를 + - 해준다음에, 최종적으로 0이 나오면 통과이고 아니면 종료입니다. 또한 ')'가 훨씬 많아 변수가 음수가 되면 종료입니다. 하지만 이 풀이법은 시간효율이 너무 좋지 않습니다. 먼저 확인해보겠습니다. class Solution { int answer=0; public int longestValidParentheses(String s) { for(int i=0;i 2020. 11. 3.
예산 : Summer/Winter Coding(~2018) ( 프로그래머스 / java ) programmers.co.kr/learn/courses/30/lessons/12982?language=java 코딩테스트 연습 - 예산 S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 programmers.co.kr *해결과정 dp로 푸는 방법과 일반적으로 접근하는 방법 2가지가 있다. 여기서 동전은 중복되서 사용되지 못하기 때문에 dp보다는 if문을 통해 바로 이동시켜 주는 것이 편리하다. dp로 계산하면 오히려 불필요한 연산들을 계속하여 O(동전의 갯수*예산)의 시간복잡도를 나타내고 통과는 하지만 효율적인 결과는 내지 못한다. 1. DP import java.ut.. 2020. 11. 3.
14430 : 자원 캐기 ( 백준 / java ) *해결 과정 오른쪽과 아래쪽만 이동하는 것에 유의하여 최대탐색 할 수 있는 숫자를 구하는 것이다. 그렇다면, BFS, DFS의 접근이 아니라 DP의 접근을 하는 것이 딱 눈에 띈다. 행이 0일때와, 열이 0일 때 2가지 경우를 나누어 먼저 초기 작업을 하고 이후에 (1,1)부터 왼쪽과 위쪽 값 중에 큰 값을 자신과 더하면서 업데이트하면 된다. 마지막으로 (N-1,M-1)의 숫자를 출력한다. 정형화 된 문제이다. package bj; import java.util.*; public class Main { static int N; static int M; static int[][] array; public static void main(String[] args) { // TODO Auto-generated .. 2020. 11. 2.
538 : Convert BST to Greater Tree ( leetcode / java ) * 해결 과정 BST이므로 이진탐색 트리임에 유의합니다. 하지만 이 문제에서 딱히 상관은 없습니다. 주어진 Tree에서 val값들을 변경 해야 합니다. 처음에는 어떤 방식과 흐름인지 이해하지 못했습니다. 단순히 전위순회, 중위순회, 후위순회 3가지 안에 포함되어 있을 것이라고 생각했습니다. 하지만 오른쪽 맨 아래로 이동 후, 부모로 올라오고 다시 왼쪽 노드로 가는 방식이었습니다. 문제가 원하는 순회의 방법으로 적절하게 이동할 수 있는지가 관건입니다. class Solution { int sum = 0; public TreeNode convertBST(TreeNode root) { if(root!=null) { convertBST(root.right); sum += root.val; root.val = s.. 2020. 11. 2.
501 : Find Mode in Binary Search Tree ( leetcode / java ) *해결 과정 이진탐색 트리라는 것을 친절하게 설명하고 있습니다. 그것보다도, 중복된 요소를 찾고 list로 반환하는 것이 더 중요해보입니다. Integer만을 다루는 Map의 형태이며 중복을 찾아야 하기 때문에 모든 요소 값에 따라서 등장할 때마다 +1씩 하도록 했습니다. 그리고 처음부터 순회하면서 value값이 최대로 큰 경우를 고르고 key값을 list에 넣어서 반환합니다. import java.util.*; class Solution { Map map = new HashMap(); public int[] findMode(TreeNode root) { if(root==null) return new int[]{}; DFS(root); int max = Collections.max(map.values().. 2020. 11. 2.
2504 : 괄호의 값 ( 백준 / java ) *해결 과정 괄호를 가지고 계산하는 것은 보통 stack을 이용하면 됩니다. 이 문제도 마찬가지로 stack을 이용합니다. 이전의 stack문제와 다른 것은, '(' 에 대한 ')'의 위치 index를 저장하고 재귀적으로 해결했지만 이번에는 그런 방식으로 하면 시간초과가 난다는 것입니다. 그래서 문자열을 하나씩 탐색하면서 Nlog(N)에 해결하도록 하였습니다. (N은 문자열 길이이고, 문자열을 하나씩 살펴보며 검사하지만 괄호 안에 다른 내용이 있을 경우 다시 while문 으로 모두 stack.pop()하는 과정이 있으므로 최악의 경우 N을 곱했습니다.) 특히 '('는 0으로 치환, '['은 1로 치환하여 stack에 저장하였으며 어차피 계산과정에서 0과 1을 만날 일이 없기 때문에 괄호라고 식별 가능합니.. 2020. 10. 30.
572 : Subtree of Another Tree( leetcode / java ) *해결 과정 t라는 트리가 s라는 트리에 포함되는지 확인하는 문제입니다. 간단하게 생각하면 각 root의 val값이 같을 때, 재귀적으로 비교해주면 됩니다. 하지만 예외 상황이 있네요. 아래의 경우입니다. 도대체 왜 val값을 독립적으로 만들지 않고 중복되게 만든 것이야!! 결국 우리는 "모든 노드를 순회하면서" val값이 같은 경우 해당 경우가 있는지 없는지 확인해야 합니다. 조건을 세워 봅시다. 초기조건 : 둘다 null이면 true입니다. 같다는 의미는 둘 다 leaf노드가 같다는 의미입니다. 혹시 한쪽만 null이면 false입니다. 당연히 s,t중 한 쪽만 특정 자손을 가지면 다르겠지요. 또한 val값이 서로 다르면 false입니다. 재귀 조건 + 반환조건 : s.left, t.left 와 s... 2020. 10. 30.
543 : Diameter of Binary Tree ( leetcode / java ) *해결 과정 리스트에서야 지름 구하는 것을 풀었지 tree에서 지름구하는 문제는 처음입니다. 처음에 root에서 왼쪽 자식의 맨 아래 자손 깊이, 오른쪽 자식의 맨 아래 자손의 깊이를 더해서 출력했는데 틀렸씁니다. 왜냐하면 꼭 루트에서 이어진 길이가 지름이라는 법이 없기 때문입니다. 그래서 각 노드를 모두 root라고 생각하고 순회하면서 비교해야 합니다. 리스트, 트리의 지름 = 가장 멀리 떨어져 있는 두 노드의 거리 빨간점을 기준으로 생각해봅시다. 해당 노드에서 지름은 어떻게 구할까요? 다음 2가지를 생각해 보시길 바랍니다. 1. 어떻게 해당 노드에서 지름의 길이를 구할 것인가 ( 종료 조건, 재귀로 계산하는 과정, return) 1-1. 무엇을 return 할 것인가? ( 최대 결과값을 반환 할 것인.. 2020. 10. 30.
563 : Binary Tree Tilt ( leetcode / java ) *해결과정 불쌍한 문제입니다. ㅜㅜ 비추수가 압도적으로 많습니다. 일반적인 tree의 문제가 아니라 그런 것 같습니다. 최근에 풀었던 파x 기업의 3번문제와 비슷합니다. postOrder 형식의 처리가 필요합니다. 즉, leaft쪽으로 먼저 이동해 root의 왼쪽 자식과 오른쪽 자식의 값을 계산하여 계속 부모쪽으로 올라오면서 최신화를 시켜주면 됩니다. 우리는 Tilt의 값을 찾으면 되기 때문에 굳이 TreeNode의 root값들을 최신화 시켜 줄 필요는 없습니다. class Solution { int totalTilt=0; public int findTilt(TreeNode root) { valueSum(root); return totalTilt; } public int valueSum(TreeNode .. 2020. 10. 30.
반응형

티스토리툴바