Algorithm - CodeKata #08

1. Question

s는 여러 괄호들로 이루어진 String 인자입니다.
s가 유효한 표현인지 아닌지 true/false로 반환해주세요.

종류는 '(', ')', '[', ']', '{', '}' 으로 총 6개 있습니다.
아래의 경우 유효합니다.
한 번 괄호를 시작했으면, 같은 괄호로 끝내야 한다.
괄호 순서가 맞아야 한다.

예를 들어 아래와 같습니다.

s = "()"
return true

s = "()[]{}"
return true

s = "(]"
return false

s = "([)]"
return false

s = "{[]}"
return true

2. Try & Answer

좌절의 연속.. 너무 어려웠다..

처음에 저 괄호 string들을 각 짝에 맞게 객체화하거나

if문, includes 등을 활용하여 시도를 해보았으나

경우의 수가 너무 많아져서 해보다가 다 지워버렸다..

결국 또 구글링을 했는데 이중 for문에 if문을 넣는다던가 기타 등등 여러가지 풀이법들이 있었다.

그 중에서 가장 깔끔하고 간단 명료해보였던 코드가 있어서 그걸 이해해보기로 했다.

근데 어떻게 이렇게 풀 생각을 하신거지.... 대단...

먼저 이 분은 reduce 메서드를 쓰셨다.

reduce.... 어제 블로그에 정리를 해놨음에도 볼 때마다 낯설다... 😭

코드와 설명을 봤는데도 처음에 이해하기가 힘들어서 예시를 추가하여 다시 정리를 해보았다.

function isValid(s) {
  const obj = {
    '(' : ')',
    '[' : ']',
    '{' : '}'
  }
  
  let verify = s.split('').reduce(function (ac, cv) {
    if (cv === obj[ac[ac.length - 1]]) {
      ac.pop();
    } else {
      ac.push(cv);
    }
    return ac;
  }, []);
  return verify.length === 0;
}

console.log(isValid("[]")); // true
console.log(isValid("([})")); // false
console.log(isValid("([]}")); // false
console.log(isValid("([])"); // true

1. 우선 빈 배열 verify를 만든다.

   verify에서 ac의 초기값 = [];

2. 괄호들의 모음을 객체(obj)로 만들고, key, value 값을 각각의 괄호 짝에 맞게 지정한다.

3. 괄호 string은 split() 함수를 사용하여 배열로 만든다.

   인자 s가 ([}) 인 경우로 예시를 들겠다.
verify = [ '(', '[', '}', ')' ] 가 된다.

4. 그 다음 reduce 메서드를 돌리면,

   ac 초기값 = [] 부터 시작하고,
if 문 옆의 조건을 안쪽에서부터 해석해보면 => ac.length - 1 => -1,
ac[-1] = undefined 이므로 else의 경우로 넘어간다.
else의 경우로 가보면, 현재 값(cv) '('을 빈 배열 ac에 push, 추가한다.)
그럼 현재 ac = ['('] 인 상태

   다시 위의 if 문 옆의 조건에서,
ac.length - 1 => 0,
ac[0] = '(' 이고, obj[ac[0]] = obj['('] = ')'
cv = '[' 이므로 if 문 옆의 조건과 일치하지 않으므로 현재 cv를 배열 ac에 추가한다.
그럼 현재 ac = [ '(', '[' ] 인 상태

   다시 위의 if 문 옆의 조건에서,
ac.length - 1 => 1,
ac[1] = '[' 이고, obj[ac[1]] = obj['['] = ']'
cv = ']' 이므로 if 문 옆의 조건과 일치하므로 현재 cv를 배열 ac에서 pop, 빼준다.
그럼 현재 ac = [ '(' ] 인 상태

   다시 위의 if 문 옆의 조건에서,
ac.length - 1 => 0,
ac[0] = '(' 이고, obj[ac[0]] = obj['('] = ')'
cv = '}' 이므로 if 문 옆의 조건과 일치하지 않으므로 현재 cv를 배열 ac에 추가한다.
그럼 현재 ac = [ '(', '}' ] 인 상태

   배열 verify의 요소를 모두 reduce 메서드로 돌렸으니 배열 ac를 리턴한다.
verify.length 가 0이면 true, 아니면 false를 리턴한다.
현재 배열 ac의 length는 2이므로 최종 리턴값은 false가 된다.

Ref.
https://im-developer.tistory.com/78