#AIL_23.10.13 // Programmers_올바른 괄호

## AIL_올바른 괄호

 

문제 설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어"()()" 또는 "(())()" 는 올바른 괄호입니다.")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항 문자열 s의 길이 : 100,000 이하의 자연수 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

제한사항
문자열 s의 길이 : 100,000 이하의 자연수문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

입출력 예 설명
입출력 예 #1,2,3,4 문제의 예시와 같습니다.

---

---

## solution.JavaScript

 

1. 문제의 접근 방식_Stack을 사용하지 않고 ()괄호의 개수를 추적하여 문제해결하기 

 

1) 변수 ''sum을 사용하여 열린 괄호 ( 의 개수과  닫힌 괄호 )의 개수를 추적하기

- 'sum' 변수를 0으로 초기화

 

2) 문자열 's'를 순회하면서 각 문자 검사하기 

-현재 문자가 ( 인 경우, 'sum'을 1 증가 시키기 _ 열린 괄호가 하나 더 열렸다는 것을 의미 

-현재 문자가 ) 인 경우, 'sum'을 1 감소 시키기 _ 닫힌 괄호가 하나 더 닫혔다는 것을 의미 

 

3) 문자열을 모두 순회한 후, 'sum'의 값과 문자열 길이의 절반 (`s.length/2`)를 비교하기 

- 'sum'의 값이 음수인 경우, 이는 닫힌 괄호가 먼저 나오거나, 열린 괄호와 대응되는 닫힌 괄호가 부족한 경우의 수를 나타냄. 이경우 올바를 괄호가 아니므로 'false'를 반환

- 'sum' 값이 문자열 길이의 절반과 같거나 큰 경우, 이는 열린 괄호의 수가 닫힌 괄호의 수를 초과한 경우로 나타냄. 이 경우 열린 괄호와 닫힌 괄호의 짝이 맞지 않으므로 'false'를 반환 

 

4) 마지막으로 'sum'이 0인 경우에만 함수가 'true'를 반환함. 이는 모든 괄호가 정확화게 대응되었다는 것을 의미

---

2. 문제풀이_수정 전: 이유를 알 수 없는 시간 초과 오류발생 

function solution(s){
    let sum = 0;
    for (let char of s) {
        if (sum < 0) {
            return false;
        }


        if (char === "(") {
            sum += 1;
        } else {
            sum -= 1;
        }
    }

    if (sum !== 0) return false;

    return true;
}

---

3. 문제풀이_수정 후 : 코드 수정 후 시간초과 오류 문제해결

function solution(s){
    answer = true;

    let sum = 0;
    for (let char of s) {
        if (sum < 0) {
            return false;
        }

        if (sum > (s.length/2)) {
            return true;
        }

        if (char == "(") {
            sum += 1;
        } else {
            sum -= 1;
        }
    }

    if (sum !== 0) return false;

    return answer;
}

+추가된 부분:  if (sum > (s.length/2)) { return true; }

현재 합이 나머지 보다 크면 바로 실행을 끝낼 수 있음 

---

4. 다른사람의 문제풀이 및 접근방식 분석_스택을 이용하여 쌍을 검사, () 괄호가 적절한 순서로 등장해야만 올바른 괄호 문자열로 판단 

function solution(s){
    let stack = [];
    
    for(let x of s){
        if(x === '(' ){
            stack.push(x)
        } else {
            stack.pop()
        }
    }
    return stack.length === 0;
}

 

1) 빈스택을 생성

2) 문자열 's'를 순회하면서 각 문자를 검사 

3) 열린 괄호 ( 를 만나면 스택에 해당 괄호를 추가 (push)

4) 닫힌 괄호 ) 를 만나면 스택에서 가장 최근에 추가한 괄호를 제거(pop) 이는 괄호의 쌍을 확인하는 과정임

5) 문자열을 모두 검사한 후, 'true'를 반환하고, 스택에 남아 있는 괄호가 있다면 올바르지 않은 괄호 문자열이므로 'false'를 반환함

---

5. 두 방식의 장단점

 

1) 스택(Stack)을 사용하지 않은 방식

 

장점_//

• 코드가 간결하고 직관적이며 , 스택을 사용하지 않아 코드가 간소화됨 
• 스택을 사용하지 않기 때문에 메모리 사용량이 적어 효율적일 수 있음 

 

단점_//

• 스택을 사용하지 않고 직접 괄호 쌍을 추적하기 때문에 코드 읽기가 어려움
• 잘못된 괄호 문자열의 경우 불필요한 연산을 계속하게 되는 경우가 있을 수 있음

 

 

2) 스택(Stack)을 사용한 방식

 

장점_ //

• 코드의 가독성이 높고 괄호의 쌍을 추적하기 용이함
• 잘못된 괄호 문자열을 더 빠르게 탐지할 수 있음

 

단점_//

• 스택을 사용하기 때문에 메모리 사용량이 많을 수 있음
• 코드가 약간 더 복잡할 수 있음

---

결론: 스택(Stack)이 일반적이고 직관적인 방법이기 때문에  이 방법을 더 선호함, 코드의 가독성과 유지 보수성이 중요한 상황이라면 스택(Stack)을 사용하는 방식이 더 적합할 수 있음.