오늘의 학습 키워드 및 문제
#스택 #Stack #ArrayDeque
백준 브론즈2) 막대기
문제풀이
처음에
입력받은 m을 push 하기 전, 비어있는지 확인하고
비어있다면 push
비어있지 않다면 현재 stack의 size 반복문으로 top과 m을 비교하여 남은 stack의 수를 출력하려고 했다.
top <= m 이면 pop(), push(m), break
top > m 이면 push(m), break
그런데 해당 풀이 방식은 아래의 테스트 케이스에는 어긋난다.
(아래) 9 4 3 6 5 (위) => (아래) 9 4 6 5 (위)
9 : push
4 : push
3 : push
6 : 3 pop, 6 push
5 : push
그런데 계속 보다보니..
stack은 top의 값과 top 아래의 값을 1:1로 비교하는 횟수가 n-1번이라는 것을 찾아냈다❗
예)
(아래) 6 4 6 7 9 6 (위)
1. 6 과 9 비교 => pop()
2. 9 와 7 비교 => pop()
3. 7 과 6 비교 => pop()
4. 6 과 4 비교 => pop()
5. 4 와 6 비교 => pop()
그렇다면
값들을 모두 stack에 push한 후 n-1번 반복하여 가장 큰 값과 비교를 하면 되겠구나 생각했다.
여기서 가장 큰 값은 비교한 값들 중 가장 높은 값을 의미한다.
예)
(아래) 9 4 3 6 5 (위)
가장 오른쪽(top) 값을 꺼내어 해당 값을 pop이라고 하자.
pop과 stack의 top을 비교했을 때,
pop < stack.peek() 라면 +1, stack.peek()가 pop이 된다.
pop >= stack.peek() 라면 그냥 stack을 pop한다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ArrayDeque<Integer> stack = new ArrayDeque<>();
for(int i=0; i<n; i++) {
int m = Integer.parseInt(br.readLine());
stack.push(m);
}
int pop = stack.pop();
int cnt = 0;
for(int i=0; i<n-1; i++) {
if (pop < stack.peek()) {
cnt++;
pop = stack.pop();
} else if (pop >= stack.peek()) {
stack.pop();
}
}
// 맨 오른쪽 막대기 포함 (+1)
System.out.println(cnt+1);
br.close();
}
}다른방법
- pop 할 때 while 반복문 사용
위에서 처음에 시도했던 방법이 특정 테스트 케이스에서 원하는 값이 나오지 않아 다른 방법으로 풀었었다.
하지만 while 반복문을 사용하여 구현할 수 있었다.
(아래) 9 4 3 6 5 (위) => (아래) 9 6 5 (위)
9 : push
4 : push
3 : push
6 : while 조건 해당, 3 pop, 4 pop, 6 push
5 : push
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
ArrayDeque<Integer> stack = new ArrayDeque<>();
for (int i=0; i<n; i++) {
int height = Integer.parseInt(br.readLine());
// 스택이 비어있지 않고 현재 막대기의 높이가 스택의 맨 위 막대기보다 크다면
while (!stack.isEmpty() && height >= stack.peek()) {
stack.pop(); // 스택에서 맨 위의 막대기 제거
}
stack.push(height); // 현재 막대기를 스택에 추가
}
System.out.println(stack.size()); // 스택에 남아있는 막대기는 보이는 막대기들
br.close();
}
}공부한 내용정리
- stack은 top의 값과 top 아래의 값을 1:1로 비교하는 횟수가 n-1번이다.
- while 반복문으로 pop하면 top의 값이 계속 변한다.
