[Leetcode] 20. Vaild Parentheses

Identifying the Problem

주어진 괄호 문자열이 올바르게 열고 닫혀야된다.

[ ) 같은 경우나, [ ( ] ) 경우는 false 값을 return 해야 한다.

Organizing thoughts

괄호가 양파를 속에서 까는 것 처럼 구상했다.

이를 위해 STACK 자료구조를 사용했다.

가장 깊은 괄호를 제거하다 보면 true 인지 false 인지 구분이 되기 때문이다.

예를 들자면, < ( [ ] ) > 에서 가장 깊은 괄호는 [] 이고

1 step 에서 []를 제거하면 <()>

2 step 에서 ()를 제거하면 <>

3 step 에서 <>을 제거하면 아무것도 남지 않는다.

 

1. 애초에 true가 되지 않는 경우

1-1 괄호가 아예 없거나

1-2 문자열의 길이가 홀수인 경우이다.

 

2. 나머지의 경우는 짝수의 경우이다.

2-1 stack에 문자열을 하나씩 집어넣다가

2-2 짝이 맞는 괄호가 있으면 마지막괄호와 들어온 괄호를 제거하고

2-2-1 아스키코드를 활용해서 두 괄호 값의 차가 일정값이면 짝이 맞는 것이다.

2-3 index를 마지막 괄호 이전으로 놓는다.

3. stack에 뭐가 남아있으면 fasle, 다 지워졌으면 true 를 return 한다.

Sourcecode

bool isValid(char * s)
{
	int n = strlen(s); 
	int t = 1; //스택의 index
	char stack[10000] ={0,}; //스택
	int gap=0;

	if(n==0) return true; //1-1
	else if(n%2 ==1) return false; //1-2
	
   	 else //2
             {
  	 	for(int i=0; i<n; i++)
        		{
   			stack[t] = *(s+i); //2-1
    			gap = stack[t] - stack[t-1];
    		
			if( 0<gap && gap<3   &&i>0) //[]같은 경우 gap 값이 2가 된다.
   	 		{
    				stack[t]=0; //2-2
   	  			stack[t-1]=0;
     				t= t-2; //2-3
  			}
            
  			t++;
 	 	}
	}
    
    
    if(stack[1] == 0) return true;
    else return false;
}

Mistake

모든 경우의 수를 생각하며 패턴을 찾는 데에 집중했다.

바로 옆과 끝의 관계에 따라 코드를 짜봤는데 너무 복잡하고, test case 에서 걸러지는 경우 더 코드가 복잡해졌다.

어떻게든 혼자서 풀려고 노력했는데 도저히 생각이 안나 solution을 참고했고, 의외로 단순한 문제였다.

도저히 안풀리는 것은 solution과 다른 사람의 코드를 보고 빨리 진행하는 것이 좋을 듯 하다.

 

New things learned

• Stack 자료구조 Last In First Out 구조로 프링글스 통안에 자료를 집어넣고 뺀다고 생각하면 된다.