우매함의 봉우리를 넘어서며 개발하면서 기록하기

백준 16637. 괄호 추가하기(삼성 A형 기출 문제)

08 Mar 2021

문제 바로가기

괄호 추가하기

문제 요약

길이가 N인 수식이 있다. 수식은 0~9 숫자와 연산자(+,-,*)로 이루어져 있다. 이 수식에서 연산자 우선순위는 모두 동일하며 수식의 계산은 항상 왼쪽부터 순서대로 이루어진다.

하지만, 수식에 괄호가 추가되면 괄호부터 먼저 계산할 수 있다. 단, 괄호 안에는 연산자가 1개만 들어갈 수 있다. 예를 들어,

3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

이때, 괄호를 적절히 추가해 식의 최대값을 구하는 프로그램을 작성하시오. 괄호의 개수 제한은 없다.

입력 조건

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

문제 풀이 포인트

삼성 SW 역량테스트 A형 기출문제 문제집 중 첫 번째 문제이다. 어느 연산자가 괄호안에 들어가는 연산자로 선택되어지는지에 따라 모든 경우의 수를 계산해보는 방식으로 해결하였으며, 순열 방식을 차용하여 연산자를 선택하였다.

StringTokenizer로 연산자와 숫자를 구분하여 배열을 저장하면 아래 그림과 같이 구성된다. BJ_16637(1)

배열의 인덱스를 잘 살펴보면 각 연산자 앞에 위치하는 숫자가 연산자와 인덱스가 동일한 것을 알 수 있다. 이런 특징을 이용하여 문제를 해결했다.

  1. 연속된 연산자의 경우 괄호에 넣을 수 없기 때문에 연산자를 선택할 때 현재 위치 +2 의 인덱스를 추가하였다.
  2. 괄호안에 들어가는 연산자가 모두 선택되었을 경우 모든 조건을 검사하여 계산식을 완성한다. (func 메소드)
    • 연산자가 괄호에 들어가는 경우 (v[i] == true): 연산자 이전에 위치한 숫자(연산자와 인덱스가 동일한 숫자)가 이미 사용되었다면 리스트에서 제거하고 괄호로 묶인 숫자들의 계산값을 리스트에 담는다.
    • 연산자가 괄호에 들어가지 않는 경우(v[i] == false): 연산자의 위치가 0이라면, 그 이전에 있는 숫자는 무조건 다른 연산자에 의해 추가되지 않으므로 리스트에 저장한다. 연산자의 위치에 0이 아니라면, 연산자 이전에 위치한 숫자(연산자와 인덱스가 동일한 숫자)는 사용하지 않았다면 리스트에 추가하고, 연산자 이후에 있는 숫자(연산자보다 인덱스가 1 높은 숫자)는 그냥 넣어준다.
  3. 괄호로 묶인 숫자들의 계산값과 묶이지 않는 숫자들을 리스트에 담은 이유는 문제의 연산 순서는 왼쪽에서부터 읽기 때문에 괄호 계산이 끝난 숫자들에 대해 괄호안에 들어가지 않는 연산자(v[i] == false)마다 앞에서부터 계산을 진행한다.

문제를 조금 어렵게 푼 감이 있다. 나중에 문제 최적화를 진행해봐야겠다.

문제 코드[JAVA]

코드 펼치기 

import java.util.*;
import java.io.*;

public class Main {
  static char[] op;
  static int[] num;
  static int n, ans= Integer.MIN_VALUE; // 출력 범위가 -2^31 ~ 2^31이기 때문에
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());
    String str = br.readLine();
    StringTokenizer st_num = new StringTokenizer(str, "+*-");
    StringTokenizer st_op = new StringTokenizer(str, "1234567890");
    
    num = new int[n - n/2];
    op = new char[n/2];
    for(int i = 0; i < num.length;i++) {
      num[i] = Integer.parseInt(st_num.nextToken());
    }
    for(int i = 0; i < op.length; i++) {
      op[i] = st_op.nextToken().charAt(0);
    }
    
    
    solve(0, new boolean[op.length]);
    System.out.println(ans);
  }
  
  private static void solve(int idx, boolean[] v) {
    if(idx >= op.length) {
      //System.out.println(Arrays.toString(v));
      func(v);
      return;
    }
    v[idx] = true;
    //현재 위치의 연산자를 괄호에 넣었을 경우에 
    //바로 다음 인덱스는 괄호에 넣지 못하기 때문에 +2
    solve(idx+2, v); 

    
    v[idx] = false;
    solve(idx+1, v);
    
  }
  private static void func(boolean[] v) {
    boolean[] numV = new boolean[num.length];
    LinkedList<Integer> num_list = new LinkedList<>();
    for(int i = 0; i < v.length;i++) {
      if(v[i]) { // 괄호
        int n = cal(i, num[i], num[i+1]); // 괄호 계산
        if(numV[i]) { // 만약 연산자 이전 위치의 숫자가 리스트에 들어가있다면
          num_list.removeLast();
        }
        numV[i] = true; numV[i+1]= true; // 숫자를 사용하였으므로 체크
        num_list.add(n);
      }
      else {
        if(i ==0) {
          num_list.add(num[0]);
          numV[i] = true;
        }else {
          if(!numV[i]) { // 연산자 이전 위치의 숫자를 사용하지 않았다면
            numV[i] = true; 
            num_list.add(num[i]); // 사용 체크 후 리스트에 담기
          }
          // 연산자 다음 위치의 경우 괄호 부분에서 체크하기 때문에 그냥 넣기
          numV[i+1] = true; 
          num_list.add(num[i+1]);
        }
      }
    }
    // 괄호 계산 이후에 남아있는 숫자가 있다면 모두 리스트로
    for(int i = 0; i < num.length; i++) {
      if(!numV[i]) {
        num_list.add(num[i]);
      }
    }
    //System.out.println(num_list);
    
    //리스트의 첫부분부터 순서대로 연산
    int sum = num_list.poll();
    for(int i = 0; i < v.length;i++) {
      if(!v[i]) {
        sum = cal(i, sum, num_list.poll());
      }
    }
    ans = Math.max(sum, ans);
    //System.out.println(sum);
    
  }

  private static int cal(int i, int num1, int num2) {
    switch(op[i]) {
    case '+':
      return num1+num2;
    case '*':
      return num1*num2;
    default:
      return num1-num2;
    }
    
  }
}

Related posts