알고리즘/백준
[알고리즘]백준 1863: 스카이라인 쉬운거
stonesy
2024. 8. 16. 08:21
728x90

해결방법
스택을 이용하여 문제를 O(N)의 시간 복잡도로 해결할 수 있다.
핵심은 스택에 자신보다 작은 높이만 유지해야 한다.
- 현재 높이를 스택의 peek() 값과 비교하여, 만약 peek() 값이 현재 높이보다 크다면, 스택에서 해당 값을 pop() 한다. 이때 pop()할 때마다 정답을 증가시킨다.
- 스택에 값을 넣을 때는 다음 조건을 확인한다.
- 현재 높이가 0이 아닌 경우
- 스택의 peek() 값이 현재 높이와 다른 경우
코드
import java.util.*;
import java.io.*;
// 216ms, 스택, O(N)
public class Main_1863_G4_스카이라인쉬운거_스택 {
public static void main(String[] args) throws IOException{
// 1. 입력 및 초기화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int answer = 0;
Stack<Integer> stack = new Stack();
// 2. Stack
for(int i=0; i<N; i++){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
// 스택에는 나보다 큰 것들이 들어있으면 안됨
while(!stack.isEmpty() && (int)stack.peek()>y){
stack.pop();
answer++;
}
// 높이가 0이면 무조건 건물은 없음
if(y==0) continue;
// 동일 높이이면 넣을 필요 없음
if(!stack.isEmpty() && stack.peek()==y) continue;
stack.add(y);
}
while(!stack.isEmpty()){
stack.pop();
answer++;
}
// 3. 출력
System.out.println(answer);
}
}
링크
728x90