[연습문제] 16. 71 ~ 75 스택

in 코딩테스트 on 연습문제




자료구조때 공부한 문제들 다시 복습하면서 완전히 익숙해지기.! 그때는 이해 못했던 문제 이번에는 완벽하게 이해하고 넘어가자


71. 기차 운행

오른쪽 그림처럼 열차가 들어갔다 나올 수 있는 플랫폼이 있다.
열차가 1번부터 3번까지 순서대로 들어온다고 했을 때, 입력 순서대로 나갈 수 있는지 없는지 판단하는 프로그램을 작성하시오.
입력은 차량 순서 번호가 적혀 있는 배열이며, 가능 여부에 따라 true/false 를 반환한다.

function answer(train) {
  // 코드 구현 시작 영역
  let stack = [];
  let num = 0;
  for (let i = 0; i < train.length; i++) {
    while (stack.length === 0 || stack[stack.length - 1] < train[i]) {
      stack.push(++num);
    }

    if (stack[stack.length - 1] === train[i]) stack.pop();
    else return false;
  }

  return true;
  // 코드 구현 종료 영역
}

let input = [
  [1, 2, 3],
  [3, 2, 1],
  [3, 1, 2],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1} `);
  console.log(answer(input[i]));
}

// #1 true
// #2 true
// #3 false

예전에 이 문제를 풀 때는 임시로 1,2,3 순서를 담은 배열을 만들었었는데,
더 많은 케이스에 대응하기에는 위와 같은 코드가 더 좋은 코드인것 같다.


72. 괄호 짝 찾기

계산 수식이 주어졌을 때, 같은 짝의 괄호 위치를 찾는 프로그램을 제작하시오.
입력은 계산 수식으로 주어지며, 괄호의 짝 별 위치를 [시작, 끝]으로 찾아 2차원 배열 형태로 반환한다.
위치 시작 값은 0으로 시작하며, 하나라도 짝이 맞지 않을 경우 빈 배열을 반환한다.

function answer(str) {
  let result = [];
  let stack = [];
  let indexStack = [];
  for (let i = 0; i < str.length; i++) {
    if (str[i] === "(") {
      stack.push(str[i]);
      indexStack.push(i);
    } else if (str[i] === ")") {
      if (stack[stack.length - 1] === "(") {
        result.push([indexStack.pop(), i]);
        stack.pop();
      } else {
        return [];
      }
    }
  }
  return stack.length === 0 ? result : [];
}

let input = [
  "(a+b)",
  "(a*(b+c)+d)",
  "(a*(b+c)+d+(e)",
  "(a*(b+c)+d)+e)",
  "(a*(b+c)+d)+(e*(f+g))",
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1} `);
  console.log(answer(input[i]));
}

// #1 [ [ 0, 4 ] ]
// #2 [ [ 3, 7 ], [ 0, 10 ] ]
// #3 []
// #4 []
// #5 [ [ 3, 7 ], [ 0, 10 ], [ 15, 19 ], [ 12, 20 ] ]



저번엔 내가 스스로 풀지 못했지만 이제는 스스로 풀 수 있다.!
다만 아래 코드가 더 깔끔하긴 하다…ㅎㅎㅎ

function answer(str) {
  let result = [];
  let stack = [];
  for (let i = 0; i < str.length; i++) {
    if (str[i] === "(") {
      stack.push(i);
    } else if (str[i] === ")") {
      if (stack.length === 0) return [];
      result.push([stack.pop(), i]);
    }
  }
  return stack.length === 0 ? result : [];
}

굳이 스택에 넣을 때 “(“를 넣을 필요 없다는 것을 파악하지 못했다. (어차피 “(“일때만 넣은건데…)



73. 접시 꺼내기

접시가 a,b,c,d 순으로 한쪽이 막혀 있는 세척기에 들어간다고 할 때, b,a,c,d 순으로 꺼내기 위해서는
push,push,pop,pop,push,pop,push,pop 순으로 꺼내면 된다.
세척기에 꺼내야 하는 접시의 순서가 주어질 때, push/pop으로 접시가 꺼내 져야 하는 동작ㅇ르 계산하는 프로그램을 작성하시오.
입력은 접시의 수가 10개를 넘기지 않는 소문자 알파벳으로 수어지며,
접시 꺼내는 push/pop 연산 동작을 push = 0, pop = 1로 변환하여 배열을 반환한다.
(단, 주어진 순서로 못 꺼낼 경우, 빈 배열로 반환)

function answer(str) {
  let result = [];
  let stack = [];
  let index = 0;

  let dish = str.split("").sort().join("");
  for (let i = 0; i < str.length; i++) {
    while (stack.length === 0 || stack[stack.length - 1] < str[i]) {
      stack.push(dish[index++]);
      result.push(0);
    }
    if (stack.length === 0 || stack[stack.length - 1] > str[i]) {
      return [];
    } else {
      stack.pop();
      result.push(1);
    }
  }

  // 코드 구현 종료 영역
  return result;
}

let input = ["bacd", "dabc", "edcfgbijha"];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1} `);
  console.log(answer(input[i]));
}

// #1 [ [ 0, 4 ] ]
// #2 [ [ 3, 7 ], [ 0, 10 ] ]
// #3 []
// #4 []
// #5 [ [ 3, 7 ], [ 0, 10 ], [ 15, 19 ], [ 12, 20 ] ]



오늘 푼 첫번째 문제와 맥락은 비슷하다.
알파벳이었어서 증감연산자로 a,b,c,d 순서를 할 수 없어서 고민이었는데, 입력된 문자열을 정렬하여 올바른 순서를 찾는 방법이 신선했다.
숫자든, 문자든 순차적으로 들어갈 때, stack[stack.length - 1] < str[i] stack[stack.length - 1] < train[i] 이렇게 사용한다는 것 잊지말고 다음에 활용해보자.



74. 기린의 시야

기린이 앞쪽만 볼 수 있는 경우, 다른 기린을 몇 마리 볼 수 있는지 총합을 구하는 프로그램을 작성하시오.
기린은 자신보다 작거나 같은 기린만 볼 수 있으며, 자신보다 큰 기린이 나올 경우 앞 기린들이 가려서 볼 수가 없다.
입력은 기린 별 키 값이 들어오며, 달느 기린을 볼 수 있는 총합을 구해 반환한다.
예를 들어 5,2,4,2,6,1 순의 기린 키가 입력으로 들어오면 1번 기린으 2,3,4 기린을 볼 수 있어 3마리, 2번은
볼 수 있는 기린이 없고, 3번은 1마리, 4번은 0마리, 5번은 1마리, 마지막 기린은 앞의 기린이 없으므로 0마리로, 답은 총 5마리 기린이다.

function answer(giraffe) {
  let result = 0;

  for (let i = 0; i < giraffe.length; i++) {
    for (let j = i + 1; j < giraffe.length; j++) {
      if (giraffe[i] >= giraffe[j]) result++;
      else break;
    }
  }
  // 코드 구현 종료 영역
  return result;
}

let input = [
  [10, 3, 7, 4, 12, 2],
  [7, 4, 12, 1, 13, 11, 12, 6],
  [20, 1, 19, 18, 15, 4, 6, 8, 3, 3],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1} `);
  console.log(answer(input[i]));
}

// #1 5
// #2 6
// #3 30



이 문제 과거에 되게 어렵다고 생각햇었는데, 엄청 간단한 문제여서 이상하다.
비록 stack을 이용해서 풀진 않았지만 매우 간단한 문제였네….?ㅋㅋㅋㅋ

function answer(giraffe) {
  let result = 0;

  let stack = [];
  giraffe.push(Number.MAX_SAFE_INTEGER); // 마지막 기린의 시야도 세기 위해
  for (let i = 0; i < giraffe.length; i++) {
    while (stack.length !== 0 && stack[stack.length - 1]["h"] < giraffe[i]) {
      result += i - stack.pop()["i"] - 1;
    }
    stack.push({ h: giraffe[i], i: i });
  }
  // 코드 구현 종료 영역
  return result;
}

스택을 적용한 풀이법!
비록 스스로 풀진 못했지만, 저번엔 이해조차 못하던 코드가 이제는 이해가 간다.
위와 같은 풀이법도 기억해뒀다가 나중에 필요하면 써먹도록 하자!
스택을 사용하면 이중for문으로 n2이던 시간복잡도가 n으로 변경된다!
배열에 객체를 넣어서 사용하는법도 익숙해지기 ^___^


75. 괄호 계산

4개의 기호 (,),[,] 를 이용해서 만들어지는 괄호열로, 아래 규칙으로 계산하는 프로그램을 작성하시오

  1. '()' 인 괄호 열 값은 2
  2. '[]' 인 괄호 열 값은 3
  3. '(x)' 인 괄호 열 값은 2 * X
  4. '[x]' 인 괄호 열 값은 3 * x
  5. ()[] 는 () + []

예를 들어 ()[[] 는 2+3*3 = 11 이다.
만약 쌍이 맞지 않거나 기호 순서가 비정상적이라 올바른 괄호 셋이 만ㄷ르어지지 않는 경우에는 0을 반환한다.
입력은 4개의 기호로만 이루어진 괄호가 문자열 형태로 주어지며, 계산을 통해 나온 정수를 반환한다.

function answer(str) {
  let result = 0;

  // ( > x2
  // [ > x3
  // ) > /2
  // ] > /3
  // () or [], 현재 temp값을 result에 더해준다.

  let stack = [];
  let temp = 1;

  for (let i = 0; i < str.length; i++) {
    let mark = str[i];

    switch (mark) {
      case "(":
        temp *= 2;
        stack.push(mark);
        break;
      case "[":
        temp *= 3;
        stack.push(mark);
        break;
      case ")":
        if (stack.length === 0 || stack[stack.length - 1] !== "(") {
          return 0;
        }
        if (str[i - 1] === "(") {
          result += temp;
        }
        stack.pop();
        temp /= 2;
        break;
      case "]":
        if (stack.length === 0 || stack[stack.length - 1] !== "[") {
          return 0;
        }
        if (str[i - 1] === "[") {
          result += temp;
        }
        stack.pop();
        temp /= 3;
        break;
    }
  }
  return stack.length === 0 ? result : 0;
}

let input = ["(()[[]])", "[][]((])", "(()[[]])([])"];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1} `);
  console.log(answer(input[i]));
}

// #1 22
// #2 0
// #3 28


이 문제 과거에도 이해 못했었는데, 오늘은 무조건 이해하려고 한시간은 눈싸움 한 것 같다.
[[]] 이 경우 일때, 왜 마지막 닫히는게 안더해질 수 있는지가 너무 의문이었는데, 바로 전이 “]”인지를 비교하는게
스택이 아니고, 문자열이었다. (나는 그동안 스택으로 생각하고 있었음!)
문자열이 바로 이어질때만 진짜 더해주고, 이어지지 않을 때는 temp값만 원상 복귀시켜주고 stack에서 pop하는 문제였다.
연달아서 닫힐때만 더해준다!
이해만 하는데도 한시간이 넘게 걸리다니….. 더 노력해야겠다………!!😂😭