자바 문법 및 알고리즘 (stack & queue)

괄호 문제 해결법

• 괄호 문제는 항상 괄호가 '(' 이면 -> push를 생각한다 : 분기점 잡기
• 그 외에는 ')'는 -> pop으로 생각

if (str.eqauls('(')) {
    	stack.push('(');
 	}
    else {
    	if (stack.isEmpty()) {
        	return "NO"// 이 경우는 이제 닫는 괄호 ')'만 남기 때문에 종료 
        }
        else {
        	stack.pop(); // 그 외에는 앞에 '('만 남기 때문에 없애줌
        }
    }

문제 1

1. 이슈 및 해결 방법

• 괄호문제는 스택을 보통 이용 (테스트 케이스에서 실수하는 경우가 많으므로 주의 사항지킬것) - 닫는 괄호가 먼저 나오면 안되는 경우 등
• 첫번째 값을 먼저 넣고 다음 인덱스부터 비교
• 스택에 홀로 ) 남으면 -> 바로 NO임 : 이 경우를 괄호 문제에서 항상 생각해야 함.
  그렇지 않으면
  - 스택의 값 (peek)과 새로 들어온 값이 다르면 - pop()
  - 스택에서 뺄때는 항상 스택이 존재하는지 확인한다! (if문으로 확인)
  같으면 그냥 - push()

    public String solution(String str) {
        String answer="NO";

        // String -> str[]
        String []strArr=str.split("");

        Stack<String>stack=new Stack();
        // 첫번째 값을 넣어준다.
        stack.push(strArr[0]);

        // 하나씩 접근
        for (int i=1;i< strArr.length;i++) {

            // 스택에 홀로 남은게 )이면 종료 -> 더이상 못닫기 때문에
            if (stack.size()==1 && stack.peek().equals(")")) {
                break;
            }

            else {
                // 만약 스택이 비어져있지 않고 스택에 있는거하고 새로 들어온값하고 다르면 -> 스택에서 빼기
                if (!stack.isEmpty() && !stack.peek().equals(strArr[i])) {
                    stack.pop();
                }
                // 같으면 스택에 더하기
                else {
                    stack.push(strArr[i]);
                }
            }
        }

        // 비워져있으면 YES
        if (stack.isEmpty()) {
            answer="YES";
        }
        return answer;

    }

해결 방법 2

• 괄호 문제는 항상 괄호가 '(' 이면 -> push를 생각한다 : 분기점 잡기
• 그 외에는 ')'는 -> pop으로 생각

    public String solution2(String str) {
        String answer="NO";

        // String -> str[]
        String []strArr=str.split("");

        Stack<String>stack=new Stack();

        for (String ss:strArr) {
            if (ss.equals("(")) {
                stack.push(ss);
            }
            else {
                // 닫혀진 괄호가 들어와서
                if (stack.isEmpty()) {
                    return "NO";
                }
                else {
                    stack.pop();
                }
            }
        }


        // 비워져있으면 YES
        if (stack.isEmpty()) {
            answer="YES";
        }
        
        return answer;
    }

문제 2.

해결방법

• Stack 문제는 항상 괄호가 '(' 이면 -> push를 생각한다 : 분기점 잡기
• 그 외에는 ')'는 -> pop으로 생각

코드

    public String solution(String str) {

//        String strArr[]=str.split("");

        char[] charArr =str.toCharArray();
        Stack<Character>stack=new Stack<>();

        for (Character ss:charArr) {
            if (ss=='(' || Character.isAlphabetic(ss)) {
                stack.push(ss);
            }
            else {
                // 닫는 괄호면 for문으로 stack 탐색하다가 ( 찾기
                while (!stack.isEmpty()) {
                    if (stack.peek().equals('(')) {
                        // 지우고 while문 종료
                        stack.pop();
                        break;
                    }
                    // 알파벳 제거
                    stack.pop();
                }
            }
        }
        String answer="";
        // stack 남은거 확인하기
        for (char s:stack) {
            answer+=s;
        }
        return answer;
    }

문제 3 (카카오 인형뽑기 문제)

주요 이슈

• 배열 만드는 것이 헷갈렸음...
  

해결 방법

• 순서대로 뽑고 스택으로 해결하면 됨

코드

// 카카오 크레인 뽑기
package inflearn.section5_stackQueue;

import java.util.*;
public class Main3 {

    public int solution(int n,int[][]arr,int m,int[]mArr) {
        int answer=0;
        Stack<Integer>stack=new Stack<>();
        for (int i:mArr) {
            int k=i-1; // 행을 뽑는다.

            int su=0;
            for (int j=0;j<n;j++) {
                if (arr[j][k]!=0) {
                    su=arr[j][k];
                    arr[j][k]=0;
                    break;
                }
            }
            // 뽑은거 저장
            // stack이 비어잇으면 저장

            if (su!=0) {

                if (stack.isEmpty()) {
                    stack.push(su);
                }
                else {
                    // 비워있지 않고 같으면 pop
                    if (stack.peek().equals(su)) {
                        answer+=2;
                        stack.pop();
                    }else{ // 아니면 그냥 저장
                        stack.push(su);
                    }
                }
            }
        }
        return answer;

    }


    public static void main(String[] args) {
        Main3 main=new Main3();
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int arr[][]=new int[n][n];

        // 배열에 넣기
        for (int i=0;i<n;i++) {
            for (int j=0;j<n;j++) {
                arr[i][j]=scan.nextInt();
            }
        }

        // 확인
//        for (int i=0;i<n;i++) {
//            for (int j=0;j<n;j++) {
//                System.out.print(arr[i][j]+" ");
//            }
//            System.out.println();
//        }

        // 진행 횟수
        int m=scan.nextInt();
        int mArr[]=new int[m];

        for (int i=0;i<m;i++) {
            mArr[i]=scan.nextInt();
        }


        System.out.println(main.solution(n,arr,m,mArr));
        
    }
}