[알고리즘 || 프로그래머스] 🐿️ 스택/큐 : 올바른 괄호 + 처음 만난 '효율성 테스트'

알고리즘 스터디에서 같이 푼 문제인데, 

처음으로 효율성 테스트라는 친구를 발견했다.

 

//(❌)
function solution(s) {
    if (s.length < 1) return false;
    if (s.startsWith(")")) {
        return false;
    }
    while (s.includes("()")) {
        s = s.replaceAll("()", "")
    }
    return s == "" ? true : false;
}

 

이 코드는 처음 작성했던 코드인데, 

 

테스트 자체는 통과했지만, 

효율성 테스트에서 실패했다고 나왔다.

 

 

새로 만난 코테의 벽,,,,

(정확성 테스트는 예외 처리를 잘 해주면 된다)

 

비난님의 힌트1

 

비난님의 힌트2

 

비난님의 힌트를 가지고 이렇게 저렇게 한시간 정도를 스무고개를 해봤는데, 내가 하고 싶었던 방식으로는 도저히 통과가 안됐다.😿

 

 

 

 

효율성 테스트란 무엇일까?

출처 : 프로그래머스

프로그래머스 사이트에서는 '테스트 코드의 시간복잡도' 를 테스트한다고 간단히 나와있다.

지난번에 잠깐 스치듯 공부했던 빅O 가 바로 시간 복잡도를 나타내는데, 일반적인 반복문의 경우 O(N) 이 된다고만 알고 있었다.

 

효율성

알고리즘 문제를 해결하는 어떤 코드를 작성했을 때, 얼마나 효율적인지 판단할 수 있는 기준이다. 수행 시간과 사용 메모리순으로 중요하다. 성능과는 관계 없지만 가독성이 좋은 코드를 작성하는 것도 중요하다.

• 부족한 메모리는 메모리 추가를 통해 해결할 수 있지만 부족한 시간은 해결할 수 없다. 문제에 따라 수행 시간보다 사용 메모리가 더 중요한 상황이 있을 수 있지만 대부분의 경우 수행시간이 더 중요하다.
• 수행 시간은 문제의 크기와 연결되기 때문에 문제를 해결할 때는 문제의 크기를 먼저 파악하고 적합한 해결 방법을 생각해야 한다.

수행 시간

입력의 크기 N에 대해서 수행 시간을 대략적으로 표현한다. 어떤 해결 방식을 적용하기 전에 미리 시간 복잡도를 계산해보고 적합한 수행 시간이라고 판단되면 적용한다. Big O 표기법을 사용한다. 즉, 최악의 경우에 시간이 얼마나 걸릴지 알 수 있다.
O(100000000)의 경우 수행 시간은 대략적으로 1초 정도라고 생각할 수 있다. 시간 제한이 있는 문제의 경우 대략적인 대입을 통해 문제 해결에 적합하지 않은 수행 시간의 해결 방법을 제외할 수 있다.

대략 1초가 걸리는 시간 복잡도

시간 복잡도N

O(1)	-
O(logN)	-
O(N)	100000000
O(N logN)	5000000
O(N2)	10000
O(N3)	500
O(2N)	20
O(N!)	10

 

 

시간 복잡도를 고려하는 이유

ex) 우리나라 인구 5000만명중에서 한 사람을 조회하는 알고리즘 2개가 있다. 

A알고리즘: O(log n)

B알고리즘: O(n^2)

->A알고리즘은 25번, B알고리즘은 2500000000000000번의 연산을 수행한다. 

->A알고리즘은 1초도 안되는 시간이 걸린다. 

->B알고리즘은 120일 정도 걸린다..

(헉..)

 

하드웨어를 발전 속도가 매우 빠르기 때문에(무어의 법칙: 1년만에 반도체 집적률이 2배씩..)

소프트웨어의 발전 속도가 상대적으로 느리게 느껴지긴 하지만...

그럼에도 우리는 시간이란 소중한 자원을 낭비하지 않기 위해서 언제나 시간복잡도를 낮추기 위한 노력을 한다.

이러한 노력을 최적화라고 부른다.

 

 

 

 

🌴 효율성 테스트가 통과가 안되는 경우

-> 알고리즘 자체를 잘못 생각하고 있을 수도 있다. 다른 방식으로 구현하는 방법을 사용해야한다.

 

기존에 풀었던 방식을 보면

 

")" 로 시작하는 한가지 경우만 예외 처리를 한 모습을 볼 수 있다.

그리고 while 문 안에 includes, replaceAll 을 넣은게 문제였다.

includes 하고 있다면 -> replaceAll 로 () 를 한번에 없애주는데, 

없애면서 다시 s 에 재할당하는 빙빙도는 코드였다.

저렇게 전체를 돌고 도는 고차함수를 사용하면 효율성 테스트에서 통과할 수 없다!

 

 

 

여러가지 방법들을 봤는데, 대체로 '(' 갯수와 ')' 갯수를 이용한 방식으로 구현했다.

array 로 바꾼 풀이들도 있었지만,   

형변환이 일어나지 않은 가장 깔끔하다고 생각했던 풀이를 가져왔다.

(비난님꺼임 껄껄껄 이쯤되면 비난님 내 교과서)

function solution(s) {
    let count = 0;

    for (const char of s) {
        if (char === '(') count++;
        else count--;

        if (count < 0) return false;
    }
    return count === 0;
}

for 문의 of 를 이용해 문자 하나하나 탐색하는 방법인데, 탐색을 하면서 간단하게 count 에 숫자를 더하고 빼는 방식이다. 

아 그리고 return 에 falsy 값을 이용해 간단히 나타낸 것도 너무 좋다!

(나였으면 삼항연산자로 ? true : false 썼을 텐데)

 

 

아래 풀이는 다른 사람들의 풀이 중 비슷한 풀이. 

더하고 빼는 부분을 삼항연산자를 이용해서 조금 더 가독성이 좋아보인다.

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;
}

 

 

 

 

알면 알 수록 공부할 게 정말 많다!

신기한 컴터 세상!

 

 

 

 

 

 

 

내용 출처

https://velog.io/@nmrhtn7898/%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%AC%B8%EC%A0%9C-%ED%92%80%EC%9D%B4-%EC%9C%A0%EC%9D%98%EC%82%AC%ED%95%AD

[ps] 코딩 테스트 문제 풀이 유의사항

https://mimimimamimimo.tistory.com/2

<Time Complexity : 시간복잡도> 구하는 법 + 코딩 팁