자바스크립트로 알고리즘 정리하기 #4 Stack, Queue, Deque 연습문제 풀이

자바스크립트로 알고리즘 정리하기 #4 Stack, Queue, Deque 연습문제 풀이

boj 17413

문제 링크

Stack을 사용한 풀이

위 문제의 경우에는 단어를 뒤집는 것(Stack의 특성 이용) + tag를 고려해주어야 한다.

단어를 뒤집을 때는 Stack에 순서대로 push() 후에 순서대로 pop()하면 LIFO(Last In First Out) 특성에 의해 단어가 반전되어 나온다.

공백( )이 나오기 전까지 스택에 담았다가 공백이 나올 때 스택에 담겨있는 것을 모두 순서대로 pop() 한 뒤에 공백 한 칸을 추가해주는 방식으로 하면 단어가 반전된다.

그 외에 < > 화살괄호가 나왔을 때는 반전하지 말고 문자열을 그대로 저장소에 넣어주면 된다.

class Stack {
  constructor() {
    this.data = [];
    this.top = 0;
  }

  push(element) {
    this.data[this.top] = element;
    this.top += 1;
  }

  length() {
    return this.top;
  }

  peek() {
    return this.data[this.top - 1];
  }

  isEmpty() {
    return this.top === 0;
  }

  pop() {
    if (this.isEmpty() === false) {
      this.top = this.top - 1;
      return this.data.splice(-1)[0];
    }
  }

  print() {
    this.data.map((element) => {
      console.log(element);
    });
  }

  reverse() {
    this._reverse(0);
  }

  // private method
  _reverse(index) {
    if (index < this.top - 1) {
      this._reverse(index + 1);
    }
    console.log(this.data[index]);
  }
}

let solution = (line) => {
  let stack = new Stack();
  let isTagOpen = false;
  let answer = '';

  line.split('').map((w) => {
    if (w === '<') {
      while (!stack.isEmpty()) {
        answer += stack.pop();
      }

      isTagOpen = true;
    }

    if (isTagOpen) {
      answer += w;
    }

    if (isTagOpen && w === '>') {
      isTagOpen = false;
    }

    if (!isTagOpen && w !== '>' && w !== ' ') {
      stack.push(w);
    }

    if (!isTagOpen && w === ' ') {
      while (!stack.isEmpty()) {
        answer += stack.pop();
      }

      answer += ' ';
    }
  });

  while (!stack.isEmpty()) {
    answer += stack.pop();
  }

  return answer;
};

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on('line', function (line) {
  console.log(solution(line));
  rl.close();
}).on('close', function () {
  process.exit();
});

Stack을 사용하지 않은 풀이 (정규표현식 이용)

이 경우가 확실히 소스코드는 짧다. 근데 시간복잡도는 위의 Stack을 이용할 때와 비슷하다.

이 경우에는 정규표현식으로 <``> 형태의 태그를 잡아내어 그 부분을 따로 처리하고 나머지는 반전시키는 방법으로 하였다.

이 방법보다는 위의 Stack을 이용한 방법이 훨씬 직관적이고 쉽게 풀렸다.

let solution = (line) => {
  // 하나의 태그는 <로 시작해서 >가 아닌 것들로 이어지다가 >로 끝나야 함
  // <>로만 잡으면 <로시작해서 >로 끝나는 가장 긴 게 잡힘.
  // 내부 내용에 닫히는 태그가 없어야 하나의 태그씩 잘 집을 수 있음
  let re = /\<([^\>]*)\>/gi;
  let regex = RegExp(re);

  line.match(re) !== null
    ? line.match(re).map((m) => {
        // match한 결과가 이상하게 스페이스가 줄어있음
        // replace를 고차함수로 이용하면 원본을 활용할 수 있음
        // m이 스페이스가 줄어있는데도 replace 매칭은 잘 됨
        line = line.replace(m, (o) => o.replace(/ /g, '$'));
      })
    : '';

  let words = line.split(' ');

  return words
    .map((word) => {
      return word
        .replace(re, (o) => ' ' + o + ' ')
        .trim()
        .split(' ')
        .map((w) => (regex.test(w) ? w : w.split('').reverse().join('')))
        .join('');
    })
    .join(' ')
    .replace(/\$/g, ' ');
};

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on('line', function (line) {
  console.log(solution(line));
  rl.close();
}).on('close', function () {
  process.exit();
});

boj 10799 쇠막대기

문제 링크

스택을 이용해 풀었다.

케이스를 정리하면

• ()(레이저)가 나왔을 때마다 스택에 들어있는 (의 개수를 세어준다.
• )가 나왔을 때 레이저인지 쇠막대기인지 구분을 해줘야 한다.
  • 쇠막대기일 때는 아무런 일이 일어나지 않고, 레이저일 때는 스택에 들어있는 (의 갯수에 따라 쇠막대기의 수가 증가한다.
• 레이저는 항상 ()와 같이 붙어서 나온다.
• 스택에 (의 인덱스를 넣어서 인덱스 차이가 1이 나는지 확인해야 한다.

코드를 말로 정리하면

• (가 들어왔을 때
  1. 스택에 (를 추가
  2. 2번 이상 연속으로 들어오면 매번 (가 들어올 때마다 쇠막대기가 생기므로 정답에 +1
• (가 아닌 다른 것이 들어왔을 때 ())
  1. 스택에 있는 (를 뺌
  2. 이전에 (가 들어왔었다면, 레이저, pop() 이후의 Stack의 길이만큼 더함 (쇠막대기 * 2)
  3. (가 연속으로 들어오는지 카운트하던 변수 초기화

class Stack {
  constructor() {
    this.data = [];
    this.top = 0;
  }

  push(element) {
    this.data[this.top] = element;
    this.top += 1;
  }

  length() {
    return this.top;
  }

  peek() {
    return this.data[this.top - 1];
  }

  isEmpty() {
    return this.top === 0;
  }

  pop() {
    if (this.isEmpty() === false) {
      this.top = this.top - 1;
      return this.data.splice(-1)[0];
    }
  }

  print() {
    this.data.map((element) => {
      console.log(element);
    });
  }

  reverse() {
    this._reverse(0);
  }

  // private method
  _reverse(index) {
    if (index < this.top - 1) {
      this._reverse(index + 1);
    }
    console.log(this.data[index]);
  }
}

let solution = (line) => {
  let stack = new Stack();
  let openCount = 0;
  let answer = 0;

  line.split('').map((e) => {
    if (e === '(') {
      openCount += 1;
      stack.push(e);

      // 2번 이상 연속으로 '('가 나올 때는 쇠막대기가 생김
      if (openCount > 1) {
        answer += 1;
      }
    } else {
      stack.pop();

      // 레이저 쏜 경우 / 이전에 생성된 막대 길이만큼 더해줌
      // 이전에 생성된 막대 길이 = pop() 연산을 수행한 stack의 길이
      if (openCount > 0) {
        answer += stack.length();
      }

      openCount = 0;
    }
  });

  return answer;
};

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on('line', function (line) {
  console.log(solution(line));
  rl.close();
}).on('close', function () {
  process.exit();
});

boj 17298 오큰수

시간/메모리 제한이 있기 때문에, 생각보다 어려운 문제이다.

이 문제의 핵심은 스택을 이용하면서 시간복잡도를 최대한 줄이는 것이다.

처음에 풀었던 답안은 아래와 같은데,

let solution = ([length, line]) => {
  let stack = [];
  let answer = [];

  line
    .split(' ')
    .map((e) => +e)
    .map((e, i, arr) => {
      stack = stack.filter((j) => {
        if (arr[j] < e) {
          answer[j] = e;
          return false;
        }

        return true;
      });

      if (e < arr[i + 1]) {
        answer.push(arr[i + 1]);
      } else {
        answer.push(-1);
        stack.push(i);
      }

      return null;
    });

  return answer.join(' ');
};

let input = [];

const readline = require('readline');
const {Console} = require('console');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on('line', function (line) {
  input.push(line);
}).on('close', function () {
  console.log(solution(input));
  process.exit();
});

위 답안의 경우 메모리초과로 실패한다.

그 이유는 아마 filter 메소드에서 stack의 모든 수를 순회하기 때문이다. 사실 stack을 배열처럼 쓰면 stack을 쓰는 의미가 전혀 없다.

stack이란 것은

• top()으로 값을 보고
• 값을 넣을 때는 push()
• 값을 뺄 때는 pop()으로 해야 한다.

그래야 의미가 있는 자료구조이다.

오큰수에서 시간복잡도를 줄이는 핵심은 '스택으로 어떻게 시간복잡도를 줄이냐?'이다.

이를테면

5 4 6 9 8 41 3 2 1 이라는 숫자가 있다고 가정했을 때

오큰수를 구한다면, 내 기준 오른쪽 숫자 중에 나보다 큰 가장 왼쪽 숫자를 찾아야 한다.

가장 일반적인 방법은 5일 때, 4 6 9 8 41 3 2 1 왼쪽부터 순차적으로 돌아가며 찾아보고 나보다 큰 숫자가 나오면 바로 그게 가장 왼쪽 수니까 더이상 찾을 필요 없이 return할 것이다.

그런데 이렇게 하면 O(n^2)이 나오게 된다. 그러면 어떻게 할까? 스택을 이용해서 나보다 큰 수가 나왔을 때 한방에 처리하는 것이다.

5로 시작했을 때, 그냥 스택에 5의 인덱스 번호를 넣는다. 그러면 스택에 [0]이 들어간다.

다음숫자는 4이다. 4가 스택 맨 위의 인덱스에 해당하는 값인 5보다 큰지 확인한다. 4는 5보다 작다. 그러면 또 4의 인덱스를 스택에 push() 한다. [0, 1]이 스택에 차있다.

다음 숫자는 6이다. 6이 스택 맨 위의 인덱스에 해당하는 값인 4보다 큰지 확인한다. 6은 4보다 크다. 그러면 스택을 pop() 연산하고 4의 인덱스 자리에 6을 넣는다. 또 6이 스택의 다음 맨 위 인덱스에 해당하는 값인 5보다 큰지 확인한다. 5보다 6이 더 크다. 그러면 5의 인덱스 값을 기록하고 있는 스택의 맨 위 인덱스 값을 pop() 연산한다. 5의 인덱스 자리에도 6을 넣어준다.

여기서 알 수 있는 간단한 사실은, 스택에는 계속 숫자가 내림차순으로 들어갈 것이란 거다. 스택의 맨 위에는 가장 작은 값이 올 수 밖에 없다. 왜냐면 큰 값이 나오는 순간 pop()되어버리기 때문이다.

이러한 특성 때문에 새로운 숫자가 들어왔을 때는 스택의 맨 위 인덱스에 해당하는 숫자만 비교하면 된다. 왜냐하면 내림차 순으로 정렬했을 때 가장 작은 값이니까, 그것보다도 큰 값이 아니라면 그 전 값보다 클 수가 없다.

이러한 특성을 이용해 시간복잡도를 줄인 코드가 아래 코드이다.

let solution = ([length, line]) => {
  let stack = [];
  let answer = new Array(length).fill(-1);

  line
    .split(' ')
    .map((e) => +e)
    .map((e, i, arr) => {
      while (stack.length !== 0 && arr[stack[stack.length - 1]] < e) {
        answer[stack.pop()] = e;
      }

      stack.push(i);
    });

  while (stack.length !== 0) {
    answer[stack.pop()] = -1;
  }

  return answer.join(' ');
};

let input = [];

const readline = require('readline');
const {Console} = require('console');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on('line', function (line) {
  input.push(line);
}).on('close', function () {
  console.log(solution(input));
  process.exit();
});

결과적으로 이 문제를 통해 우리가 배워야 할 것은,

수가 정렬되는 등의 경우로 배열의 맨 위만 바라봐도 되는 경우, 스택을 활용하여 시간복잡도를 줄일 수 있다는 것이다.

boj 17299 오등큰수

1. 먼저 숫자를 배열로 보기 쉽게 split() 메소드를 이용해서 띄어쓰기 기준으로 배열로 변경
2. 정답 배열을 -1로 초기화 (정답 배열은 반드시 문제의 숫자 배열과 길이가 똑같게 되어있음, -1로 초기화 하는 이유는 오등큰수가 없는 경우 -1이 들어가야 하기 때문에 디폴트 값으로 넣어줌)
3. dictionary 구현해서 모든 숫자의 빈도수를 먼저 셈 -> 빈도수의 딕셔너리가 만들어짐
4. 모든 숫자를 다시한번 순회하면서 스택에 숫자의 위치 인덱스를 넣음
5. 이번 숫자의 빈도수와 스택의 가장 위의 빈도수를 비교함
6. 스택의 가장 위의 빈도수보다 큰 경우 정답 배열에 해당 숫자를 넣음 그리고 스택에 기존에 가장 위에 있던 숫자는 pop() 해서 지워줌 -> while()을 이용하여 반복

• 이 연산으로 인해 스택에는 빈도수가 내림차순으로 저장됨

7. 정답 배열을 join() 하여 띄어쓰기 형태로 반환하면 끝

let solution = ([n, line]) => {
  let dict = {};
  let answer = new Array(+n).fill(-1);
  let stack = [];

  line
    .split(' ')
    .map((e) => +e)
    .map((e) => {
      dict[e] = dict[e] ? dict[e] + 1 : 1;
      return e;
    })
    .map((e, i, arr) => {
      // 인덱스를 저장했으므로 arr의 배열에서 스택에 저장된 인덱스를 불러와야 함 그리고 그것을 다시 딕셔너리의 빈도수로 바꿈
      while (stack.length > 0 && dict[e] > dict[arr[stack[stack.length - 1]]]) {
        answer[stack.pop()] = e;
      }

      stack.push(i);
    });

  // 스택에 조건 안맞았던 인덱스들 쌓아놨다가 해결하기
  // 스택은 끝까지 돌아보게 되므로 하나하나씩 해결해서 전부 해결 가능

  return answer.join(' ');
};

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on('line', function (line) {
  input.push(line);
}).on('close', function () {
  console.log(solution(input));
  process.exit();
});