본문 바로가기

Algorithm

(66)

2504 : 괄호의 값 ( 백준 / java ) *해결 과정 괄호를 가지고 계산하는 것은 보통 stack을 이용하면 됩니다. 이 문제도 마찬가지로 stack을 이용합니다. 이전의 stack문제와 다른 것은, '(' 에 대한 ')'의 위치 index를 저장하고 재귀적으로 해결했지만 이번에는 그런 방식으로 하면 시간초과가 난다는 것입니다. 그래서 문자열을 하나씩 탐색하면서 Nlog(N)에 해결하도록 하였습니다. (N은 문자열 길이이고, 문자열을 하나씩 살펴보며 검사하지만 괄호 안에 다른 내용이 있을 경우 다시 while문 으로 모두 stack.pop()하는 과정이 있으므로 최악의 경우 N을 곱했습니다.) 특히 '('는 0으로 치환, '['은 1로 치환하여 stack에 저장하였으며 어차피 계산과정에서 0과 1을 만날 일이 없기 때문에 괄호라고 식별 가능합니..

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...

543 : Diameter of Binary Tree ( leetcode / java ) *해결 과정 리스트에서야 지름 구하는 것을 풀었지 tree에서 지름구하는 문제는 처음입니다. 처음에 root에서 왼쪽 자식의 맨 아래 자손 깊이, 오른쪽 자식의 맨 아래 자손의 깊이를 더해서 출력했는데 틀렸씁니다. 왜냐하면 꼭 루트에서 이어진 길이가 지름이라는 법이 없기 때문입니다. 그래서 각 노드를 모두 root라고 생각하고 순회하면서 비교해야 합니다. 리스트, 트리의 지름 = 가장 멀리 떨어져 있는 두 노드의 거리 빨간점을 기준으로 생각해봅시다. 해당 노드에서 지름은 어떻게 구할까요? 다음 2가지를 생각해 보시길 바랍니다. 1. 어떻게 해당 노드에서 지름의 길이를 구할 것인가 ( 종료 조건, 재귀로 계산하는 과정, return) 1-1. 무엇을 return 할 것인가? ( 최대 결과값을 반환 할 것인..

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 ..

235 : Lowest Common Ancestor of a Binary Search Tree ( leetcode / java ) * 해결과정 제목에 이진탐색 트리라고 써있습니다. 이를 적극적으로 활용합니다! (하지만 저는 또 그냥 지나쳤습니다.. ㅜㅜ) 또한 최소 공통 조상에 대한 문제이기도 합니다. 하지만 걱정하지 않아도 되는 것은 이진탐색 트리이기 때문에, 또한 p,q가 동시에 주어졌기 때문에 간단하게 해결 할 수 있습니다. 각 해당 노드의 값의 대소비교를 통해 해결합니다. class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { int parentVal = root.val; int pVal = p.val; int qVal = q.val; if(pVal>parentVal && qVal>parentVal) return..

993 : Cousins in Binary Tree ( leetcode / java ) *해결과정 우리가 필요한 것은 depth(깊이), parent(부모)이다. 새로운 배열을 만들어서 DFS순회를 돌면서 depth와 parent를 갱신하면 된다. 굳이 새로운 class를 만들 것 없이 매개변수로 전달하면 된다. class Solution { int xDepth=0; int yDepth=0; int xParent = 0; int yParent = 0; public boolean isCousins(TreeNode root, int x, int y) { DFS(root,x,y,0,-1); return (xDepth==yDepth) && (xParent!=yParent); } public void DFS(TreeNode root, int x, int y, int depth,int parent){..

1662 : 압축 ( 백준 / java ) * 해결 과정 이 문제는 압축이 문자열 길이라는 것에 주의해야 하며, 대부분의 문자열을 다루는 것은 stack을 통해서 해결해야 합니다. 더불어 재귀를 이용하여 괄호를 처리하는 스킬을 배울 수 있습니다. public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); line = sc.next(); Stack stack = new Stack(); reverse = new int[50]; for(int i=0;i

16926 배열돌리기1, 16927 배열돌리기2 ( 백준 / java ) www.acmicpc.net/problem/16921 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← ..

이전 1 2 3 4 5 6 7 8 9 다음

티스토리툴바