https://www.acmicpc.net/problem/4949
๋ฌธ์
์ธ๊ณ๋ ๊ท ํ์ด ์ ์กํ์์ด์ผ ํ๋ค. ์๊ณผ ์, ๋น๊ณผ ์ด๋ ๊ทธ๋ฆฌ๊ณ ์ผ์ชฝ ๊ดํธ์ ์ค๋ฅธ์ชฝ ๊ดํธ์ฒ๋ผ ๋ง์ด๋ค.
์ ๋ฏผ์ด์ ์๋ฌด๋ ์ด๋ค ๋ฌธ์์ด์ด ์ฃผ์ด์ก์ ๋, ๊ดํธ๋ค์ ๊ท ํ์ด ์ ๋ง์ถฐ์ ธ ์๋์ง ํ๋จํ๋ ํ๋ก๊ทธ๋จ์ ์ง๋ ๊ฒ์ด๋ค.
๋ฌธ์์ด์ ํฌํจ๋๋ ๊ดํธ๋ ์๊ดํธ("()") ์ ๋๊ดํธ("[]")๋ก 2์ข ๋ฅ์ด๊ณ , ๋ฌธ์์ด์ด ๊ท ํ์ ์ด๋ฃจ๋ ์กฐ๊ฑด์ ์๋์ ๊ฐ๋ค.
- ๋ชจ๋ ์ผ์ชฝ ์๊ดํธ("(")๋ ์ค๋ฅธ์ชฝ ์๊ดํธ(")")์๋ง ์ง์ ์ด๋ค์ผ ํ๋ค.
- ๋ชจ๋ ์ผ์ชฝ ๋๊ดํธ("[")๋ ์ค๋ฅธ์ชฝ ๋๊ดํธ("]")์๋ง ์ง์ ์ด๋ค์ผ ํ๋ค.
- ๋ชจ๋ ์ค๋ฅธ์ชฝ ๊ดํธ๋ค์ ์์ ๊ณผ ์ง์ ์ด๋ฃฐ ์ ์๋ ์ผ์ชฝ ๊ดํธ๊ฐ ์กด์ฌํ๋ค.
- ๋ชจ๋ ๊ดํธ๋ค์ ์ง์ 1:1 ๋งค์นญ๋ง ๊ฐ๋ฅํ๋ค. ์ฆ, ๊ดํธ ํ๋๊ฐ ๋ ์ด์์ ๊ดํธ์ ์ง์ง์ด์ง์ง ์๋๋ค.
- ์ง์ ์ด๋ฃจ๋ ๋ ๊ดํธ๊ฐ ์์ ๋, ๊ทธ ์ฌ์ด์ ์๋ ๋ฌธ์์ด๋ ๊ท ํ์ด ์กํ์ผ ํ๋ค.
์ ๋ฏผ์ด๋ฅผ ๋์ ๋ฌธ์์ด์ด ์ฃผ์ด์ก์ ๋ ๊ท ํ์กํ ๋ฌธ์์ด์ธ์ง ์๋์ง๋ฅผ ํ๋จํด๋ณด์.
์ ๋ ฅ
ํ๋ ๋๋ ์ฌ๋ฌ์ค์ ๊ฑธ์ณ์ ๋ฌธ์์ด์ด ์ฃผ์ด์ง๋ค. ๊ฐ ๋ฌธ์์ด์ ์๋ฌธ ์ํ๋ฒณ, ๊ณต๋ฐฑ, ์๊ดํธ("( )") ๋๊ดํธ("[ ]")๋ฑ์ผ๋ก ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, ๊ธธ์ด๋ 100๊ธ์๋ณด๋ค ์๊ฑฐ๋ ๊ฐ๋ค.
์ ๋ ฅ์ ์ข ๋ฃ์กฐ๊ฑด์ผ๋ก ๋งจ ๋ง์ง๋ง์ ์ ํ๋(".")๊ฐ ๋ค์ด์จ๋ค.
์ถ๋ ฅ
๊ฐ ์ค๋ง๋ค ํด๋น ๋ฌธ์์ด์ด ๊ท ํ์ ์ด๋ฃจ๊ณ ์์ผ๋ฉด "yes"๋ฅผ, ์๋๋ฉด "no"๋ฅผ ์ถ๋ ฅํ๋ค.
์์ ์ ๋ ฅ 1 ๋ณต์ฌ
So when I die (the [first] I will see in (heaven) is a score list). [ first in ] ( first out ). Half Moon tonight (At least it is better than no Moon at all]. A rope may form )( a trail in a maze. Help( I[m being held prisoner in a fortune cookie factory)]. ([ (([( [ ] ) ( ) (( ))] )) ]). . .
์์ ์ถ๋ ฅ 1 ๋ณต์ฌ
yes yes no no no yes yes
ํํธ
7๋ฒ์งธ์ " ."์ ๊ฐ์ด ๊ดํธ๊ฐ ํ๋๋ ์๋ ๊ฒฝ์ฐ๋ ๊ท ํ์กํ ๋ฌธ์์ด๋ก ๊ฐ์ฃผํ ์ ์๋ค.
ํ์ด - > (Java 8.0 ์ฌ์ฉ)
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
//์ค์บ๋ ์์ฑ (ํด๋น ๋ฌธ์ฅ์ ๋ฐ๋ ์ญํ )
Scanner in = new Scanner(System.in);
//์
๋ ฅํ ๋ฌธ์ฅ ๋ณ์ -> s
String s;
//๋ฌธ์์ด ์ฐพ๋ ์ฅ์ (๋ฐ๋ณต๋ฌธํ์ฉ)
while(true) {
s = in.nextLine(); // ๋ฌธ์ฅ์ ๋ฐ์์ s์ ๋ฃ๋๋ค
if(s.equals(".")) { // ๋ฌธ์ฅ ์ค์บํ๋ค๊ฐ (.)์ ์ฐพ์์ผ๋ฉด ํ์ถํด
break;
}
System.out.println(solve(s)); // solve๋ฅผ ์คํ !
}
}
public static String solve(String s) { // s๋ณ์ (๋ฌธ์ฅ)์ ๋ฐ์
Stack<Character> stack = new Stack<>(); // ์คํ ์์ฑ
for(int i = 0; i < s.length(); i++) { //s(๋ฌธ์์ด)์ ๊ธธ์ด๋งํผ ๋ฐ๋ณตํ ๊ฑฐ์ผ
char c = s.charAt(i); //i๋ฒ์งธ ๋ฌธ์์ ๋ณ์๋ c์ ๋ด์๊ฑฐ๋ค.
// ์ฌ๋ ๊ดํธ์ผ ๊ฒฝ์ฐ ์คํ์ push
if(c == '(' || c == '[') {
stack.push(c);
}
// ๋ซ๋ ์๊ดํธ ์ผ ๊ฒฝ์ฐ
else if(c == ')') {
// ์คํ์ด ๋น์ด์๊ฑฐ๋ popํ ์์๊ฐ ์๊ดํธ๋ ๋งค์นญ์ด ์๋๋ ๊ฒฝ์ฐ
if(stack.empty() || stack.peek() != '(') {
return "no";
}
else {
stack.pop();
}
}
else if(c == ']') {
// ์คํ์ด ๋น์ด์๊ฑฐ๋ popํ ์์๊ฐ ๋๊ดํธ๋ ๋งค์นญ์ด ์๋๋ ๊ฒฝ์ฐ
if(stack.empty() || stack.peek() != '[') {
return "no";
}
else {
stack.pop();
}
}
//
}
if(stack.empty()) {
return "yes";
}
else {
return "no";
}
}
}
'๐ฎ ์๊ณ ๋ฆฌ์ฆ Algorithm > โ ๏ธ ๋ฐฑ์ค โ ๏ธ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๋ฐฑ์ค ์๊ณ ๋ฆฌ์ฆ - [์ด๋ถ ํ์] ๋๋ฌด ์๋ฅด๊ธฐ (0) | 2021.03.18 |
---|
๋๊ธ