[한양대 HCPC 2023] Yeah, but How?

🔐 핵심 풀이 방법

해당 문제의 핵심 풀이 방법은 다음과 같다.

1. input으로 주어지는 수식은 완벽한 수식이다.
2. 제약조건이 2 <= |S| <= 200000 이므로 우선 최소값인 2가 올 경우 주어지는 값은 ()가 된다.
3. S가 200000개의 문자일때 수식의 길이는 500000이하여야 하므로 가능하면 수식을 길게 하지 않는다.

위와 같은 조건을 통해 아래 가설을 만들고 적용하였다.

1. 스택을 만들고 input의 문자열을 담는다.(deque활용)
2. 스택의 길이가 2인 경우 (1+1)을 반환한다.(빠른 종료를 위함)
3. 맨 앞의 두개 문자를 꺼내어 비교후 결과에 담는다.
   • ')''('인 경우
     - ")+"를 추가한다.
   • '('')'인 경우
     - "(1"을 추가한다.
   • 그 외
     - 앞의 문자를 추가한다.
4. 추가 후에는 두번째 문자를 다시 스택의 앞에 넣는다.
5. 반복을 하다가 길이가 2개가 되면 반복을 종료하고 두번째문자를 결과에 추가한다.

⏱️ 시간 복잡도

해당 문제의 시간 복잡도는 O(n)이다. 따라서 최대길이의 문자가 주어져도 타임아웃이 나지 않기 때문에 단순 구현 문제라고 할 수 있다.

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();

		System.out.println(Solution(input));
	}

	public static String Solution(String input) {
        Deque<Character> stack = new ArrayDeque<>();
        int inputlength = input.length();

        if (inputlength == 2) {
            return "(1+1)";
        }

		for (int i = 0; i < input.length(); i++) {
			stack.offerLast(input.charAt(i));
		}

		boolean finish = true;
		StringBuilder answer = new StringBuilder();
		while(finish) {
			if (stack.size() == 2) {
				finish = false;
			}

			
			char L = stack.pollFirst();
			char R = stack.pollFirst();

			if (L == ')' && R == '(') {
				answer.append(L);
				answer.append('+');
			}
			else if (L == '(' && R == ')') {
				answer.append(L);
				answer.append('1');
			} else {
				answer.append(L);
			}
			stack.offerFirst(R);
			if (finish == false) answer.append(R);
		}
		String res = String.valueOf(answer);
		return res;
  	}
}