[백준 / BOJ] 3015 오아시스 재결합

문제

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

3015번: 오아시스 재결합

N명의 사람이 한 줄로 기다리고있다.

i번째 사람과 i+a번째 사람이 서로 보기위해선, i ~ i+a사이에 i와 i+a보다 큰 사람이 없어야한다. 

이때, 서로 볼수있는 사람의 쌍을 구하는 문제다.

 

---

풀이

푸는데 시간이 좀 많이 걸린문제다.

처음엔, 세그먼트 트리로 생각했으나, N*N/2 시간이 걸릴것이라 생각하여 포기했다.(문제 질문을 보니 세그먼트로도 풀리는듯하다)

 

알고리즘 설명에있는 스택위주로 생각을해서 풀었다. 

 

몇개의 시뮬레이션을 해보면 일정한, 규칙을 찾을수있다.

아래에서 같이 시뮬레이션을 해보자.

 

문제를 일반화 하기위해, 모든 사람을 키가 [큰사람, 작은사람, 같은사람]이라고 가정했다.

(사람이 2명만 있을때 서로 항상 쌍을 이룬다는것은 항상 참이므로 고려하지않는다.)

 

1) 3명의 사람이 있는경우. A,B,C 3명의 사람이 알파벳 순서대로 서있다. 이때, C가 나머지 사람과 서로 마주볼수있는 조합은 다음 과 같은 경우이다.

 

A : B보다 크거나 같은사람

B : A와 같거나 작은사람

C : B보다 크거나 같은사람

 

C가 B보다 작은사람이거나, A가 B보다 작은사람일경우, 혹은 B가 A,C보다 큰사람일경우 C는 모든 사람을 볼수없다.

 

즉, 3명의 사람이 서 있을때, 양 끝의 사람이 마주볼려면 사람의 키 형태는 항상 다음과 같아야함을 알수있다. [큰(같), 작(같), 큰(같)]

 

2) 4명의 사람이 있는경우. A,B,C,D 4명의 사람이 알파벳 순서대로 서있다. 이때, D가 나머지 사람들과 마주볼수있는 조합은 다음과 같은 경우다.

 

A : 큰사람

B : A보다 작거나 같은사람

C : A,B보다 작거나 같은사람

D : B,C보다 크거나 B,C둘중 큰 키와 같은사람

 

3) 5명의 사람이 있는경우.

이 경우도 2번과 마찬가지로 진행된다.

 

위 규칙을 살펴보면, 새로 추가되는 사람이 나머지 사람을 확인하기 위해서는, 모든 사람이 감소하는 수열꼴을 이뤄야한다는것을 알수있다.

 

즉,  i번째 사람과 i + a 번째 사람 사이에 두 사람보다 더 키가 큰 사람이 있다면, 해당 (키큰)사람 뒤에있는 모든 사람은 절대 (키큰)사람 뒤에 줄서있는사람과 쌍을 이룰수없다.

 

따라서, 입력을 받을때, 현재 스택의 값보다, 더 큰 사람이 추가되면, (추가되는 사람보다 키가 작은사람은 이후에 추가되는사람과 절대 만날수없으니..) 스택에서 빼주며 연산을 진행하면된다.

 

이때, 키가 같은경우를 생각하며 TLE를주의해서 풀어야한다.

 

주요 소스코드

    private long stackOperation(int last){
        long ret = 0;
        if(headerStack.isEmpty()){
            headerStack.add(new Num(last, 1));
            return 0;
        }
        Num num = new Num(last, 1);
        while(!headerStack.isEmpty() && headerStack.peek().num <= last) {
            if(headerStack.peek().num == num.num) num.dup += headerStack.peek().dup;
            ret += headerStack.pop().dup;
        }
        if(!headerStack.isEmpty()) ret++;
        headerStack.add(num);
        return ret;
    }

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/3015%20%EC%98%A4%EC%95%84%EC%8B%9C%EC%8A%A4%20%EC%9E%AC%EA%B2%B0%ED%95%A9/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃