[백준] 3015

오아시스 재결합

문제

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.

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

줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

출력

서로 볼 수 있는 쌍의 수를 출력한다.

풀이

const oasis = () => {
  const fs = require("fs");
  let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
  const len = parseInt(input[0]);
  input.shift();
  input = input.map((n) => {
    return parseInt(n);
  });
  let stack = [];
  let ans = 0;

  for (let i of input) {
    while (stack.length > 0 && stack[stack.length - 1][0] < i) {
      ans += stack[stack.length - 1][1];
      stack.pop();
    }
    if (stack.length < 1) stack.push([i, 1]);
    else if (stack[stack.length - 1][0] === i) {
      ans += stack[stack.length - 1][1];
      if (stack.length - 2 >= 0) ans++;
      stack[stack.length - 1][1]++;
    } else if (stack[stack.length - 1][0] > i) {
      ans += 1;
      stack.push([i, 1]);
    }
  }
  console.log(ans);
};

// 오아시스 노래들으면서 푸는데 슬슬 오아시스 노래가 화나려고하는군요
// 그와중에 오아시스 재결합 하면 좋겠다.. 그럴리없겠지만..

oasis();

반성회

// ======= 입력값 =======
7
2
4
1
2
2
5
1

입력값 배열: [2, 4, 1, 2, 2, 5, 1]

// ======= 동작 =======
0번째 루프
현재 원소: 2
스택: []
// 스택이 비어 있으므로 아무것도 pop하지 않는다
// 가장 왼쪽 사람 기준으로 더 왼쪽에는 사람이 없으므로 이 사람은 아무도 볼 수 없다
// 스택에는 [2, 1] (1번째 인덱스는  해당 원소의 개수) 을 넣는다
쌍의 수: 0

1번째 루프
현재 원소: 4
스택: [[2, 1]]
// 스택이 비어있지 않고, 4는 2보다 크므로 2를 pop하고, 1번째 인덱스 값만큼 쌍의 수를 더해준다
// 4는 2를 볼 수 있으나, 4가 2보다 크므로 4보다 뒤에 있는 사람들은 앞으로 2를 볼 수 없다
// 4가 왼쪽에서 볼 수 있는 사람은 2 한 명이므로 쌍의 수가 1 증가
쌍의 수: 1

2번째 루프
현재 원소: 1
스택: [[4, 1]]
// 스택이 비어있지 않지만, 4는 1보다 크므로 아무것도 pop하지 않는다
// 1은 4를 볼 수 있고, 1은 4보다 작으므로 뒤에 있는 사람들도 4를 볼 수 있다
// 1이 왼쪽에서 볼 수 있는 사람은 4 한 명이므로 쌍의 수가 1 증가
쌍의 수: 2

3번째 루프
현재 원소: 2
스택: [[4, 1], [1, 1]]
// 스택이 비어있지 않지만, 2는 1보다 크므로 1을 pop하고, 1번째 인덱스 값만큼 쌍의 수를 더해준다
// 2는 1을 볼 수 있으나, 2가 1보다 크므로 2보다 뒤에 있는 사람들은 앞으로 1을 볼 수 없다
// 2가 왼쪽에서 볼 수 있는 사람은 4, 1의 2명이므로 쌍의 수가 2 증가
쌍의 수: 4

4번째 루프
현재 원소: 2
스택: [[4, 1], [2, 1]]
// 스택이 비어있지 않고, 2와 2는 같으므로 아무것도 pop하지 않는다
// 2는 2와 4 모두를 볼 수 있고, 키가 크지 않으므로 뒤에 있는 사람들도 이들을 볼 수 있다
// 2가 왼쪽에서 볼 수 있는 사람은 2명이므로 쌍의 수가 2 증가
쌍의 수: 6
// 스택의 top에 있는 2와 현재 원소인 2가 같은 수이므로 2를 push하지 않고 
// 스택에 이미 있는 [2, 1] 배열의 1번째 인덱스를 +1 한다

5번째 루프
현재 원소: 5
스택: [[4, 1], [2, 2]]
// 스택이 비어있지 않지만, 5는 2, 4보다 크므로 둘 다 pop하고, 1번째 인덱스 값만큼 쌍의 수를 더해준다
// [4, 1]의 1번째 인덱스 값은 1이고, [2, 2] 의 1번째 인덱스 값은 2이므로 쌍의 수는 총 3 증가한다
// 5는 2와 4를 볼 수 있으나, 이들은 5보다 작으므로 2보다 뒤에 있는 사람들은 앞으로 이들을 볼 수 없다
// 5가 왼쪽에서 볼 수 있는 사람은 3명이므로 쌍의 수가 3 증가
쌍의 수: 9

6번째 루프
현재 원소: 1
스택: [[5, 1]]
// 스택이 비어있지 않고, 5는 1보다 크므로 아무것도 pop하지 않는다
// 1은 5를 볼 수 있고, 키가 크지 않으므로 뒤에 있는 사람들도 5를 볼 수 있다
// 1이 왼쪽에서 볼 수 있는 사람은 1명이므로 쌍의 수가 1 증가
쌍의 수: 10

// ====== 출력 ======= 
10

// ======= 입력값 =======
6
6
6
6
5
2
5

입력값 배열: [6, 6, 6, 5, 2, 5]

// ======= 동작 =======
0번째 루프
현재 원소: 6
스택: []
// 스택이 비어 있으므로 아무것도 pop하지 않는다
// 가장 왼쪽 사람 기준으로 더 왼쪽에는 사람이 없으므로 이 사람은 아무도 볼 수 없다
// 스택에는 [2, 1] (1번째 인덱스는 해당 원소의 개수) 을 넣는다
쌍의 수: 0

1번째 루프
현재 원소: 6
스택: [[6, 1]]
// 스택이 비어있지 않지만, 6과 6은 같으므로 아무것도 pop하지 않는다
// 6은 6을 볼 수 있고, 6은 6과 같으므로 뒤에 있는 사람들도 6을 볼 수 있다
// 6이 왼쪽에서 볼 수 있는 사람은 한 명이므로 쌍의 수가 1 증가
쌍의 수: 1
// 스택의 top에 있는 6과 현재 원소인 6은 같은 수이므로 6을 push하지 않고 
// 스택에 이미 있는 [6, 1] 배열의 1번째 인덱스를 +1 한다

2번째 루프
현재 원소: 6
스택: [[6, 2]]
// 스택이 비어있지 않지만, 6과 6은 같으므로 아무것도 pop하지 않는다
// 6은 6을 볼 수 있고, 6은 6과 같으므로 뒤에 있는 사람들도 6을 볼 수 있다
// 6이 왼쪽에서 볼 수 있는 사람은 두 명이므로 쌍의 수가 2 증가
쌍의 수: 3
// 스택의 top에 있는 6과 현재 원소인 6은 같은 수이므로 6을 push하지 않고 
// 스택에 이미 있는 [6, 2] 배열의 1번째 인덱스를 +1 한다

3번째 루프
현재 원소: 5
스택: [[6, 3]]
// 스택이 비어있지 않지만, 5는 6 한 명을 제외하고 모두 볼 수 없다
// 5는 6 한 명만을 볼 수 있고, 뒤에 있는 사람들도 5를 볼 수 있다
// 5가 왼쪽에서 볼 수 있는 사람은 한 명이므로 쌍의 수가 1 증가
쌍의 수: 4

4번째 루프
현재 원소: 2
스택: [[6, 3], [5, 1]]
// 스택이 비어있지 않고, 2는 5 한 명을 제외하고 모두 볼 수 없다
// 2는 5 한 명만을 볼 수 있고, 키가 크지 않으므로 뒤에 있는 사람들도 이들을 볼 수 있다
// 2가 왼쪽에서 볼 수 있는 사람은 1명이므로 쌍의 수가 1 증가
쌍의 수: 5

5번째 루프
현재 원소: 5
스택: [[6, 3], [5, 1], [2, 1]]
// 스택이 비어있지 않고, 5는 2, 5, 6 모두를 볼 수 있으나 뒤의 6 두명은 볼 수 없다
// 5가 왼쪽에서 볼 수 있는 사람은 2, 5, 6의 3명이므로 쌍의 수가 3 증가
쌍의 수: 8

// ====== 출력 ======= 
8

• 어차피 A ↔ B이든 B ↔ A이든 같은 쌍이므로, A → B 단방향만 찾아도 쌍의 수는 구할 수 있다

  따라서 사람들의 시선은 왼쪽을 향한다고 가정하였음

• 현재 가리키는 원소 (현재 사람의 키) 가 i, 스택의 top 원소가 [t, n]일 때

  (t는 현재 가리키는 사람보다 왼쪽에 위치한 사람의 키, n은 연속으로 키가 같은 사람의 수)

  1. t가 i보다 작으면 스택을 계속 pop한다

     이때 쌍의 수 ans는 pop한 원소의 n값만큼 더한다

     t가 i보다 작으므로 i는 n명의 t를 모두 볼 수 있기 때문

  2. 조건문에 진입

     • 스택의 길이가 0일 경우 스택에 [i, 1] 을 push한다

       키가 i인 사람이 연속으로 등장한 횟수가 초기화되었으므로 1번째 원소의 값은 1이다

     • 현재 스택의 top 원소 t가 i와 같을 때

       i는 자신과 키가 같은 n명을 볼 수 있으므로 쌍의 수 ans에 n만큼 더한다

       • 만약 스택의 원소 개수가 1개 이상일 경우 (top 원소 외에 다른 원소가 존재할 경우)

         t보다 키가 큰 사람이 뒤에 존재한다는 의미이고, 어차피 t보다 큰 사람이 한 명이라도 등장하면 그 뒤에 있는 사람들은 볼 방법이 없으므로 ans에 1을 더한다

     • 현재 스택의 top 원소 t가 i보다 클 때

       i는 t 외의 다른 사람을 볼 수 없으므로 ans에 1을 더한다

       그리고 [i, 1]을 push한다

  3. 1 ~ 2를 모든 사람에 대해 왼쪽에서 오른쪽으로 반복한다

그래서 오아시스 재결합 언제함? (안함)