[백준/JAVA] 1863 - 스카이라인 쉬운거
문제 정보
https://www.acmicpc.net/problem/1863
문제
문제 해결 과정
1. 문제 조건의 x좌표 범위와 y좌표 범위
1 ≤ 고도가 바뀌는 x좌표 ≤ 1,000,000. 0 ≤ 고도가 바뀌는 y좌표 ≤ 500,000
만약 좌표를 byte 2차원 배열로 만들어 기록하게 된다면, 공간복잡도 = 1,000,000*500,000*1B = 500GB이므로, 메모리 제한인 128MB를 초과하게 된다. 따라서 2차원 배열로 저장하는 것은 불가능하다고 생각하였다.
사실상 중요한 것은 x좌표가 아닌 높이인 y좌표 이므로, 이것만 저장하자고 생각하였다.
2. 아이디어
같은 높이들끼리는 최대한 이어 건물을 만드는 것이 건물의 개수를 최소로 하기 위한 방법이라고 생각하였다.
예를 들어, 1, 2, 1, 3, 1로 고도의 y좌표가 변한다고 했을 때
1을 모두 이은 건물 1개 + 2를 모두 이은 건물 1개 + 3을 모두 이은 건물 1개 = 3개
2-1) 첫번째 방법 (X)
"바뀐 높이가 0이거나 마지막 바뀐 고도가 주어졌을 때, 그 전까지의 같은 높이들끼리 이어 건물을 만들면 최소일 것이다."
하지만, 고도가 바뀌는 지점의 y좌표가 아래와 같이 주어졌을 때 반례가 존재하였다.
1, 2, 3, 1, 2, 0 ≠ 3개
앞의 2와 뒤의 2 사이에 더 낮은 높이인 1이 있어서 이을 수 없었다.
(만약 이을 수 있었다면 스카이라인이 최소 2이기 때문에, 1이 나올 수 없음!!)
2-2) 두번째 방법 (O)
"현재 바뀐 높이가 최근(직전)의 바뀐 높이보다 낮다면, 그 전까지 현재 바뀐 높이보다 높은 건물들을 같은 높이끼리 이어 건물을 만들면 최소일 것이다."
"최근(직전)"이라는 단서에서 자료구조로 스택을 사용하지 않을까?하는 생각이 들었고, pop 연산과 peek 연산을 할 때에 스택이 비어있는지를 확인하는 것을 주의해야겠다고 생각하였다. 또한 스택에 같은 높이는 1번만 들어갈 수 있도록(건물들 이을 것임) boolean[ ] visited를 이용해야겠다고 생각하였다.
바뀌는 고도를 입력받으며 아래의 ⅰ)과 ⅱ)와 같이 비교하는 작업을 하였다.
ⅰ) 현재 바뀐 높이 ≥ 최근(직전)의 바뀐 높이
'스택에서 peek한 높이가 더 낮고, 스택에 현재 바뀐 높이가 없다면, 현재 바뀐 높이를 스택에 push하고 visited[현재 바뀐 높이] = true
ⅱ) 현재 바뀐 높이 < 최근(직전)의 바뀐 높이 ⇒ 그 전까지 현재 바뀐 높이보다 높은 건물들을 같은 높이끼리 이음
'스택에서 peek한 높이가 더 높다면, pop하고(건물 개수 증가) visited[스택에서 pop한 높이] = false'를 반복
모든 고도가 바뀌는 지점을 입력받은 후, 스택이 빌때까지 pop하는(건물 개수 증가) 작업을 하였다.
3. 시간복잡도 계산
바뀌는 고도를 입력받을때마다, ⅱ)에서 반복이 일어난 횟수가 시간복잡도를 결정하는 요소라고 생각하였다.
반복문 안에 스택 연산이 있는 것처럼 보일 수 있지만, 중요한 것은 스택 연산(특히 pop)의 총 수행 횟수라고 생각하였다.
각 고도 변화 지점마다 스택 연산이 수행되지만, 최악의 경우 바뀌는 모든 고도가 정확히 한 번 삽입(push)되고 한 번 제거(pop)된므로, 최대 n번 연산이 수행된다. 즉, 시간복잡도는 O(n) = O(50,000)이므로 시간 제한 2초 이내에 충분하다.
코드
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()); // 고도가 바뀌는 지점의 수
int cnt = 0; // 최소 건물의 수
boolean[] exist = new boolean[500001]; // 해당 높이의 건물 존재 여부
exist[0] = true; // 0이란 높이의 건물은 존재할 수 없음
Stack<Integer> stack = new Stack<>();
// 고도가 바뀌는 지점의 좌표 입력 받음
for(int i=0; i<n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
st.nextToken(); // 바뀐 고도의 x좌표
int cury = Integer.parseInt(st.nextToken()); // 바뀐 고도의 y좌표
// 스택이 비어있고, 건물이 존재하는(바뀐 고도 0이 아닌) 경우
if(stack.isEmpty() && cury != 0) {
stack.push(cury);
exist[cury] = true;
continue;
}
// 스택이 비어있지 않은 경우
while(!stack.isEmpty()) {
// 현재 바뀐 높이 >= 최근의 바뀐 높이
if(cury >= stack.peek()) {
break;
}
// 현재 바뀐 높이 < 최근의 바뀐 높이
cnt++; // 건물 개수 증가
exist[stack.pop()] = false; // 해당 높이의 건물 존재하지 않음 처리
}
// 스택에 현재 바뀐 높이가 없다면 push하고, 해당 높이의 건물 존재 처리
if(!exist[cury]) {
stack.push(cury);
exist[cury] = true;
}
}
while(!stack.isEmpty()) {
stack.pop();
cnt++; // 건물 개수 증가
}
System.out.println(cnt);
}
}