๐ŸŒžAlgorithm/๐Ÿ”ฅBaekjoon

[Baekjoon] 16654_Generalized German Quotation

๋ฟŒ์•ผ._. 2025. 8. 22. 10:22
๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/16654)

< Generalized German Quotation >

 

๋ฌธ์ œ ํ’€์ด 

 

์ž…๋ ฅ ๋ฌธ์ž์—ด ์‹œ์ž‘์ด '>>' ์ด๊ฑฐ๋‚˜ '<<'์ด๋”๋ผ๋„ ๋ฌด์กฐ๊ฑด '['๋กœ ๋ฐ”๊พผ๋‹ค. ์‹œ์ž‘์„ ๊ธฐ์ค€์œผ๋กœ ํ•˜์—ฌ ๋’ค๋ฅผ '[' ๋˜๋Š” ']'๋กœ ๋ฐ”๊พผ๋‹ค.

<<>><<<<>>>>

 

์ž…๋ ฅ์ด ์œ„์™€ ๊ฐ™๋‹ค๋ฉด ์‹œ์ž‘์ธ '<<'์„ '['๋กœ ๋ฐ”๊พผ๋‹ค. ์ด๊ฒƒ์„ ๊ธฐ์ค€์œผ๋กœ ๋ฐ”๊พธ๋ฉด ๋‹ค์Œ์ฒ˜๋Ÿผ ๋œ๋‹ค.

<< >> << << >> >>
[     ]     [    [    ]    ]

 

 

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.ArrayList;
import java.util.Stack;

public class _16654_ { // Generalized German Quotation

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

		String str = bf.readLine();

		ArrayList<Character> list = new ArrayList<>();
		Stack<Character[]> stack = new Stack<>();

		for (int i = 0; i < str.length(); i += 2) {
			if (stack.isEmpty()) {
				stack.add(new Character[] { str.charAt(i), '[' });
				list.add('[');
			} else {
				if (stack.peek()[0] == str.charAt(i)) {
					stack.add(new Character[] { str.charAt(i), stack.peek()[1] });
					list.add(stack.peek()[1]);
				} else {
					stack.pop();
					list.add(']');
				}
			}
		}

		if (stack.isEmpty()) {
			for (int i = 0; i < list.size(); i++) {
				bw.write(list.get(i));
			}
		} else {
			bw.write("Keine Loesung");
		}
		bw.flush();
	}
}
๋ณ€์ˆ˜)
list : ๋ณต์›ํ•œ ๋ฌธ์ž์—ด
stack : ์˜ฌ๋ฐ”๋ฅธ ๋”ฐ์˜ดํ‘œ์ธ์ง€ ํ™•์ธํ•˜๊ธฐ ์œ„ํ•œ Stack

 

๋ฌธ์ž์—ด์„ ์ž…๋ ฅ๋ฐ›๋Š”๋‹ค. ๋ฌธ์ž์—ด์„ ํƒ์ƒ‰ํ•˜๋ฉด์„œ ๋‹ค์Œ ๊ณผ์ •์„ ๊ฑฐ์นœ๋‹ค.

 

1) stack์ด ๋น„์–ด์žˆ๋‹ค๋ฉด ์ƒˆ๋กœ์šด ๊ด„ํ˜ธ๊ฐ€ ์‹œ์ž‘๋˜๋Š” ๊ฒƒ์ด๋ฏ€๋กœ stack์— [๋ฌธ์ž, '[' ] ์ €์žฅ ๋ฐ ArrayList์—๋„ '[' ์ €์žฅ

2) stack์ด ๋น„์–ด์žˆ์ง€ ์•Š๋‹ค๋ฉด stack์˜ peek ๊ฐ’๊ณผ ์ผ์น˜ํ•˜๋Š” ๋ฌธ์ž์ธ์ง€ ํ™•์ธ 

2-1) ์ผ์น˜ํ•˜๋‹ค๋ฉด ์•ž๊ณผ ๊ฐ™์€ ๊ด„ํ˜ธ๊ฐ€ ์ €์žฅ๋˜์–ด์•ผ ํ•จ

2-2) ์ผ์น˜ํ•˜์ง€ ์•Š๋‹ค๋ฉด ๋‹ซ๋Š” ๊ด„ํ˜ธ์ด๋ฏ€๋กœ stack pop ๋ฐ list์— ']' ์ €์žฅ

 

์ตœ์ข… stack์ด ๋น„์–ด์žˆ๋‹ค๋ฉด ArrayList๋ฅผ ์ถœ๋ ฅํ•˜๊ณ , ๋น„์–ด์žˆ์ง€ ์•Š๋‹ค๋ฉด ์˜ฌ๋ฐ”๋ฅธ ๋”ฐ์˜ดํ‘œ๊ฐ€ ์•„๋‹ˆ๋ฏ€๋กœ "Keine Loesung"์„ ์ถœ๋ ฅํ•œ๋‹ค.