๐ ํ๋ก๊ทธ๋๋จธ์ค / ์คํ&ํ / Level2 / ์ฌ๋ฐ๋ฅธ ๊ดํธ
๐ ๋ฌธ์
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
๐ซ ์ ํ ์ฌํญ
- ๋ฌธ์์ด s์ ๊ธธ์ด : 100,000 ์ดํ์ ์์ฐ์
- ๋ฌธ์์ด s๋ '(' ๋๋ ')' ๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ต๋๋ค.
๐ ์ ์ถ๋ ฅ ์
| s | answer |
| "()()" | true |
| "(())()" | true |
| ")()(" | false |
| "(()(" | false |
๐ค ํ์ด ๋ฐฉ๋ฒ
1๏ธโฃ ๋จ์ ๋ฐฐ์ด์ ํตํ ํ์ด (1)
โก๏ธ ๋ฌธ์์ด s ๋ฅผ ๋๋์ด ๋ฐฐ์ด์ ๋ง๋ค๊ณ "(" ๋ฅผ +1 ๋ก ํ๊ณ ")" ๋ฅผ -1 ๋ก ํ์ ๋, ์์์๋ถํฐ ํ์ํ์ ๋ ๊ทธ ํฉ์ด 0๋ณด๋ค ์์์ง๊ฑฐ๋ ์ต์ข ํฉ์ด 0์ด ์๋๋ฉด ์ ์์ ์ธ ๊ดํธ์ ํํ๋ผ๊ณ ๋ณผ ์ ์๋ค.
class Solution {
boolean solution(String s) {
int total = 0;
// ๋ฌธ์์ด ๋ถํด
String[] str = s.split("");
// ๋ฐฐ์ด ์ ์ฒด ํ์
for (int i=0; i<str.length; i++) {
if (total < 0) { // ํ์ ์ค ์์๊ฐ ๋๋ฉด false
return false;
}
String tmp = str[i];
if (tmp.equals("(")) {
total++;
continue;
}
total--;
}
// ์ ์ฒด๋ฅผ ํ์ํ์ ๋ ํฉ์ด 0์ด ์๋๋ฉด false
if (total == 0) {
return true;
}
return false;
}
}
โก๏ธ ์คํ๊ฒฐ๊ณผ ํจ์จ์ฑ ํ ์คํธ๋ฅผ ํต๊ณผํ์ง ๋ชปํ๋ค.

2๏ธโฃ Stack ์ ์ด์ฉํ ํ์ด (1)
โก๏ธ ์๋์ ๊ฐ์ ๊ณผ์ ์ผ๋ก ์์ง์ธ๋ค.
["(", "(", ")", ")", "(", ")"] ์ ์ํ๋ก ๋ฌธ์์ด์ ์ชผ๊ฐ ๋ค
โ Stack ์ด ๋น์ด์๋์ง ํ์ธ
โ -1 _ ๋น์ด์๋ ๊ฒฝ์ฐ : ์คํ์ ๋ฐ๋ก ๋ฃ๋๋ค (push)
โ -2 _ ๋น์ด์์ง ์์ ๊ฒฝ์ฐ : โก ๋ก ๋์ด๊ฐ
โก peek ์ ํตํด ๋งจ ์ ์์๋ฅผ ๊บผ๋ด๊ณ ์์์ ํฉ์นจ
โก -1 _ ํฉ์ณค์ ๋ () ๊ฐ ๋๋ ๊ฒฝ์ฐ : ์คํ์์ ๋งจ ์๋ฅผ ๋บธ๋ค (pop)
โก -2 _ ํฉ์ณค์ ๋ () ๊ฐ ๋์ง ์๋ ๊ฒฝ์ฐ : ์คํ์ ๋ฃ๋๋ค (push)
import java.util.Stack;
class Solution {
boolean solution(String s) {
Stack<String> box = new Stack<>();
String[] str = s.split("");
for (String ss : str) {
if (box.isEmpty()) {
box.push(ss);
continue;
}
String match = box.peek() + ss;
if (match.equals("()")) {
box.pop();
continue;
}
box.push(ss);
}
if (box.isEmpty()) {
return true;
}
return false;
}
}
โก๏ธ ๋๊ฐ์ด ํจ์จ์ฑ ํ ์คํ ํต๊ณผํ์ง ๋ชปํ๋ค. ๊ทธ๋ฆฌ๊ณ ์ผ๋ฐ ํ ์คํธ๋ ๋ฐฐ์ด์ ์ด์ฉํ ํ์ด๋ณด๋ค๋ ์ค๋๊ฑธ๋ ธ๋ค.
โ๋น ๋ฅด๊ฒ ์๋ํ์ง ๋ชปํ๋ ์ด์
โ ๋ฐ๋ณต๋ฌธ โก๏ธ ํ์ง๋ง ์ ์ฒด ํ์์ ํด์ผ ์๋ชป๋ ๊ฒ์ ์ ์ ์์ผ๋ฏ๋ก ์ค์ด๊ธฐ ์ด๋ ต๋ค.
โก ๋ฌธ์์ด โก๏ธ ๋ฌธ์์ด์ ๊ฒฝ์ฐ ์ฐ์ฐ ๋๋ ๋น๊ต๊ฐ ์ซ์๋ณด๋ค ์ค๋๊ฑธ๋ฆฐ๋ค. ๊ดํธ ๋ฌธ์ ๋์ ์ซ์๋ก ์ฐ์ฐํ ์ ์๋ ๋ฐฉ๋ฒ์ ์๊ฐํด๋ณด์.
3๏ธโฃ Stack ์ ์ด์ฉํ ํ์ด (2)
โก๏ธ ์๋ฌด๋๋ ๋ฌธ์์ด์ ๋ง๋ค๊ณ ๋น๊ตํ๋ ๊ณผ์ ์์ ์๊ฐ์ด ๊ฑธ๋ฆด ๊ฒ ๊ฐ๋ค. ํด๋น ๋ถ๋ถ์ ์ซ์๊ฐ์ผ๋ก ๋์ ํด์ ๊ณ์ฐํด๋ณธ๋ค.
int sum = '(' - ')'; // ๊ฒฐ๊ณผ : -1
์ด๋ ๊ฒ ๋ ์ฐจ๋ฅผ ํ์ธํ๊ณ equals ๋ฅผ ํตํ ๋ฌธ์์ด ๋น๊ต๋์ sum ๊ณผ ์ผ์นํ๋์ง ํ์ธํจ์ผ๋ก์จ ์๋๋ฅผ ๊ฐ์ ํ๋ค.
import java.util.Stack;
class Solution {
boolean solution(String s) {
// ๋ชจ๋ char ํํ๋ก ๋ฐ๊ฟ์ค๋ค.
Stack<Character> box = new Stack<>();
char[] c = s.toCharArray();
int sum = '('-')'; // -1
for (char ss : c) {
if (box.isEmpty()) {
box.push(ss);
continue;
}
if (sum == box.peek()-ss) {
box.pop();
continue;
}
box.push(ss);
}
if (box.isEmpty()) {
return true;
}
return false;
}
}
โก๏ธ ์ด๋ฒ์๋ ํจ์จ์ฑ ํ ์คํธ 2๊ฐ์ค์ 1๊ฐ๋ฅผ ์ฑ๊ณตํ๋ค.

4๏ธโฃ ๋จ์ ๋ฐฐ์ด์ ํตํ ํ์ด (2)
โก๏ธ ๋งจ ์ฒ์ ํ์ด ๋๋ ์คํ๋ณด๋ค๋ ๋ฐฐ์ด์ด ์ฒ๋ฆฌ ์๋๊ฐ ๋นจ๋์ผ๋ ๋๊ฐ์ ์๋ฆฌ๋ฅผ ์ฒซ๋ฒ์งธ ํ์ด์ ์ ์ฉ์์ผ ๋ณด์๋ค.
class Solution {
boolean solution(String s) {
int total = 0;
int left = '(';
char[] str = s.toCharArray();
for (int i=0; i<str.length; i++) {
if (total < 0) {
return false;
}
if (str[i] == left) {
total++;
continue;
}
total--;
}
if (total == 0) {
return true;
}
return false;
}
}
โก๏ธ ๋ฌธ์ ์ ์ฃผ์ ์ธ Stack ์ผ๋ก ํผ๊ฑด ์๋์ง๋ง ํจ์จ์ฑ ํ ์คํธ๋ฅผ ๋ชจ๋ ํต๊ณผํ์๋ค.

๐ป ํ์ด ์ฝ๋
[level 2] Title: ์ฌ๋ฐ๋ฅธ ๊ดํธ, Time: 4.74 ms, Memory: 52.8 MB -BaekjoonHub · Young998904/Practice_Algorithm_Auto@3fafcc5
Show file tree Showing 2 changed files with 208 additions and 0 deletions.
github.com