[BOJ 14468] 소가 길을 건너간 이유 2

문제

소가 길을 건너간 이유 2

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

 

 

풀이

설명

경로가 무조건 만나는 소가 몇 쌍인지를 구하는 문제입니다.

 

스택을 이용합니다.

 

과정은 다음과 같습니다.

1. 문자열을 순회합니다.
2. 처음 나온 문자인 경우
   1. 스택에 추가합니다.
3. 두 번 나온 문자인 경우
   1. 그 사이에 있는 문자 개수를 카운트해 더합니다.
   2. 해당 문자를 제거합니다.

 

예시 코드

function solution() {
  const str = input();
  let cnt = 0;
  const visited = Array(26).fill(false);
  let stack = [];

  for (let i = 0; i < str.length; i++) {
    const ch = str[i];
    const num = ch.charCodeAt(0) - 65;
    if (!visited[num]) {
      visited[num] = true;
      stack.push(ch);
    } else if (stack.at(-1) === ch) stack.pop();
    else {
      let j = stack.length - 1;
      for (; j >= 0; j--) {
        if (stack[j] === ch) break;
        cnt++;
      }
      stack = [...stack.slice(0, j), ...stack.slice(j + 1)];
    }
  }

  return cnt;
}