[Baekjoon] 7318_Parencodings

문제(출처: https://www.acmicpc.net/problem/7318)

---

< Parencodings >

 

문제 풀이 

 

P-sequence  -> S -> W-sequence

 

P-sequence를 보고 숫자만큼 '(' 괄호를 추가한 후 ')'를 추가한다.

W-sequence는 S를 보고 구간 사이에 있는 ')'의 개수를 구한다.

 

my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class _7318_ {// Parencodings

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int t = Integer.parseInt(bf.readLine());

		for (int i = 0; i < t; i++) {
			int n = Integer.parseInt(bf.readLine());

			st = new StringTokenizer(bf.readLine());

			String str = "";
			int cnt = 0;

			for (int j = 0; j < n; j++) {
				int num = Integer.parseInt(st.nextToken());

				while (cnt < num) {
					str += "(";
					cnt += 1;
				}
				str += ")";
			}

			Stack<Character> stack = new Stack<>();
			for (int j = 0; j < str.length(); j++) {
				if (str.charAt(j) == '(') {
					stack.add(str.charAt(j));
				} else {
					int result = 0;
					while (stack.peek() != '(') {
						result += stack.pop() - '0';
					}
					stack.pop();
					bw.write((result + 1) + " ");
					stack.add((char) (result + 1 + '0'));
				}
			}
			bw.write("\n");
		}
		bw.flush();
	}
}

변수)
t : 테스트 케이스 수
n : 입력값 개수
str : P-sequence를 변환한 괄호 문자열 
cnt : 왼쪽 괄호 개수 
stack : W-sequence를 구하기 위한 stack 

 

 테스트 케이스 수를 입력받아 테스트 케이스 수만큼 다음 과정을 반복한다.

 

1) 입력값 개수를 입력받는다.

2) P-sequence를 입력받아 입력값만큼 '('를 추가하고 ')'를 추가한다.

3) str를 탐색하며 '('면 stack에 추가한다. ')'라면 stack을 살펴보면서 '('가 나올 때까지 값을 pop 하여 더한다. 더한 값에 +1 한 값을 출력하고 stack에 다시 저장한다.

---

---