[프로그래머스] Lv2 올바른 괄호

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12909

문제 설명

내 풀이

function solution(s){
    let stack = 0;
    for (let i = 0; i< s.length; i++) {
        if (stack < 0) return false
        if (s[i] == "(") stack++
        if (s[i] == ")") stack--
    }
    if (stack == 0) {
        return true
    } else {
        return false
    }
    // while(stack >= 0 && i < s.length) {
    //     if (s[i] == "(") stack++
    //     if (s[i] == ")") stack--
    //     i++
    // }
    // if (stack == 0) {
    //     return true
    // } else {
    //     return false
    // }
}

Stack 자료구조를 활용해서, "("인 경우 ++, ")"인 경우 --을 하여 문제를 풀었다.

반복문 for을 돌리면서 만약 stack이 0보다 작아지는 경우 false를 하여 올바른 괄호처리가 되지 않았다고 return 진행

두번째로 반복문이 종료 후, stack이 정확하게 0이면 true, 아니면 false 처리를 진행했다.

그리고 왜 while 문일때랑 for 문일 때 시간 복잡도 차이가 나는가?? 이 부분은 아직 해결 못함

for 문일 때가 효율성 test에서 조금 더 좋은 모습을 보여줬다.

다른 사람의 풀이

function solution(s){
    let cum = 0
    for (let paren of s) {
        cum += paren === '('? 1: -1
        if(cum < 0) {
            return false
        }
    }
    return cum === 0? true: false;
}

비슷하게 풀었지만, 삼항연산자를 사용하여 더욱 깔끔하게 코드를 작성한 모습

오늘 배운 점

• 삼항 연산자를 조금 더 추가로 사용하자.
• for문과 while문의 차이점이 뭘까

아무래도 조건을 두 개 주다보니 그러한 점에서 차이가 있을 수 있다.

큰 차이는 없지만 추후에는 조사를 조금 더 해봐야겠다.

GPT한테 물어본 결과

그러나, while 문에서 가능한 성능 문제는 다음과 같습니다

1. 조건 평가 순서: while 루프에서는 두 조건 stack >= 0과 i < s.length를 모두 확인합니다. 이 조건들이 for 루프의 단일 조건 i < s.length보다 추가적인 계산을 필요로 할 수 있습니다. 하지만 이 차이는 매우 미미하며, 일반적으로 이 정도 차이가 큰 성능 문제를 일으키지는 않습니다.
2. 컴파일러/인터프리터 최적화: JavaScript 엔진에 따라 for 루프와 while 루프를 다르게 최적화할 수 있습니다. 어떤 엔진은 특정 유형의 루프에 대해 더 효율적인 최적화를 수행할 수 있으며, 이는 실행 성능에 영향을 미칠 수 있습니다.
3. 기타 요인: JavaScript 엔진의 특정 구현, 메모리 관리, 가비지 컬렉션 등과 같은 다른 요인들이 성능에 영향을 미칠 수 있습니다.

그러나 일반적으로, for와 while 루프 사이에 이렇게 큰 성능 차이가 나는 것은 드문 경우입니다. 효율성 테스트에서의 차이는 주어진 테스트 케이스의 특성, 사용된 JavaScript 엔진, 혹은 다른 실행 환경의 차이 때문일 수 있습니다. 코드 자체에서 명확한 성능 차이의 원인을 찾기는 어렵습니다.