[백준] 3015번 - 오아시스 재결합 (Java)

문제

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

3015번: 오아시스 재결합

 

입력

 

출력

---

알고리즘

스택

 

참... 어려운 문제다. 혼자서 못풀고 결국 답을 보고 풀었다. 일단 기본적인 프로세스는 다음과 같다.

 

0. 한명의 학생 키를 받는다.

1. Stack이 비어있으면, 아무것도 하지않고 스택에 학생 키를 집어넣는다. Stack이 비어있다는 말은 쌍을 지어줄 학생이 없다는 의미이기 때문이다.

2. 스택이 비어있지 않으면 2가지 중에서 하나를 수행한다.

2-1) 자기 바로 앞에 있는 학생의 키(즉, Stack의 Top)가 자기 자신보다 작을 경우, 스택의 Top 값을 빼버리고 쌍의 개수를 증가시켜준다. (자기 자신과 바로 앞에 있는 학생과 쌍을 지어주는 것) 이 과정을 스택이 비거나, 바로 앞에 있는 학생의 키가 자기 자신보다 클때까지 반복한다. → 자기 앞에 있는 학생이 자기보다 키가 작으면 그 뒤에 사람들은 자기때문에 그 앞에 사람들을 못보기 때문이다. 예를 들어서 stack에 4 3 2가 들어가있는데 4의 키를 가진 사람이 줄을 서면, 그 뒤로 오는 사람들은 3과 2의 키를 가진 사람들을 보지 못할 것이다.

2-2) 바로 앞에 학생의 키가 자기 자신보다 크면 쌍의 개수를 증가시킨다.

3. 스택에 자기 자신을 넣는다.

 

예시로 아래와 같이 입력이 들어온다고 해보자. (count는 쌍의 개수)

2 4 3 2 5

 

1. 2를 입력받는다. 스택은 비어있으므로 2를 넣는다. (stack : {2}, count : 0}

2. 4를 입력받는다. 바로 앞에 있는 2가 자기보다 작으므로 2와 4를 매칭시키고 2를 제거하고 4를 넣는다. (stack : {4}, count : 1}

3. 3을 입력받는다. 바로 앞에 있는 학생 키가 자기보다 크므로 4와 3을 매칭시키고 3을 넣는다. (stack : {4,3}, count : 2}

4. 2를 입력받는다. 바로 앞에 있는 학생 키가 자기보다 크므로 3와 2를 매칭시키고 2를 넣는다. (stack : {4,3,2}, count : 3}

5. 5를 입력받는다.

5-1) 바로 앞에 있는 2가 자기보다 작으므로 2와 5를 매칭시키고 2를 제거한다. (stack : {4,3}, count : 4}

5-2) 바로 앞에 있는 3이 자기보다 작으므로 3와 5를 매칭시키고 3을 제거한다. (stack : {4}, count : 5}

5-3) 바로 앞에 있는 4가 자기보다 작으므로 4와 5를 매칭시키고 4을 제거한다. (stack : {}, count : 6}

 

이렇게 6번이 나온다. 하지만, 여기서 이 문제가 어려운 이유가 나온다. 어딜봐도 "학생 키는 모두 다르다"라는 조건이 없기 때문이다. 그 조건만 있었어도 이 문제가 플레를 가지 않았을 것이다. 나도 이거 때문에 못풀었다. 위 입력을 조금 변형해보자

2 4 3 2 2 5

 

2와 5 사이에 2가 새로 들어왔다. 위에 과정에서 4번과정까지 했다고 가정하고 이어서 똑같은 로직으로 해보겠다.

5. 2를 입력받는다. 바로 앞에 있는 2가 자기와 같으므로 2와 2를 매칭시키고 2를 제거한다. (stack : {4,3}, count : 4}

5-1) 바로 앞에 있는 3이 자기보다 크므로 3과 2를 매칭시키고 2를 넣는다. (stack : {4,3,2}, count : 5}

6. 5를 입력받는다.

6-1) 바로 앞에 있는 2가 자기보다 작으므로 2와 5를 매칭시키고 2를 제거한다. (stack : {4,3}, count : 6}

6-2) 바로 앞에 있는 3이 자기보다 작으므로 3와 5를 매칭시키고 3을 제거한다. (stack : {4}, count : 7}

6-3) 바로 앞에 있는 4가 자기보다 작으므로 4와 5를 매칭시키고 4을 제거한다. (stack : {}, count : 8}

 

이렇게 8번이 나온다. 하지만, 이렇게 하면 중복되어서 들어간 2는 전혀 고려하지 않아서 9번이 나와야되는데 잘못된 답인 8번이 나와버렸다. 따라서, 스택에서 제거하는 과정에서 자기 자신과 같을 경우, 같은게 몇개 나왔는지 기록을 해줘야한다. 그리고 count를 더할때 그 개수만큼 더해야한다.

위와 같이 바로 앞에 있는 학생키와 지금 입력받은 키가 같으면, 자신과 같은 사람이 총 몇명있는지 기록을 해뒀다. 그럼 다시 위와 같은 과정으로 진행을 해보자. (이번엔 3번과정까진 했다는 전제)(스택 옆에 있는 괄호는 앞서말한 자기 자신과 같은 것의 개수를 의미함)

 

4. 2를 입력받는다. 바로 앞에 있는 학생 키가 자기보다 크므로 3와 2를 매칭시키고 2를 넣는다. (stack : {4(1),3(1),2(1)}, count : 3}

5. 2를 입력받는다. 바로 앞에 있는 2가 자기와 같으므로 2와 2를 매칭시키고 2를 제거한다. (stack : {4(1),3(1)}, count : 4}

5-1) 바로 앞에 있는 3이 자기보다 크므로 3과 2를 매칭시키고 2를 넣는다. (stack : {4(1),3(1),2(2)}, count : 5}

6. 5를 입력받는다.

6-1) 바로 앞에 있는 2가 자기보다 작으므로 2와 5를 매칭시키고 2를 제거한다. 그런데 이때, 2의 같은것 개수가 2라고 기록되있으므로 count를 2만큼 증가시킨다. (stack : {4,3}, count : 7}

6-2) 바로 앞에 있는 3이 자기보다 작으므로 3와 5를 매칭시키고 3을 제거한다. (stack : {4}, count : 8}

6-3) 바로 앞에 있는 4가 자기보다 작으므로 4와 5를 매칭시키고 4을 제거한다. (stack : {}, count : 9}

 

위와같은 과정으로 답이 정상적으로 나온다. 진짜 같은것 처리 때문에 많이 어려웠던 문제였다.

---

코드

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

public class Main {
    public static class Node{
        int cur;
        long count;

        public Node(int cur, long count){
            this.cur = cur;
            this.count = count;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        //최악의 경우에는 int 범위를 넘어갑니다.
        long answer = 0;
        Stack<Node> stack = new Stack<>();
        for(int i = 0; i<n; i++){
            int m = Integer.parseInt(br.readLine());
            Node cur = new Node(m, 1);
            //stack에 들어있는 것중에서 맨위에서부터 자기보다 작거나 같은건 전부 빼버림
            while(!stack.isEmpty() && stack.peek().cur<=m){
                Node prev = stack.pop();
                answer += prev.count;
                if(prev.cur == m){
                     cur.count += prev.count;
                }
            }
            
            //자기보다 큰거 남아있는거랑도 짝을 지어줘야됨
            if(!stack.isEmpty()){
                answer ++;
            }

            stack.push(cur);
        }

        System.out.println(answer);
    }
}