백준 3015번: 오아시스 재결합

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

3015번: 오아시스 재결합

Source Code : https://github.com/JangAJang/Study/blob/main/백준_스택%202/오아시스%20재결합/src/Main.java

개인적으로 스택 문제는 뭔가 사용하기 어려운 감이 있는 것 같다. 스택의 특성상, push&pop으로 제일 마지막의 값만 넣거나 뺄 수 있기 때문이다. 

 

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

이 부분을 통해 두가지를 기본적으로 생각해두었다. 

(기준 : 제일 앞 사람부터 경우의 수를 셀 때)

1. 기본적으로 바로 다음 사람은 볼 수 있다. 

2. 그 다음을 보려면 그 사이에 더 큰 사람이 없어야 한다. 

 

이를 토대로 생각한 것은, 각 사람이 볼 수 있는 사람 수를 카운트 해야겠다는 것이다. 

그냥 총 값을 구하자니 stack이 아닌 배열을 사용해야 할 것 같다는 생각이 들었다. 

public static class Point{
     int height;
     int count;

    public Point(int height, int count){
        this.height = height;
        this.count = count;
    }

    public void addCount(){
        count++;
    }

}

그래서 이런 식으로 클래스를 만들었다. 

Point라는 사람마다 자신의 키와, count라는 볼 수 있는 사람 수의 변수를 두었다. 

또한, ++처럼 써도 되지만, 조금 더 구조를 편하게 보기 위해 addCount라는 함수를 만들어두었다. 

 

문제에서는 키가 2, 4, 1, 2, 2, 5, 1인 사람들이 있다고 했는데, 이에 대해 어떻게 과정이 흘러가는지 생각해보았다. 

기본적으로 첫번째부터 마지막사람까지 확인하며 진행을 한다. 

(1)이미 확인하고 스택에 담은 사람의 키가 다음사람보다 작다면 제거한다. 키가 큰 사람 뒤는 볼 수 없기 때문이다. 

(2)스택의 마지막 사람이 새로운 사람보다 크다면 그 뒤도 볼 수 있다. 기본적으로 2명 이상 볼 수 있다. 

(3)키가 같다면 스택에 남아있는 더 큰 사람들, 그리고 키가 같은 사람 한명은 볼 수 있다. 

 

 

1. 기본적으로 스택에 Point가 있을 때, 스택의 마지막 사람이 새로운 사람보다 작다면, 계속해서 빼준다. 뺀 count는 결과에 더해준다. 

2. 만약 스택이 비어있다면, 해당 사람의 키와 count=1로 새로운 객체를 만들어 스택에 push한다. 

3. 만약 스택이 비어있지 않다면

   3-1 스택의 마지막 사람 > 새로운 사람

           스택의 마지막 사람은 그 다음사람도 볼 수 있다. 그러므로 결과에 1을 더한다. 새로운 사람도 이후를 봐야하기에 스택에 추가시킨다. 

   3-2 스택의 마지막 사람 = 새로운 사람

           키가 같은 두 사람은 서로 볼 수 있다. 둘을 매칭시킨다. 또한, 스택에 Point가 더 있을 경우,

           그 사람은 새로운 사람보다 큰 사람이므로, result++를 해준다. 

for(int i=0; i<n; i++) {
    while(!points.isEmpty() && points.peek().height < arr[i]) {
        result+= points.pop().count;
    }

    if(points.isEmpty()) {
        points.push(new Point(arr[i], 1));
    }else {
        if(points.peek().height > arr[i]) {
            points.push(new Point(arr[i], 1));
            result++;
        } else {
            result += points.peek().count;
            points.peek().addCount();
            if(points.size()>1) {
                result++;
            }
        }
    }
}

 

이렇게 만든 상태에서 입출력만 관리해주면 된다. 

 

생각보다 스택을 쓰는 것은 Array, List, Deque보다 까다로운 것 같다. 추가와 제거가 원할하지 못하다는 점이 있다. 

대신 편하게 만들 수 있는 반복문으로보단 시간복잡도가 덜하다. 

배열을 계속 해서 반복할 경우, 약O(n^2)정도가 나오기 때문이다. 

 

난이도가 올라갈 수록 시간 복잡도를 위한 생각이 많아져야 할 것 같다.