๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/9012
- ๊ดํธ ๋ฌธ์์ด(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์ ํ๊ณ ')'๊ฐ ๋ค์ด์ค๋ฉด -1์ ํ๋ค.
- ๋ง์ฝ ๋ณ์๊ฐ ๋ง์ด๋์ค๊ฐ ๋๋ค๋ฉด ์์๊ฐ ์๋ชป๋ ๊ฒ์ด๋ฏ๋ก ๋ฐ๋ณต๋ฌธ์ ์ข ๋ฃ ํ "NO"๋ฅผ ์ถ๋ ฅํ๊ณ
- ๋ฐ๋ณต๋ฌธ์ด ๋๋ฌ๋๋ฐ๋ ๋ณ์๊ฐ 0์ด ์๋๋ผ๋ฉด ๋ซํ์ง ์์ ๊ดํธ๊ฐ ์๋ค๋ ์๋ฏธ์ด๋ฏ๋ก "NO"๋ฅผ ์ถ๋ ฅํ๋ค.
- ๋ฐ๋ณต๋ฌธ์ด ์ข ๋ฃ๋ ํ, ๋ณ์๊ฐ 0์ด๋ผ๋ฉด "YES"๋ฅผ ์ถ๋ ฅํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- X
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ9012 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
for(int test = 0; test < T; test++){
// vps์ธ์ง ํ๋ณํ ๋ฌธ์์ด
String vps = br.readLine();
// ๊ดํธ๊ฐ ๋ง๊ฒ ๋ค์ด์ค๋์ง ํ๋ณํ ๋ณ์
int cnt = 0;
for(int i = 0; i < vps.length(); i++){
// ๋ง์ฝ ์ฌ๋ ๊ดํธ๊ฐ ๋ค์ด์จ๋ค๋ฉด
if(vps.charAt(i) == '('){
// ์นด์ดํธ + 1
cnt = cnt + 1;
}
// ๋ซ๋ ๊ดํธ๊ฐ ๋ค์ด์จ๋ค๋ฉด
else if(vps.charAt(i) == ')'){
// ์นด์ดํธ - 1
cnt = cnt - 1;
}
// ๋ง์ฝ ์นด์ดํธ๊ฐ ๋ง์ด๋์ค๋ผ๋ฉด ๊ดํธ์ ์์๊ฐ ์๋ชป๋๋ค๋ ๋ป์ด๋ฏ๋ก
// ๋ฐ๋ณต๋ฌธ ์ข
๋ฃ
if(cnt < 0){
break;
}
}
// ์นด์ดํธ๊ฐ 0์ด๋ฉด ์์์ ๊ฐ์๊ฐ ๋ชจ๋ ๋ง์ผ๋ฏ๋ก YES ์ถ๋ ฅ
if(cnt == 0){
sb.append("YES" + "\n");
}
// 0์ด ์๋๋ผ๋ฉด NO ์ถ๋ ฅ
else{
sb.append("NO" + "\n");
}
}
System.out.println(sb);
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 10816 ์ซ์ ์นด๋ 2 (0) | 2024.07.20 |
---|---|
[Java] BOJ 10773 ์ ๋ก (0) | 2024.07.20 |
[Java] BOJ 4949 ๊ท ํ์กํ ์ธ์ (2) | 2024.07.19 |
[Java] BOJ 2839 ์คํ ๋ฐฐ๋ฌ (0) | 2024.07.18 |
[Java] BOJ 2164 ์นด๋2 (0) | 2024.07.18 |