알고리즘
자바의 자료구조 - 스택의 활용
고유빙글
2021. 11. 21. 06:14
드디어 본격적인 시작이다.
다시 한번 밝히지만 해당 포스팅들은 https://blog.encrypted.gg/919 이 출처이며,
해당 블로그의 포스팅을 공부하는 포스팅이다.
정확한 정보와 자세한 내용은 해당 블로그를 보는 것을 강력히 권한다.
: 수식의 괄호 쌍
간단한 스택의 활용이다. (, {, [ 등이 올때 Stack에 담고, 쌍이 맞는 ),},]이 올때 pop()을 시키어 해결하는 구조다.
: https://www.acmicpc.net/problem/10799
10799번: 쇠막대기
여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저
www.acmicpc.net
심화로 BOJ에서 이 문제를 풀어보도록 했다.
처음 접했을때 감이 오지 않았다.
import java.util.Scanner;
import java.util.Stack;
public class BOJ4949 {
//public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
String q = sc.nextLine();
String answer = solution(q);
System.out.println(answer);
}
private static String solution(String q) {
Stack<Character> stack = new Stack<>();
boolean result = true;
for (int i = 0; i < q.length(); i++) {
if(q.charAt(i)=='(' || q.charAt(i)=='[') {
stack.push(q.charAt(i));
result = false;
}
if(q.charAt(i)=='.') break;
if(q.charAt(i)==')') {
if(!stack.isEmpty()) {
if(stack.peek().equals('(')) {
stack.pop();
result = true;
}
}
else {
result = false;
break;
}
}
if(q.charAt(i)==']') {
if(!stack.isEmpty()) {
if(stack.peek().equals('[')) {
stack.pop();
result = true;
}
}
else {
result = false;
break;
}
}
}
if(result) return "yes";
else return "no";
}
}이런 방식으로 풀어봤는데 백준에서 자바를 사용하는 방법이 기존에 이용하던 프로그래머스와 달라서 애를 먹었다.
그러다 여러 줄을 다루는 방법에도 문제가 있었음을 깨달았다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
public class BOJ4949 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String q = "";
while((q = br.readLine()) != null) {
String answer = solution(q);
System.out.println(answer);
}
}
private static String solution(String q) {
Stack<Character> stack = new Stack<>();
boolean result = true;
for (int i = 0; i < q.length(); i++) {
if(q.charAt(i)=='(' || q.charAt(i)=='[') {
stack.push(q.charAt(i));
result = false;
}
if(q.charAt(i)=='.') break;
if(q.charAt(i)==')') {
if(!stack.isEmpty()) {
if(stack.peek().equals('(')) {
stack.pop();
result = true;
}
}
else {
result = false;
break;
}
}
if(q.charAt(i)==']') {
if(!stack.isEmpty()) {
if(stack.peek().equals('[')) {
stack.pop();
result = true;
}
}
else {
result = false;
break;
}
}
System.out.println("q.charAt(i) : "+q.charAt(i));
System.out.println("stack : "+stack);
System.out.println();
}
if(result) return "yes";
else return "no";
}
}
그래서 이렇게 해보았는데, 여러 줄은 다 처리가 됐는데
([ (([( [ ] ) ( ) (( ))] )) ]).이게 나는 yes가 나오고, 답지는 no가 나와야 한다고 한다. 괄호 쌍은 맞지만, 문제구문중에
- 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
이 내용에 위배되는게 아닌가 싶은데 도저히 문자열의 균형이라는게 어떤건지 모르겠다.
===============================================================
: https://www.acmicpc.net/problem/2504
불러오는 중입니다...
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
public class BOJ2504 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String q = br.readLine();
int a = solution(q);
bw.write(a+"");
bw.flush();
bw.close();
System.out.println();
}
private static int solution(String q) {
Stack<Character> s = new Stack<>();
Stack<Integer> p = new Stack<>();
Stack<Integer> stage = new Stack<Integer>();
int point = 0;
int count = 0;
for (int i = 0; i < q.length(); i++) {
char m = q.charAt(i);
int tool = 0;
if(m=='{') return 0;
if(m=='}') return 0;
if(m=='(') {
if(s.isEmpty()) {
s.push(m);
}else if(s.peek().equals('(')) {
s.push(m);
}else if(s.peek().equals('[')) {
s.push(m);
}else if(s.peek().equals(')')) {
s.push(m);
}else if(s.peek().equals(']')) {
s.push(m);
}
count++;
} else if(m=='[') {
if(s.isEmpty()) {
s.push(m);
}else if(s.peek().equals('(')) {
s.push(m);
}else if(s.peek().equals('[')) {
s.push(m);
}else if(s.peek().equals(')')) {
s.push(m);
}else if(s.peek().equals(']')) {
s.push(m);
}
count++;
} else if(m==')') {
if(s.isEmpty()) return 0;
if(s.peek().equals('(')) {
p.push(2);
s.push(m);
}else if(s.peek().equals(')')) {
if(p.size()>=2) {
if(count/2==0) {
while(true) {
if(!p.isEmpty()) tool += p.pop();
else break;
}
}else {
for (int j = 0; j < count/2; j++) {
tool = p.pop();
}
}
}else {
tool = p.pop();
}
p.push(tool*2);
s.push(m);
}else if(s.peek().equals(']')) {
if(p.size()>=2) {
if(count/2==0) {
while(true) {
if(!p.isEmpty()) tool += p.pop();
else break;
}
}else {
for (int j = 0; j < count/2; j++) {
tool = p.pop();
}
}
}else {
tool = p.pop();
}
p.push(tool*2);
s.push(m);
}else if(s.peek().equals('[')) {
return 0;
}
count--;
} else if(m==']') {
if(s.isEmpty()) return 0;
if(s.peek().equals('[')) {
p.push(3);
s.push(m);
}else if(s.peek().equals(')')) {
if(p.size()>=2) {
if(count/2==0) {
while(true) {
if(!p.isEmpty()) tool += p.pop();
else break;
}
}else {
for (int j = 0; j < count/2; j++) {
tool = p.pop();
}
}
}else {
tool = p.pop();
}
p.push(tool*3);
s.push(m);
}else if(s.peek().equals(']')) {
if(p.size()>=2) {
if(count/2==0) {
while(true) {
if(!p.isEmpty()) tool += p.pop();
else break;
}
}else {
for (int j = 0; j < count/2; j++) {
tool = p.pop();
}
}
}else {
tool = p.pop();
}
p.push(tool*3);
s.push(m);
}else if(s.peek().equals('(')) {
return 0;
}
count--;
}
if(count==0 && i != 0) {
stage.push(p.pop());
point = 0;
}
// System.out.println("s : "+s);
// System.out.println("p : "+p);
// System.out.println("count : "+count);
// System.out.println("stage : "+stage);
// System.out.println("point : "+point);
// System.out.println("====");
}
// while(true) {
// if(!p.isEmpty()) point += p.pop();
// else break;
// }
while(true) {
if(!stage.isEmpty()) point += stage.pop();
else break;
}
return point;
}
}이래도 되나 싶을정도의 진행속도다.. 이렇게 복잡한것 8시간이나 걸렸다.
밖에서 하다보니 집중을 잘 못하기도 했지만 ㅠㅠ
그마저도 현 시점 오류가 있다. 좀 더 수정해봐야겠다.
이건..좀 더 기본기를 공부하고 다뤄봐야겠다.