Programmers - 올바른 괄호

---

title: Programmers - 올바른 괄호
date: 2022-07-16
tags:

• Algorithm

---

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

문제 요약

'('와 ')'로만 이루어진 문자열이 주어진다. '('가 나오면 ')'가 반드시 뒤에 나와야 한다.
문자열의 괄호가 올바른지에 대한 여부를 bool로 return한다.

문제 풀이

매우 간단한 구현 문제이다. '(' 와 ')'에 따라 값을 변경해주면 된다.
'('가 나오면 1씩 더하고, ')'는 반대로 1씩 뺐다.
')'가 더 많이 나오면 값이 -가 되며, 이는 '('가 빠져있으므로 올바른 괄호가 아니기에 바로 false를 return한다.
'('와 ')'의 개수가 같다면 값은 다시 0이 될 것이다. 0이면 true, 아니라면 false를 return하면 된다.

간단한 알고리즘이므로 효율성까지 종합하여 좋은 점수를 받으려면 많은 작업이 가능하다.
보통 반복문을 돌릴 때 문자열의 길이만큼 돌리는데, 이 값을 저장하지 않으면 매 반복문마다 .size 함수가 실행이 된다.
이 문자열의 크기는 바뀔 일이 없으므로 미리 변수 하나를 할당하면 .size 함수를 1회만 호출하여 훨씬 좋은 성능을 보일 수 있다.

string 접근에 대한 깊은 이해가 존재하지 않으나, 아마 const char * 에서의 접근보다는 느릴 것이다.
그렇기에 .data 함수를 이용하여 포인터를 이용하여 직접 확인하면 더욱 좋은 성능을 낼 수 있다.
또한, 앞에서부터 각 원소를 1회씩만 참조한다. 그러므로 포인터를 통한 배열 접근 방식보다는, 포인터만 이용하는 방식이 더 빠르다.
cpString [ i ] 보다는 * cpString ++이 성능이 좋다. 미세한 차이이지만, 이러한 간단한 알고리즘 문제에서 성능을 챙기려면 이렇게 미세한 성능이라도 챙겨야 한다.

이 외에는 최적화 과정을 고려하여 프로그램을 작성하는 것 뿐이다.
각 첨자의 비교 방법, 값이 0보다 작은지 비교 시점 등 최적화 과정에서 하나의 최적화된 프로그램으로 바뀔 수도 있고, 여러 성능이 다양한 프로그램으로 바뀔 수도 있다.
이 부분에 대한 깊은 공부를 통해 최적화를 고려하여 프로그램을 작성하면 성능 측면에서 거의 독보적일 것이다.

프로그램

#include <string>

using std :: string ;

bool solution ( string s )
{
    int iStringSize = s.size () ;
    const char * cpStirng = s.data () ;
    int iLeftParenthesisCount = 0 ;



    for ( int i = 0 ; i < iStringSize ; ++i )
    {
        if ( '(' == * cpStirng ++ )
            ++ iLeftParenthesisCount ;
        else
            -- iLeftParenthesisCount ;


        if ( iLeftParenthesisCount < 0 )
        {
            return false ;
        }        
    }


    return 0 == iLeftParenthesisCount ;
}