📝 알고리즘/자료구조

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

문제 https://leetcode.com/problems/add-two-numbers-ii/description/ 주어진 두개의 비어있지 않은 linked list는 각각 음수가 아닌 정수로 이루어져있다. 가장 중요한 숫자가 첫번째로 오며, 그들의 노드 각각은 한자리 수를 포함한다. 두 숫자를 더한 합을 linked list 형태로 반환하라. 두 숫자는 0일 경우를 제외하고, 앞자리가 0으로 나타나지 않는다. 풀이 Stack을 사용한 풀이 public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { ArrayDeque st1 = new ArrayDeque(); ArrayDeque st2 = new ArrayDeque(); while (l1 != n..

문제 SWEA(SW Expert Academy) 1223번 계산기2 [D4] 풀이 스택을 이용하여 후위표기식을 작성/계산하는 문제 후위표기식 변환 만약 숫자일 경우, 바로 출력(여기에는 후위표기식 문자열carr에 저장)하고 연산자일 경우, 우선순위에 따라 스택에 pop/push. 스택에서 자신보다 낮은 우선순위 연산자가 나올 때까지 계속 pop하여 출력한다. 즉, 자신보다 높거나 같은 우선순위 연산자를 모두 pop 현재 문제에서는 +, *밖에 없으므로 +는 스택에 있는 모든 연산자를 출력하고, *는 peek()값이 *일 때 출력한다. 우선순위에 따른 연산자 출력 후, 자기 자신을 push 후위표기식 계산 문자열배열(carr)을 순회하며 숫자일 경우 stack에(이전과 다른 스택 사용) push하고 연산자..