BOJ 1863 : 스카이라인 쉬운거

 

https://www.acmicpc.net/problem/1863

🚩문제

 

🔒문제해결(오답)

전혀 쉽지않았는데.....왜 쉬운거일까 .....................쉽지않은 문제였다고 한다...

풀고나니 막대기 문제와 비슷한 결인데 좀 더 좀더 어려운 느낌??

 

1.왼쪽부터 고도가 바뀌는 지점의 좌표가 입력되므로 x값이 중복되는 경우가 없음

2.리스트에 y값만 저장하여 카운트 ++

3.첫번째 입력받은 y의 최솟값과 최댓값으로 지정

4.for문을 돌며 최솟값이 같거나 최댓값이 바뀌게 될 경우 +1씩

(최솟값이 같으면 :같은높이건물, 최댓값이 바뀌면 : 다른높이 건물)

5.y의 값이 0을 만나면 최소,최댓값을 초기화해줌

예제를 돌렸을때 정답이 나와서 접근법이 맞는줄 알았다고 한다 ㅇㅅㅇ 하지만 제출하고서 7%?에서 바로 오답

중간에 계속 수식을 바꿔봤지만 틀림연속이여서 알고리즘 분류를 봤더니 스택으로 풀면되는 문제였다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> list = new ArrayList<>();
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] str = br.readLine().split(" ");
            list.add(Integer.parseInt(str[1]));
        }
        int min = list.get(0);
        int max = list.get(0);
        int cnt = 0;
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i)>max) { //최고높이건물
                max = list.get(i);
                cnt++;
            }else if (list.get(i)==0) { 
                min =0;
                max=0;
            }else if (min==0 && min<list.get(i)) {  //0바로 다음 건물
                min=list.get(i);
                max=list.get(i);
            } else if (min==list.get(i)) { //같은 높이건물
                cnt++;
            }
        }
        System.out.println(cnt);


    }

}

 

🔓문제해결(정답)  - Stack

스택은 LIFO 이므로 바로 직전건물의 높이를 알 수 있다.

1.스택이 비어있다면 값을 무조건 저장해준다.

2.이전 값과 입력값을 비교한다.

3. 입력한 값이 크면 스택에 무조건 저장해준다.

4.입력한 값이 작으면 스택에서 값을 꺼내야한다.

   4-1 이전에 저장된 모든 값들과 비교하여 스택이 비거나 기존값보다 작을때까지 무한 반복을 한다.

   4-2  기존값보다 입력값이 작으면 건물수++,해당건물의 높이를 제외시킨다.

5.해당 while문을 탈출하고 나서도 입력한값이 기존값보다 크면 저장해줘야함!!

(이부분때문에 중간부분에서 계속 틀렸습니댜..)

 

만약 y가 0이거나 입력한 값과 높이가 같다면 저장하지않는다.

 

y가 0이라면 그 위치에 건물이 없다는것이니까 앞 뒤 건물이 따로 존재함을 알 수있다.

그래서 y가 0일때 스택이 비어있지않다면 이전에 건물이 계산되지 않은것이기때문에 스택의 크기를 결과값에 저장하고

스택을 비워준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
* 입력
입력 n
x좌표 y좌표
*
* 출력
경험치합의 최댓값
* */

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Integer> stack = new Stack<>();
        int n = Integer.parseInt(br.readLine());
        int cnt =0;
        for (int i = 0; i < n; i++) {
            String[] str = br.readLine().split(" ");
            int y = Integer.parseInt(str[1]);
            if(y==0){ //0이라면 ,다음값을 받음
                if(!stack.isEmpty()){
                    cnt+=stack.size(); //기존값 저장하고 비워줌
                    stack.clear();
                    continue;
                }
                continue;
            }
            if (!stack.isEmpty() && stack.peek()>y){ //기존값보다 크거나 같으면
                 while(!stack.isEmpty() && stack.peek()>y){ //스택이 비거나 기존값보다 작을때까지 반복
                cnt++;
                stack.pop();
                 }
            }
            if(stack.isEmpty() || (!stack.isEmpty() &&stack.peek()<y)){ //스택이 비어있거나 기존값보다 크면 스택에 저장
                stack.push(y);
            }

        }
        if(!stack.isEmpty()){
            cnt+=stack.size();
        }
        System.out.println(cnt);

    }

}