210825 괄호 짝꿍 찾기

문제

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

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

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

s = "()"
return true

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

s = "(]"
return false

s = "([)]"
return false

s = "{[]}"
return true

이번에 새로 배운 개념

ADT (Abstract Data Type)

추상 자료형
어떤 데이터의 구체적인 구현 방식은 생략한 채,
데이터의 추상적 형태와 그 데이터를 다루는 방법

스택 Stack

1. 데이터를 집어넣을 수 있는 선형(linear) 자료형
2. LIFO(Last In First Out) : 나중에 집어넣은 데이터가 먼저 나온다
3. 데이터가 들어가는 곳과 나오는 곳이 동일하다

• 데이터를 집어넣는 push
• 데이터를 추출하는 pop
• 맨 나중에 집어넣은 데이터를 확인하는 peek

큐 (Queue)

1. 데이터를 집어넣을 수 있는 선형(linear) 자료형
2. FIFO(First In First Out) : 먼저 집어넣은 데이터가 먼저 나온다
3. 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer)로 사용된다

• 데이터를 집어넣는 enqueue
• 데이터를 추출하는 dequeue

문제이해

따라서 데이터를 넣고 빼는 곳이 동일한 선형 자료형 stack의 배열 만들고

여는 괄호가 나오면 → push해서 데이터가 추가하고
닫는 괄호가 나오면 → pop으로 데이터를 꺼내면서 반환된 값은 배열 객체의 키값으로 지정한다

따라서 정상적인 괄호만나면 최종적으로 남는것이없다

(())() 이처럼 여는 괄호가 더 많은 경우
스택에 남게 되서 비어있지 않으면 false

(()))( 처럼 순서가 맞지 않아도
닫는괄호가 나오면 자기 짝을 pop 처리를 해줘야되는데
) 이 괄호가 나왔을 때에는 해당하는 여는괄호 (짝) 이 stack에 없기 때문에
정상적인 괄호가 아니라 false가 된다
따라서 스택의 제일 상단에 짝이 있어야 pop을 해줄 수 있다

정답

function isValid(s) {
    let result = true;
    let stack = [];
    let map = {
        '(': ')',
        '[': ']',
        '{': '}'
    }

    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(" || s[i] === "[" || s[i] === "{") {
            stack.push(s[i]);
        } else {
            let s_key = stack.pop();
            if (s[i] !== map[s_key]) 
                result = false;
            }
        }
    if (stack.length !== 0) 
        result = false;
    return result;
}

코드설명

1. isValid 함수에서 사용할 값 변수로 지정하면서 초기값 설정
   • 입력한 괄호가 true인지 false인지 결과값을 담을 변수 result에 초기값으로는 true 로 설정했다
   • stack 자료형의 빈 배열 stack
   • 여는 괄호가 key, 닫는 괄호가 value인 객체 map

let result = true;
// 이후에는 정상적이지 않은 괄호형태만 false로 지정하도록 한다
let stack = [];
let map = {
  '(': ')',
  '[': ']',
  '{': '}'
 }

2. 문자열의 처음부터 끝까지 요소를 확인할 것이기 때문에 for문 이용

for (let i = 0; i < s.length; i++) {
}

3. 만약 여는 괄호가 나오면 stack 배열에 해당하는 값 push 해준다

if (s[i] === "(" || s[i] === "[" || s[i] === "{") {
    stack.push(s[i]);
}

4. 그렇지 않다면 (=닫는괄호가 나온다면)
   • 현재 stack 배열에서 가장 바깥에 담긴 값을 s_key 라는 변수에 담고
   • map 객체에서 s_key의 키값 (=닫는괄호) 이 해당하는 해당하는 괄호 (=닫는괄호)와 동일하지 않으면 정상적이지 않은 괄호형태라 result에는 false라는 값이 담긴다

예를 들어 stack 배열에는 "(" 가 있고, 해당하는 값이 "]"이라면
s_key = "("
map[s_key] = ")"
s[i] = "]"
이기 때문에 result 에는 false 값이 들어간다

else {
    let s_key = stack.pop();
    if (s[i] !== map[s_key]) 
        result = false;
    }

5. 인자로 넣어준 문자열의 처음부터 끝까지 for문을 통해 모두 확인했을 때
   stack 배열에 요소가 남아있다면 정상적인 괄호 형태가 아니므로 false가 된다

if (stack.length !== 0) result = false;

다른 정답

function isValid(s) {
    let arr = s.slice();
    for (let i = 0; i < s.length / 2; i++) {
        for (let j = 0; j < s.length; j++) {
            let match = arr[j] + arr[j + 1];
            if (match === '()' || match === '{}' || match === '[]') {
                arr = arr
                    .replace(arr[j], '')
                    .replace(arr[j + 1], '');
            }
        }
    }
    if (arr === '') 
        return true;
    else 
        return false;
    }

코드설명

1. 인자로 받은 문자열을 slice() 메서드를 이용해 배열로 만들어준다

문자열에 split()을 해도 동일한 문자열인데 무슨차이일까...
arr대신에 s자체로 코드를 작성하면 틀린다고 나온다

let arr = s.slice();

2. 문자 2개를 비교할 거라 for문 두개를 돌린다
   • for문 2개 중 하나는 범위를 i < s.length / 2; 라고적어주는데 범위를 동일하게 s.length 라고 잡아줘도 잘 작동한다
   • 찾아보지는 않았지만 내 생각에는 match가 동일한 괄호로 열고 닫아주면 두개 모두 삭제하기 때문에 굳이 처음에 비교하는 바깥의 for문의 범위를 s.length 까지 지정할 필요가 없어서인 것 같다 (속도차이)

• i < s.length

• i < s.length / 2

for (let i = 0; i < s.length / 2; i++) {
    for (let j = 0; j < s.length; j++) {}
}

3. 해당하는 요소와 그 다음 요소의 값을 match 라는 변수에 담는다

let match = arr[j] + arr[j + 1];

4. 만약 match가 열고 닫으면 해당하는 값과 그 다음 값은 삭제한다

if (match === '()' || match === '{}' || match === '[]') {
    arr = arr
        .replace(arr[j], '')
        .replace(arr[j + 1], '');
}

for문을 이용해서 괄호 열고 닫는거를 세트로 삭제하고 나면
{[]}() → {일 때 } 만나서 삭제 → [일 때 ] 만나서 삭제 → ( 일 때 ) 만나서 삭제

5. for문을 통해 문자열 s 전체를 돌았을 때
   arr 배열에 요소가 남아있으면 정상적인 괄호 형식이 아니라 false가 리턴되고
   arr 배열에 남아있는 요소가 없으면 정상적인 괄호형태라 true가 리턴이 된다

if (arr === '') return true;
else return false;