leetcode

문제 https://leetcode.com/problems/implement-stack-using-queues/description/ 오직 두개의 queue만을 사용하여 후입선출(LIFO)의 stack을 구현하여라. 구현된 스택은 기본 스택의 함수(push, top, pop, empty)들을 지원하여야 한다. MyStack 클래스를 구현하여라. void push(int x): 스택의 끝에 x를 넣는다. int pop(): 스택의 끝 값을 지우고, 이를 반환한다. int top(): 스택의 끝 값을 반환한다. boolean empty(): 스택이 비어있으면 true를 반환하고, 아니라면 false를 반환한다. 주의 오직 큐의 표준 operation만을 사용하여라. 이는 큐의 끝에서 요소를 추가하는 push..

문제 https://leetcode.com/problems/frog-jump/description/ 개구리는 강을 건넌다. 강은 몇개의 unit으로 나뉘어져있고, 그곳에는 돌이 있을 수도 있고 없을수도 있다. 개구리는 돌 위에서 점프할 수 있으며 물로 뛰어들어선 안된다. 오름차순으로 정렬된 stones(돌)의 위치 리스트가 주어졌을 때, 개구리가 마지막 돌에 착륙하며 강을 건널 수 있는지 판별하라. 처음 개구리는 첫번째 돌 위에 서 있으며, 첫번째 점프는 1 unit만큼이다. 만약 개구리의 마지막 jump가 k unit만큼이었다면, 다음 점프는 k-1, k 또는 k+1 unit만큼이어야 한다. 개구리는 오직 앞으로만 갈 수 있다. 풀이 public class LeetCode_403_FrogJump { H..

문제 https://leetcode.com/problems/unique-binary-search-trees-ii/ 주어진 n에 대해, 모든 구조적으로 유일한 BST(이진 검색 트리)를 반환하라. BST는 1부터 n까지 고유한 값을 갖는 n개의 노드로 구성된다. 답을 반환하는데에 순서는 무관하다. 풀이 DP와 메모이제이션을 이용 - 가장 작은 트리노드부터 만들어 이를 기록해두고, 계속해서 해당 memo를 사용하는 방식 시간 복잡도: O(n^2), 공간 복잡도: O(n^2) 1. JAVA public class LeetCode_95_UniqueBinarySearchTrees2 { public static class TreeNode { int val; TreeNode left; TreeNode right; T..

문제 https://leetcode.com/problems/asteroid-collision/ 주어진 `asteroids` 배열은 연속한 소행성(asteroid)을 나타내는 정수로 이루어져있다. 각 소행성의 절대값은 이것의 사이즈를 나타내고, 부호는 방향을 나타낸다(+는 오른쪽, -는 왼쪽). 소행성들은 같은 속도로 움직인다. 모든 충돌이 끝난 후의 소행성의 상태를 반환하라. 만약 두 소행성이 만난다면, 더 작은 것이 폭발한다. 만약 두 소행성이 같은 크기라면, 모두 폭발한다. 같은 방향으로 움직이는 두 소행성은 절대 만나지 않는다. 풀이 class Solution { public int[] asteroidCollision(int[] asteroids) { ArrayDeque st = new ArrayD..