Algorithm

[CodeKata] 프로그래머스 : 3.3(수), 올바른 괄호 & 튜플

ttaeng_99 2021. 3. 3. 12:45
반응형

🥋 Ooooth!! (Level 2) : 올바른 괄호

 

🧮 풀이

function solution(s){
  let stack = [];
  let stackNum = 0;
  for (let bracket of s) {
    if (bracket === '(') {
      stack.push(bracket)
      stackNum++
    }
    else {
      stack.pop();
      stackNum--
    }
  }
  return stack.length === 0 && stackNum === 0
}
  1. stack 과 stackNum 2가지 형태의 스택으로 s(괄호 문자열)의 누적값을 관리할 것이다.
  2. s(괄호 문자열)을 순회하며, '(' 라면 stack 배열 push & stackNum++, ')' 라면 stack 배열 끝을 pop() & stackNum-- 처리한다.
  3. stack이 빈 배열, stackNum이 0이라면 올바른 괄호이다!
  4. stack 배열은 ')'로 시작하는 경우, stackNum은 '())()' 과 같이 중간에 ')'이 더 있는 경우에 유효하다.

 

🖇 리뷰

function solution(s) {
  let sum = 0
  for (let i = 0; i < s.length; i++) {
    s[i] === "(" ? sum++ : sum--
    if (sum < 0) break
  }

  return sum === 0
}

* 출처 : raina94.github.io/2019/09-26-algorithm-3/

 

배열스택을 만들 필요 없이, 숫자스택만 관리한다. 괄호에 따라 +/- 처리한 뒤, 음수가 되는 순간 break 조건을 추가한 심플한 풀이다! 

🥋 Ooooth!! (Level 2) : 튜플

위 문제도 빠르게 풀었고, 다음 문제풀이를 고안하다가 바로 생각이나서 풀어보았다!! 😏😏

문제가 길지만 요약하자면, s는 n튜플의 부분집합들이 무작위로 적혀있는 문자열이다.

튜플은 중복되는 원소가 없고, 부분집합은 튜플의 {1번째}, {1번째, 2번째}, {1번, 2번, 3번째}... 의 패턴으로 생성된다는걸 이해하면 된다!

 

 

🧮 풀이

function solution(s) {
  let nTuple = 
  s.slice(2, s.length-2).split("},{").map(e => e.split(",").map(e2 => Number(e2)))
   .sort((a,b) => a.length - b.length)
   .reduce((acc, cur) => { 
    acc.push(cur.find(e => !acc.includes(e)))
    return acc;
  }, [])
  
  return nTuple;
}
  1. slice() 로 양쪽 괄호 "{{", "}}" 삭제, 그리고 이를 "},{" 로 split() 하면 부분집합들이 문자열 형태로 나눠진다.
  2. 이 부분집합을 map() 으로 재가공한다. 각 요소를, ","로 split() 한 배열과, 배열내 부분집합의 숫자값들을 Number() 로 전환한다.
  3. 이를, sort() 를 통해 배열의 길이로 정렬한다. 다음 부분집합에서, 이전에 포함되지 않은 값을 비교하기 위함
  4. 마지막으로 reduce() 처리를 한다. cur(현재값)에서 acc(누적값)에 없는 값을 찾아 누적 push() 한다.
  5. 이렇게, 누적된 acc(누적값)이 우리가 원하는 정답이 될 것이다.

 

🖇 리뷰

처음엔, 가공된 nTuple을 반복문으로 순회하며 필터를 통해 answer이라는 배열에 값을 추가해나갔다.

하지만, reduce를 적용하니 처리시간(효율성)이 확연하게 좋아졌음을 확인할 수 있었다.

반응형