01-10 04:27
Recent Posts
Recent Comments
๊ด€๋ฆฌ ๋ฉ”๋‰ด

miinsun

[BAEKJOON] ๋ฐฑ์ค€ ์Šคํƒ/ํ 9012 :: ๊ด„ํ˜ธ JAVA ๋ณธ๋ฌธ

Algorithm/Baekjoon

[BAEKJOON] ๋ฐฑ์ค€ ์Šคํƒ/ํ 9012 :: ๊ด„ํ˜ธ JAVA

miinsun 2022. 3. 14. 22:06

 

๐Ÿ’ฌ  ๋ฌธ์ œ ์„ค๋ช…

๊ด„ํ˜ธ ๋ฌธ์ž์—ด(Parenthesis String, PS)์€ ๋‘ ๊ฐœ์˜ ๊ด„ํ˜ธ ๊ธฐํ˜ธ์ธ ‘(’ ์™€ ‘)’ ๋งŒ์œผ๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋Š” ๋ฌธ์ž์—ด์ด๋‹ค.
๊ทธ ์ค‘์—์„œ ๊ด„ํ˜ธ์˜ ๋ชจ์–‘์ด ๋ฐ”๋ฅด๊ฒŒ ๊ตฌ์„ฑ๋œ ๋ฌธ์ž์—ด์„ ์˜ฌ๋ฐ”๋ฅธ ๊ด„ํ˜ธ ๋ฌธ์ž์—ด(Valid PS, VPS)์ด๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค.

ํ•œ ์Œ์˜ ๊ด„ํ˜ธ ๊ธฐํ˜ธ๋กœ ๋œ “( )” ๋ฌธ์ž์—ด์€ ๊ธฐ๋ณธ VPS ์ด๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค.
๋งŒ์ผ x ๊ฐ€ VPS ๋ผ๋ฉด ์ด๊ฒƒ์„ ํ•˜๋‚˜์˜ ๊ด„ํ˜ธ์— ๋„ฃ์€ ์ƒˆ๋กœ์šด ๋ฌธ์ž์—ด “(x)”๋„ VPS ๊ฐ€ ๋œ๋‹ค.
๊ทธ๋ฆฌ๊ณ  ๋‘ VPS x ์™€ y๋ฅผ ์ ‘ํ•ฉ(concatenation)์‹œํ‚จ ์ƒˆ๋กœ์šด ๋ฌธ์ž์—ด xy๋„ VPS ๊ฐ€ ๋œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด “(())()”์™€ “((()))” ๋Š” VPS ์ด์ง€๋งŒ “(()(”, “(())()))” , ๊ทธ๋ฆฌ๊ณ  “(()” ๋Š” ๋ชจ๋‘ VPS ๊ฐ€ ์•„๋‹Œ ๋ฌธ์ž์—ด์ด๋‹ค. 

์—ฌ๋Ÿฌ๋ถ„์€ ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ๊ด„ํ˜ธ ๋ฌธ์ž์—ด์ด VPS ์ธ์ง€ ์•„๋‹Œ์ง€๋ฅผ ํŒ๋‹จํ•ด์„œ ๊ทธ ๊ฒฐ๊ณผ๋ฅผ YES ์™€ NO ๋กœ ๋‚˜ํƒ€๋‚ด์–ด์•ผ ํ•œ๋‹ค. 

 

๐Ÿ”จ  ์ž…์ถœ๋ ฅ ์˜ˆ

์ž…๋ ฅ 

  • ์ž…๋ ฅ ๋ฐ์ดํ„ฐ๋Š” ํ‘œ์ค€ ์ž…๋ ฅ์„ ์‚ฌ์šฉํ•œ๋‹ค.
  • ์ž…๋ ฅ์€ T๊ฐœ์˜ ํ…Œ์ŠคํŠธ ๋ฐ์ดํ„ฐ๋กœ ์ฃผ์–ด์ง„๋‹ค.
  • ์ž…๋ ฅ์˜ ์ฒซ ๋ฒˆ์งธ ์ค„์—๋Š” ์ž…๋ ฅ ๋ฐ์ดํ„ฐ์˜ ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์ •์ˆ˜ T๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.
  • ๊ฐ ํ…Œ์ŠคํŠธ ๋ฐ์ดํ„ฐ์˜ ์ฒซ์งธ ์ค„์—๋Š” ๊ด„ํ˜ธ ๋ฌธ์ž์—ด์ด ํ•œ ์ค„์— ์ฃผ์–ด์ง„๋‹ค.
  • ํ•˜๋‚˜์˜ ๊ด„ํ˜ธ ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๋Š” 2 ์ด์ƒ 50 ์ดํ•˜์ด๋‹ค. 

 

์ถœ๋ ฅ

  • ์ถœ๋ ฅ์€ ํ‘œ์ค€ ์ถœ๋ ฅ์„ ์‚ฌ์šฉํ•œ๋‹ค.
  • ๋งŒ์ผ ์ž…๋ ฅ ๊ด„ํ˜ธ ๋ฌธ์ž์—ด์ด ์˜ฌ๋ฐ”๋ฅธ ๊ด„ํ˜ธ ๋ฌธ์ž์—ด(VPS)์ด๋ฉด “YES”, ์•„๋‹ˆ๋ฉด “NO”๋ฅผ ํ•œ ์ค„์— ํ•˜๋‚˜์”ฉ ์ฐจ๋ก€๋Œ€๋กœ ์ถœ๋ ฅํ•ด์•ผ ํ•œ๋‹ค.

 

์˜ˆ์ œ ์ž…๋ ฅ 1)

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

 

์˜ˆ์ œ ์ถœ๋ ฅ 1)

NO
NO
YES
NO
YES
NO

 

์˜ˆ์ œ ์ž…๋ ฅ 2)

3
((
))
())(()

 

์˜ˆ์ œ ์ถœ๋ ฅ 2)

NO
NO
NO

โ€‹

โ€‹

๐Ÿ’ป  Main.java

  • stack์— '('๊ฐ€ ์žˆ์œผ๋ฉด ')'๊ฐ€ ์ž…๋ ฅ๋˜๋ฉด ์˜ฌ๋ฐ”๋ฅธ ์ž…๋ ฅ์ž„์œผ๋กœ popํ•ด์ค€๋‹ค.
  • stack์ด ๋น„์–ด์žˆ์„ ๋•Œ๋Š” popํ•˜์ง€ ์•Š๋„๋ก isEmpty ์œ ๋ฌด๋ฅผ ๊ฒ€์‚ฌํ•œ๋‹ค.
/* ๋ฐฑ์ค€ ์Šคํƒ/ํ - 9012 :: ๊ด„ํ˜ธ */
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < t; i++) {
			Stack<Character> stack = new Stack<>();
			StringTokenizer st = new StringTokenizer(br.readLine());
			String s = st.nextToken();

			for(char x : s.toCharArray()) {
				if(stack.isEmpty()) stack.add(x);
				else {
					if(x == '(') stack.add('(');
					else {
						if(stack.peek() == '(') stack.pop();
						else stack.add('(');
					}
				}
			}
			
			if(stack.isEmpty()) System.out.println("YES");
			else	System.out.println("NO");
		}
		
	}
}
Comments