Algorithm - BOJ 16637 괄호 추가하기

오늘도 습하디 습한 날

---

BOJ 16637 괄호 추가하기

문제
길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 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은 홀수이다.

출력
첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 2^31보다 작고, -2^31보다 크다.

코드

public class B16637 {
	static long max = Long.MIN_VALUE;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		char[] ca = br.readLine().toCharArray();
		
		Deque<Character> deq = new ArrayDeque<>();
		search(ca, 0, false, deq);
		
		System.out.println(max);
		
	}
	static void search(char[] arr, int index, boolean flag, Deque<Character> deq) {
		Deque<Character> nd = new ArrayDeque<>(deq);
		if(index == arr.length) {
			char c;
			long res = nd.poll() - '0';
			while(!nd.isEmpty()) {
				c = nd.poll();
				if(c == '+'){
					res += nd.poll() - '0';
				} else if(c == '-') {
					res -= nd.poll() - '0';
				} else {
					res *= nd.poll() - '0';
				}
			}

			max = Math.max(max, res);
			return;
		}
		
		
		boolean odd = index % 2 != 0;
		if(odd) { // 연산자
			if(flag) { // 괄호
				int left = nd.pollLast() - '0';
				int right = arr[index + 1] - '0';
				if(arr[index] == '+') nd.add((char) ((left + right) + '0'));
				if(arr[index] == '-') nd.add((char) ((left - right) + '0'));
				if(arr[index] == '*') nd.add((char) ((left * right) + '0'));
				
				search(arr, index + 2, false, nd);
			}else {
				nd.add(arr[index]);
				search(arr, index + 1, flag, nd);
			}
		}
		else { // 피연산자
			nd.add(arr[index]);
			search(arr, index + 1, true, nd);
			search(arr, index + 1, false, nd);
		}
	}
}

설명

음...딱히 잘 짠 코드라고는 못할 것 같다.
괄호에는 연산자가 단 1개만 들어갈 수 있다.
그래서 Deque에 연산자와 피연산자를 넣을 때, 피연산자를 기준으로 괄호를 채울지 말지 분기를 나누어 주었다.
괄호를 채울지 말지를 flag라는 boolean 변수로 두어 재귀함수를 호출할 때, 다음 요소를 생각하여 true/false로 바꾸어 재귀하면 된다.

모든 요소를 다 돌았다면 deque가 비워질 때까지 각 연산자에 맞는 계산을 하면 되고, 마지막에 그 값이 최대인지 확인하면 된다.

---

알고리즘 문제 해결

싸피에서 알고리즘 문제를 풀기 위한 특강을 했다.
여기서 중요한 부분을 정리해 보고자 한다.

해결 과정

1. 문제를 읽고 이해한다.
   1회 : 빠르게 읽으면서 문제 유형 파악
   2회 : 유형을 생각하면서 다시 읽기 (제약사항, 입력 크기 등을 통해 시간복잡도와 공간복잡도를 어림)
   3회 : 꼼꼼하게 읽으면서 다시 읽기 (조건 특히 조사[~도, ~만], 히든 케이스, 기능 파악)
2. 문제를 익숙한 용어로 재정의
3. 어떻게 해결할지 계획을 세운다.
   가능하게 풀어쓰거나 의사 코드
4. 계획을 검증한다.
   가능한 작은 크기의 데케로 검증
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.
   최적화

코테를 잘 보는 TIP

1. 내가 문제 푸는 화면을 녹화한다.
2. 알고리즘 오답노트(문제, 소요시간, 시도횟수, 유형, 아이디어, 실수)