439. Ternary Expression Parser

1271 단어

메서드1: O(N^2)


사고방식이 매우 직관적이다. 문제를 어떻게 줄이는가(Decrease and Conquer)
  • outtermost의 표현식을 찾습니다
  • 두 개의subexpress를 찾았고 하위 문제는 귀속으로 해답을 구했다

  • 주요 질문:
  • 귀속이라면 베이스는?
  • 질문 마크가 없으면 바로 돌아갑니다
  • 질문 마크 1개만 있으면 직접 판단할 수 있다

  • 어떻게 outtermost의 표현식을 찾습니까?제목 정보'The conditional expressions group right-to-left'를 이용하여 맨 왼쪽에 있는question mark는 outter most입니다
  • 질문 마크에 대응하는colon을 어떻게 찾습니까?pair matching 질문: 1) counting 2) Stack

  • 복잡도: Question mark를 찾을 때 문자열을 반복해야 하기 때문에 O(N^2)

    방법2: 최적화


    사고방식: 표현식 평가와 유사하게 두 개의 stack, 하나의conditionStack, 다른operantStack
    1.  condition: 
      conditionStack 
    2.  colon:
      conditionStack 
      1)  condition T: skip to corresponding colon( )
      2)  condition F:operantStack , 
    3.  
      operant 
    
     operantStack.peek()
    

    주요 질문:
    어떻게 표현식의 두 번째 부분을 뛰어넘습니까?pair matching을 이용한counting
    // skip i to corresponding colon position
    int cnt = 1;
    while (i + 1 < expression.length()) {
      if (expression.charAt(i + 1) == ':' && --cnt == 0) break;
      else if (expression.charAt(i + 1) == '?') cnt++;
      i++;
    }
    

    주의해야 할 것은 i+1에 대한 판단이지 i가 아니다. 왜냐하면 외부 순환은 i++
    시간 복잡도: 문자열을 한 번만 훑어볼 수 있기 때문에 O(N)

    좋은 웹페이지 즐겨찾기