백준 10799 - 쇠막대기

 

올바른 괄호문제를 응용한 문제이다. 

 

해결방법 

 

- (하나당 쇠막대기 1개로 간주 스택에 push() 

 

- )닫는괄호 등장시 

   - 바로 인접한 여는 괄호 존재시 -->레이저로 간주 총 길이에 스택의 사이즈(총 쇠막대기)만큼 + (2등분 되므로 기존 쇠막대기 만큼 +됨) 

   - 인접한 여는 괄호가 없을 시 -->쇠막대기 끝을 의미 쇠막대기 하나 없어짐

 

-->>바로 인접한 여는괄호인지 아닌지를 판단하는게 중요하다.

 

풀이 1

  public static void main(String[] args) throws Exception {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String input = br.readLine();
        Stack ss = new Stack();
        int result=0;
        int presize=0;

        for(char a: input.toCharArray()){
            if(a ==')'){
                ss.pop();
                //()라면 (는넣자마자 pop 사이즈 일정
                //-1해준것은 ()에 (한쪽 추가시에도 size증가해서
                if(presize-1 == ss.size()){
                    result += ss.size()-1; //size()만큼 추가하고 레이저에 (때문에 result에 ++된거 
                                           //하나 빼준 것
                }

            }else {
                ss.push(a);
                result++;
                presize = ss.size();
            }

        }
        bw.write(result+"");
        bw.flush();
        bw.close();
    }

()를 제외한 기존의 괄호크기를 저장해서 

레이저인지, 쇠막대기의 끝인지 확인하는 방법을 선택했다.

여는괄호 일때, 스택에 여는괄호를 저장하면서, presize = 스택사이즈 저장 

닫는괄호 등장시 

            - ()로 바로 사라짐 따라서 기존 사이즈 변화 없음 레이저 발동 -->단 레이저의 (로 presize++됨 따라서 presize-1와 닫는괄호로 하나 pop된 스택 사이즈 비교 

           - 여는괄호 없이 닫는괄호만 등장시 --pop된 사이즈가 presize보다 작아짐 ---> 쇠막대기 끝 레이저 발동x