Intro
스택과 큐 문제를 다시 풀어보면서 템플릿처럼 요약을 했다.
문제 링크 : https://school.programmers.co.kr/learn/courses/30/parts/12081
🔆다리를 지나는 트럭
반복문으로 향상 for문 + 내부 while문을 돌려야 하는데 이 구조를 떠올리지 못했다.
- 주어진 입력값의 길이보다 반복의 길이가 더 길다고 생각하면 while문과 break할 조건을 떠올린다.
- 큐/스택이 특정 요소마다 비우고 채우기를 반복해야 한다면 요소를 위한 for와 큐/스택을 위한 while을 같이 써야 한다.
길이 유지를 위해 아무 값(0)으로 채워야 할 때도 있다.
트럭은 주어진 다리의 길이만큼 이동해야 하며, 1칸씩 이동할 때마다 time이 증가한다.
다리의 길이가 2라면 결과적으로 2초의 시간으로 다리를 건넌 셈이다.
이를 위해서 다리의 길이 유지를 위해 트럭이 올라갈 수 없을 때는 0값을 큐에 대신 추가하고 time을 증가시켰다.
🔆올바른 괄호
스택의 가장 기본 문제다. 스택에 앞서서 기초적인 문자열 분해부터 외운다.
String에서 각 문자에 접근하는 방법
- 첫번째로 캐릭터 배열로 변환해서 향상된 for문으로 출력할 수 있다.
String s = "abcde";
for(char c : s.toCharArray()) {}- 두번째로
charAt()메서드를 사용해서 일반 for문으로 출력할 수 있다.
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
}문자열의 각 문자는 character라서 자연스레 스택의 타입이 된다.
풀이
stack 내 값과 비교할 때는 .peek()를 사용한다. (과 )가 만날 때 stack에서 (를 제거하면 된다.
최종적으로 !stack.isEmpty() 여부가 정답이 된다.
다 넣고 시작하는가? 진행하면서 넣는가?
어떤 문제들은 다 요소들을 넣고 (초기화 작업) 문제를 풀고, 다른 문제들은 반복문을 돌리면서 요소들을 비교를 통해서 넣거나 뺀다. 다 넣고 시작하는 지 판단해보고 코딩을 해야 한다.
🔆 프로세스
3시간에 걸쳐서 겨우 풀어낸 문제다. 필요한 자료구조가 큐라는 것은 알았지만 우선순위로 정렬하면 기존 작업의 인덱스 위치를 알 수 없기 때문에 어떻게 초기의 작업의 인덱스 위치를 저장할 것이냐를 고민했던 문제다.
생각보다 복잡한 자료구조가 아니야!
처음에 정렬을 위해서 Comparator도 데려오고, 큐에 저장할 때 객체 형태로 저장하기도 했다.
하지만 같은 순위의 프로세스들의 우선순위가 인덱스 순서가 아니기 때문에 옳지 않다.
결과적으로 큐를 객체 레벨로 저장할 것이 아니라
- 우선순위 내림차순 정렬을 위한 우선순위 큐 1개
- 인덱스 순서를 위한 인덱스 큐 1개
- 우선순위 자체를 위한 작업숫자 큐 1개
큐 3개로 문제를 해결할 수 있다. 복잡하게 갈 바에 큐의 개수를 늘리는 방법을 먼저 고려한다.
가장 쉬운 정렬
우선순위 큐는 가장 쉬운 정렬용 자료구조다.
- 원시값이라면 우선순위 큐에 담는 것만으로도 오름차순 정렬할 수 있다.
- 원시값이라면 우선순위 큐에
Collections.reverseOrder()를 통해 내림차순 정렬할 수 있다.
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());만약 객체를 정렬하고 싶다면 이후는 Comparator를 도입한다.
