프로그래머스 - 쇠막대기 (JavaScript)

문제 : https://programmers.co.kr/learn/courses/30/lessons/42585

프로그래머스

문제 해결 과정

1) 처음 시도한 방법 -> 테스트 케이스 1개가 시간초과

1) 쇠막대기를 보관하는 스택을 만든다.
2) input으로 들어온 string을 순환한다.
    2-1) "(" 인 경우
        2-1-1) 다음 인덱스에 ")"이 나온다? -> 레이저
            2-1-2) 스택에 남아있는 모든 막대기에 레이저를 추가한다. 다음인덱스까지 확인했으므로 i+=1 해줌
        2-1-2) 레이저가 아니라면 새로운 쇠막대기의 시작이므로 스택에 쇠막대기를 추가한다.
    2-2) ")" 인 경우
        쇠막대기의 끝이므로 스택에서 막대를 제거한다. 이 때 answer에 나눠진 쇠막대기 조각만큼 더해준다.

function solution(arrangement) {
  let answer = 0;
  const stack = [];
  for (let i = 0; i < arrangement.length; i++) {
    if (arrangement[i] === "(") {
      if (arrangement[i + 1] === ")") {
        //레이저인경우
        if (stack.length > 0) {
          stack.forEach((element) => {
            element.push(1);
          });
        }
        i = i + 1;
      } else {
        stack.push([]);
      }
    } else {
      answer += stack[stack.length - 1].length + 1;
      stack.pop();
    }
  }

  return answer;
}

 

2) 위의 로직과 동일한데 실제 스택에 막대기와 레이저를 직접 넣지 않는 방식으로 바꿈

막대기를 [] 배열로 표현하고, 레이저를 1로 표현했는데

막대기를 1로 표현하고, 레이저를 만날 때마다 스택의 길이만큼 answer에 더해준다.

레이저를 2번 만나면 3조각이 되니까 레이저보다 +1만큼이 더 필요한데 쇠막대를 추가할 때, answer에 +1을 해줬다.

 

코드

function solution(arrangement) {
  let answer = 0;
  const stack = [];
  for (let i = 0; i < arrangement.length; i++) {
    if (arrangement[i] === "(") {
      if (arrangement[i + 1] === ")") {
        //레이저인경우
        answer = answer + stack.length;
        i = i + 1;
      } else {
        answer = answer + 1;
        stack.push(1);
      }
    } else {
      stack.pop();
    }
  }
    return answer
}

 

생각해보고 싶은 점

생각한 방법은 똑같은데 실행시간을 고려해서 코드로 표현하는 방법을 바꾸는 연습이 필요한 것 같다.

컴퓨터 입장에서 똑같은 로직인데 더 간단하게 표현될 수 있게 하는 걸 연습하는 게 좋을 것 같다.

---

출처:

프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges