알고리즘 스터디 - 2주차 1

9012

• 알고리즘 : 문자열, 배열, 스택?
• 난이도 : 실버4

문제

9012

접근

• "("과 ")"의 갯수가 동일하면 YES, 동일하지 않으면 NO
  • 동일해도 VPS가 아닌경우가 존재 : ))((
• VPS가 되지 않은 조건?
  • "("과 ")"의 갯수가 동일하지만 ")"부터 시작한경우: )(
  • "("가 많은 경우 : (())(
  • ")"가 많은 경우 : ())))
• 만약, 들어오는 데이터가 "("이고 "("이 나갈 수 있는 조건이 ")"을 만날 때라면?
  • ))(( : 처음에 없는데 꺼내려고 해서 NO, 들어오기만 해서 NO
  • (())) : 전부 나갔는데 또 들어온 데이터를 꺼낼려고 해서 NO
  • )(()): 처음에 없는데 꺼내려고 해서 NO
  • (() : 아직 한개 데이터가 남아있어서 NO
  • ()( : 위와 동일

가정

• 위와 같은 검증을 할 수 있는 자료구조?
  • 배열, 스택
• 스택에 (를 만났을 때 넣고 )를 만나면 하나씩 꺼내면서 검증하면 될 것 같다.
  • Stack이 0인 상태에서 꺼내려고 하면 NO로 리턴
  • Stack에 값이 남아 있으면 NO

풀어보기

package org.example;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine());
        String[] result = new String[N];

        for(int i = 0; i < N; i++){
            if(stackCheck(reader.readLine())){
                result[i] = "YES";
                continue;
            }
            result[i] = "NO";
        }
        for(String s : result){
            System.out.println(s);
        }
    }
    public static boolean stackCheck(String string){
        String[] strArr = string.split("");
        Stack<String> stack = new Stack<>();
        //처음부터 빼려고 하면
        if(strArr[0].equals(")")) return false;
		for (String s : strArr) {;
            if(s.equals("(")) stack.push(s);
            //스택이 비어있는데 빼려고 할 때
            if(stack.isEmpty() && s.equals(")")) return false;
            //)일때 
            if(s.equals(")")) stack.pop();
		}
		return stack.isEmpty();
	}

}

시행착오

• 스택이 비어있지 않을때 문자가 )일때 pop을 해야하는데 스택에 들어있는 문자와 단순 비교하여서 스택에 있는 문자를 제대로 꺼내지 않았다.

if (!stack.isEmpty()&&stack.peek().equals(s)) {
				stack.pop();
			}
//아래 코드로 수정
//)일때 
 // 다른 조건식에서 스택이 비어있는지 체크를 해서 아래 조건식에는 
 // 스택이 비어있는지 체크를 별도로 하지 않음.
 if(s.equals(")")) stack.pop();

참고자료

-골든레빗 스택 설명 페이지