[21주차_목요일] 괄호의 값

[KodaHye]

• 사이트: 백준(BOJ)
• 문제: 괄호의 값
• 번호: 2504

### 🤔 시간복잡도 고려사항



### 💡 풀이 아이디어

[KodaHye]

🤔 시간복잡도 고려사항

• 1 ≤ 문자열의 길이 ≤ 30
• 스택을 통한 문제풀이: 최대 30 × 30 정도라고 생각함

💡 풀이 아이디어

스택을 통해 유효한 입력인지 확인하면서 결과 값 계산하기

변수	설명
Stack<Character> stack	괄호, 숫자 존재에 대한 정보 저장
Stack<Long> numStack	숫자에 대한 정보 저장

• 입력을 차례로 보면서 유요한 입력인지 확인하고, 결과 값 계산하기
  • 여는 괄호인지 닫히는 괄호인지 확인
    • 여는 괄호: 스택에 넣어주기
    • 닫히는 괄호: 유효한 입력인지 확인해야 됨
      • 괄호 뒤집어주기
      • stack을 확인하면서 숫자가 있는지 확인하고, 동일한 괄호가 나올 때까지 값 계산해주기
• 스택에서 원소들을 뽑으면서 숫자들 더해주기
  • 괄호가 하나라도 있으면 유효하지 않은 입력

스택 구현할 때, 예외 고려 잘 하기

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ 문자열의 길이 ≤ 30
• 완전탐색 가능

💡 풀이 아이디어

• 스택 이용
  • 여는 괄호 ((, [)
    • 스택에 넣기 stack.addFirst()
    • 괄호 종류에 따라 값 곱하기

    case '(':
                    stack.addFirst(cur);
                    tmp*=2;
                    break;

  • 닫는 괄호 (), ])
    • 스택 peek했을때 괄호 쌍이 맞지 않으면 0 출력후 종료
    • 해당 괄호 쌍이 처음 완성되는지 확인 후 그때 tmp값 ans에 더해주기
    • 그 외엔 값이 중복되어 곱해지지 않도록 나눠주기

    case ')':
                  if (stack.isEmpty() || stack.peekFirst() != '('){
                      System.out.println(0);
                      return;
                  }
                  if (line.charAt(i - 1) == '(') ans+=tmp;
                  tmp/=2;
                  stack.pollFirst();
                  break;

• 반복문 다 돈 후, 남은 괄호 있는지 체크

[yeongleej]

🤔 시간복잡도 고려사항

• 괄호 문자열 길이 <= 30

=> 완전 탐색 가능

💡 풀이 아이디어

• 스택 활용
• 괄호가 닫힐 때마다 현재 까지의 값을 곱해줘야 함! -> 괄호가 닫힐 때마다 tmp에 저장했던 것을 ans에 더하고, 닫힌괄호 만큼 복귀(나누기)
• 열린 괄호일 경우,
  • 스택에 저장 + tmp값에 해당 괄호값 만큼 곱해주기
• 닫힌 괄호일 경우,
  • 올바르지 않은 괄호와, 스택이 비어있다면 false
  • 올바른 괄호이면 tmp갑을 저장하고 닫힌 괄호만큼 복귀

[jewan100]

🤔 시간복잡도 고려사항

• 문자열의 길이 ≤ 30 → 딱히 신경쓰지 않아도 되는 구현

💡 풀이 아이디어

• 문자열이 올바른 괄호를 띄고 있는지 확인하는 문제
  • 기본적으로 스택이지만, 값을 계산하기 위해서 재귀로 풀이
• 반복문으로 여는 괄호 (, [가 등장할 때마다 재귀를 호출
• 내부 재귀에서 닫는 괄호 ),]가 나온다면 재귀를 빠져나와서 값을 계산
• 빠져나왔을 때, 닫는 괄호과 여는 괄호가 맞지 않을 경우, -1을 반환하여 전체 종료

private static int recursive() {
    int sum = 0; // 첫 여는 괄호가 가질 수 있는 값
    while (idx < str.length()) {
        char c = str.charAt(idx);
        // 여는 괄호라면
        if (c == '(' || c == '[') {
            char openC = c;
            idx++; // 다음 괄호를 탐색하기 위해 인덱스 증가
            int value = recursive(); // 여는 괄호였으므로 내부에 괄호가 존재하는지 확인하기 위한 재귀 호출
            // 종료 조건
            if (value == -1 || idx == str.length())
                return -1;
            char closeC = str.charAt(idx++);  // 내부 값 계산이 끝났다면 닫는 괄호 탐색
            // 올바른 괄호가 아닐 경우
            if (!isValid(openC, closeC))
                return -1;
            // value == 0은 내부에 괄호가 없었을 경우
            if (value == 0)
                sum += openC == '(' ? 2 : 3;
            else
                sum += openC == '(' ? value * 2 : value * 3;
        } else
            break; // 닫는 괄호라면 재귀 종료
    }
    return sum;
}

스택으로 풀걸...