본문 바로가기

Java/알고리즘

 (47)
[자바 알고리즘 인터뷰] ch 10. 데크, 우선순위 큐 (3) - 원점에서 가장 가까운 k개의 점 https://leetcode.com/problems/k-closest-points-to-origin/description/  - 평면상에 points 목록이 있을 때, 원점(0,0)에서 가장 가까운 k개의 점 목록을 순서대로 출력하라. 평면상에 있는 두 점의 거리는 유클리드 거리(Euclidean Distance)로 한다.   풀이 1) 유클리드 거리의 우선순위 큐 순서  - 유클리드 거리는 두 점의 직선 거리를 의미한다. - 유클리드 거리를 계산하고 이 값을 우선순위 큐로 k번 출력하면 쉽게 문제를 풀 수 있다.    - 위의 유클리드 거리를 계산하고 이 값을 우선순위 큐에 삽입하는 코드는 다음과 같다. //Point 클래스를 저장하는 우선순위 큐로, 정렬 기준은 distance로 한다. Priori..
[자바 알고리즘 인터뷰] 10장 데크, 우선순위 큐 (2) k개 정렬 리스트 병합 https://leetcode.com/problems/merge-k-sorted-lists/zm - k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라   풀이 1) 우선순위 큐를 이용한 리스트 병합  우선순위 큐  - 어떠한 특정 조건에 따라 우선순위가 가장 높은 엘리먼트가 먼저 추출되는 자료형 - 이 문제의 예제 입력값은 [[1,4,5],[1,3,4],[2,7]] 이며, 먼저 다음과 같이 반복문으로 각 연결 리스트의 첫 번째 노드를 큐에 저장한다. //각 연결 리스트의 첫 번째 노드를 큐에 저장for(ListNode node : lists){ if(node!=null) pq.add(node);} - 이렇게 하면 큐에는 각 연결 리스트의 루트인 1,1,2가 저장된다. - 그렇다면 ..
[자바 알고리즘 인터뷰] 10장 데크, 우선순위 큐 (1) 원형 데크 디자인 데크- Double-Ended-Queue의 줄임말로, 글자 그대로 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)이다. - 양쪽에서 삽입과 삭제를 모두 처리할 수 있으며, 스택과 큐의 특징을 모두 갖고 있다. - 이중 연결 리스트(Doubly Linked List)로 구현   - 양쪽으로 head와 tail이라는 이름의 두 포인터를 갖고 있다가 새로운 아이템이 추가될 때마다 앞쪽 또는 뒤쪽으로 연결해주기만 하면 된다.  - 자바에서 데크를 구현하는 Deque 자료형은 Queue와 마찬가지로 인터페이스이며, Queue를 확장해 정의되어 있다 ,- 실제 구현은 LinkedList 또는 ArrayDeque로 할 수 있다.  //데크 선언Deque deque = new LinkedL..
[자바 알고리즘 인터뷰] 9장 스택,큐 (6) 원형 큐 디자인 https://leetcode.com/problems/design-circular-queue/description/    - 원형 큐를 디자인하라, 큐가 비어 있다면 -1을 리턴하며, 해당 원형 큐의 사용 예는 다음과 같다.   풀이 1) 배열을 이용한 풀이  - 원형큐(Circular Queue)는 FIFO 구조를 지닌다는 점에서 기존 큐와 동일하다. - 그러나 마지막 위치가 시작 위치와 연결되는 원형 구조를 띠기 때문에, 링 버퍼(Ring Buffer)라고 부른다.   - 기존의 큐는 공간이 꽉 차면 더 이상 엘리먼트를 추가할 수 없다. - 심지어 앞쪽에 엘리먼트들이 deQueue()로 모두 빠져서 충분한 공간이 남게 돼도 그 쪽으로는 추가할 수 있는 방법이 없다.  - 그러나 원형 큐는 앞쪽에 공간..
[자바 알고리즘 인터뷰] 9장 큐,스택 (5) 스택을 이용한 큐 구현 https://leetcode.com/problems/implement-queue-using-stacks/ - 스택을 이용해 다음 연산을 지원하는 큐를 구현하라.  push(x) : 엘리먼트 x를 큐 마지막에 삽입한다. pop() : 큐 처음에 있는 엘리먼트를 제거한다. peek() : 큐 처음에 있는 엘리먼트를 조회한다. empty() : 큐가 비어 있는지 여부를 리턴한다.   풀이 1) 스택 2개 사용  - 가장 먼저 삽입된 아이템을 끄집어 내야 하는데, 스택은 아무리 추가, 삭제를 반복해도 가장 가장 마지막에 삽입된 아이템만 넣고 빼기를 반복하므로 하나의 스택만을 이용해서는 풀 수 없다. - 이 문제를 풀기 위해서는  2개의 스택이 필요하다.  - 특히 추출시 pop()과 조회 시 peek()는 결..
[자바 알고리즘 인터뷰] 9장 스택,큐 (4) 큐를 이용한 스택 구현 https://leetcode.com/problems/implement-stack-using-queues/  - 큐를 이용해 다음 연산을 지원하는 스택을 구현하라.  push(x) : 엘리먼트 x를 스택에 삽입한다. pop() : 스택의 첫 번째 엘리먼트를 삭제한다. top() : 스택의 첫 번째 엘리먼트를 가져온다. empty() : 스택이 비어있는지 여부를 리턴한다.   풀이 1) push()할 때 큐를 이용해 재정렬  - 큐를 선언 하고 큐 추상 자료형의 기본 연산으로 구현  - 가장 복잡한 부분은 push()이다. - 엘리먼트를 삽입한 후에 방금 삽입한 엘리먼트를 맨 앞에 두는 상태로 전체를 재정렬하면 나머지는 기본적인 큐 연산으로 쉽게 구현이 가능하다.  class MyStack { //큐..
[자바 알고리즘 인터뷰] 9장 스택, 큐 (3) 일일 온도 https://leetcode.com/problems/daily-temperatures/description/  - 매일의 온도 리스트 temperatures를 입력받아서, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라   풀이 1) 스택 값 비교    - 현재의 인덱스를 계속 스택에 쌓아두다가, 이전보다 상승하는 지점에서 현재 온도와 스택에 쌓아둔 인덱스 지점의 온도 차이를 비교해서, 더 높다면 다음과 같이 스택의 값을 pop()으로 꺼내고, 현재 인덱스와 스택에 쌓아둔 인덱스의 차이를 정답으로 업데이트  - 그리고 현재 인덱스를 다시 스택에 삽입한다.   //현재 온도가 스택에 있는 온도보다 높다면 꺼내서 결과를 업데이트 while(!stack.isEmpty() && temperat..
[자바 알고리즘 인터뷰] 9장 스택,큐(2) - 중복 문자 제거 https://leetcode.com/problems/remove-duplicate-letters/description/   - 중복된 문자를 제외하고 사전식 순서(Lexicographical Order)로 나열하라   풀이 1) 재귀를 이용한 분리  사전식 순서(Lexicographical Order) - 사전에서 가장 먼저 찾을 수 있는 순서 - bcabc에서 중복 문자를 제외하면 사전에서 가장 먼저 찾을 수 있는 문자열은 abc가 된다.  - ebcabc가 입력값이라면 결과는 eabc가 된다.  -> e 문자 자체는 해당 문자열 내에서는 사전에서 가장 뒤에 있지만 e는 입력값에서 딱 한번만 등장하고, a,b,c는 뒤이어 등장하기 때문에 e의 위치를 변경할 수 없기 때문이다.  - ebcabce라면 ..

티스토리툴바