[262가지 문제로 정복하는 코딩 인터뷰 간단요약] 8장 스택과 큐

 - Java에서 스택과 큐를 표현하는 좋은 방법은 Deque 인터페이스 사용하는 것
- 스택은 후입선출법, 큐는 선입선출법 따름

 

Deque(덱)이란?
양방향 큐(double-ended queue)라고도 부르며 모든 삽입 삭제가 리스트의 양 끝, 둘중 하나에서 일어나는 이중 연결리스트

이는 스택으로 사용할수도 있고 큐로 사용할 수도 있다.

 

스택 라이브러리 이해하기

메서드	설명	특징
push()	원소 집어넣기	- 용량에 한계는 없지만 구현에 따라 예외 던질 수 있다. - null 삽입 가능하지만 매우 조심해야 한다.
peek()	원소 삭제하지 않고 스택의 위에 있는 원소 반환하기	- 빈 스택은 null 반환 - null이 유효한 원소일 수도 있으므로 isEmpty() 사용
pop()	스택에서 원소 삭제하고 그 원소 반환하기	- 빈 덱 호출시 예외 발생 (이를 피하려면 isEmpty()로 확인하는 것이 좋다.)

 

8.1 최댓값 찾는 API로 스택 구현하기

push와 pop외에 max 연산을 제공하는 스택 클래스를 설계하라
(max()는 스택에 저장된 원소 중 가장 값이 큰 원소 반환)

힌트 : 최댓값 기억용 공간 추가 사용

- 간단하게 스택을 배열로 구현했다면, 배열 순회하며 가장 큰 값 찾으면 됨(시간복잡도 O(n), 공간복잡도 O(1))

- 힙, BST, 해시테이블과 같은 추가 자료구조 사용시 시간복잡도 O(log n) 감소가능, 공간복잡도 O(n)으로 늘어나고 코드 복잡

- 공간 사용하여 스택의 모든 원소에 대해 최댓값 캐싱(시간복잡도 O(1), 공간복잡도 O(n))

각 최댓값이 몇번 등장했는지 기록하면 중복 제거할 수 있음(최악 공간복잡도 O(n)/ 최고 공간복잡도 O(1)), 시간복잡도는 O(1)

 

8.2 RPN 수식 계산하기

RPN : 역 폴란드법 표기법

1) 길이가 1이상인 숫자로 이루어진 문자열('-'로 시작하는 경우 있음) => "6", "123", "-42"

2) A와 B가 RPN 수식 만족하고 O가 +,-,x, / 중 하나일 때 "A, B, O"의 형태로 작성된 문자열 

수식 주어졌을 때 결과를 반환하라

- 스택에 담다가 연산자 마주치면 수식 계산하기 (시간복잡도 O(n))

 

8.3 문자열이 올바른 형태인지 확인하기

서로 다른 괄호 종류가 올바른 순서로 짝 이룰 때 문자열을 '올바른 형태' 라고 함
'(',  ')',  '[',  ']',  '{',  '}' 로 이루어진 문자열이 올바른 형태인지 확인하기

힌트 : 어떤 괄호와 어떤 오른쪾 괄호가 짝 이루는지?

- 여는 괄호는 더하기 / 아니라면 찍이 맞는지? / 맞으면 제거하기 / 한바퀴 돌려서 스택이 비어 있는지 확인하기 (시간복잡도 O(n))

 

8.4 경로 이름 표준화하기

절대경로 : 루트에서 시작 / 상대경로 : 현재 디렉터리에서 시작

문자열 경로 이름 주어졌을 때 같은 경로 나타내는 가장 짧은 경로 반환하기
(알파벳과 숫자로 이루어져 있으며 하위 디렉터리 이름은 슬래시(/), 현재 디렉턱리(.), 부모 디렉터리(..)의 조합으로 나타냄)

힌트 : 각각 경우의 수 생각하기. 유효하지 않은 경로 조심

- 슬래시일 경우 / 현재디렉터리일 경우 / 부모디렉터리일 경우로 나누어 이벤트 발생시키기(시간복잡도 O(n))

 

8.5 노을이 보이는 건물 찾기

서쪽에서 동쪽방향으로 건물이 직선 배치되어 있는데, 높이가 같거나 낮은 건물이 동쪽에 있다면 그 건물에서 노을을 볼 수 없다.
동쪽에서 서쪽으로 차례대로 건물 처리한다고 했을 때 노을을 볼 수 있는 건물의 집합 반환하기

힌트 : 건물에서 노을을 볼 수 없는 것은 언제?

- 무식하게 배열 저장 후 거꾸로 읽으면서 높이 기록하고 높이보다 낮거나 같은 건물 볼 수 없다고 체크(시간 및 공간복잡도 O(n))

- 노을 볼 수 있는 건물들을 스택에 저장하기

=> 건물 처리할 때마다 건물보다 높은 건물 나올때까지 스택에서 건물을 제외한다.

---

큐 라이브러리 이해하기

 

 

8.6 깊이 순서대로 이진 트리의 노드 구하기

이진트리가 주어졌을 때 같은 높이(depth)의 키 값들을 배열로 반환하라
(키값은 노드의 깊이 순서대로 나타나야 하며, 높이가 같은 경우에는 왼쪽에서 오른쪽 순서대로 나타나야 함)

- 무식하게 노드와 그 깊이를 배열에 함께 기록하는 방법

- 큐 두 개 사용해서 푸는 방법

=> 깊이가 i인 노드를 저장하는 큐와 깊이가 i+1인 노드 저장하는 큐 사용하여  전자를 처리하면서 다음 노드들을 새로운 큐에 담는다.

(시간복잡도 O(n), 공간복잡도 O(n))

 

8.7 환형 큐 구현하기

배열의 끝과 시작이 붙어 있는 환형 큐는 배열과 두 개의 변수로 구현할 수 있다.
배열을 사용하여 환형 큐 API 구현하라

- 무식하게 배열 헤드 가리키는 변수는 언제나 0번 인덱스 가리키도록 하고 또 다른 변수 통해 테일 원소가 무엇인지 추적하는 방법

(enqueue는 시간복잡도가 O(1)이지만 dequeue는 O(n)소요됨 => 원소 뺄때마다 시프트해야 하기 때문)

- 위 방법에 헤드 추적용 변수 하나 더 추가하는 방법(dequeue 도 O(1))

 

8.8 스택 사용하여 큐 구현하기

스택라이브러리 이용하여 큐 구현하라

- 스택 두 개를 서로 이동하며 삽입, 삭제 구현 (시간복잡도 O(n))

- 스택 두 개를 각각 enqueue용, dequeue용으로 나누어 사용(m = 연산갯수, 시간복잡도 O(m))

 

8.9 최댓값 API로 큐 구현하기

enqueue, dequeue, max 연산 제공하는 큐 구현하기

- 무식하게 최댓값과 비교하여 계속 갱신하는 방법(시간복잡도 O(n))

- 스택 두 개를 사용해서 구하기(8.8 사용)