-
728x90
https://www.acmicpc.net/problem/9012
문제요약
- 문장 내의 () [] 괄호 쌍이 올바르게 되어 있는지 확인하는 문제
- 마침표( . )이 첫 문자열로 들어오면 종료
해당문제는 괄호 쌍이 맞는 지를 확인하는 문제였다.
괄호쌍이 맞는다는 것은
- 여는 괄호 -> 닫는 괄호 쌍을 찾는 것
이 핵심이므로, stack에 두 개의 쌍이 나오면 pop()을 하여 제거하였고,
결과적으로 stack이 비어있는지를 체크하는 방향으로 접근을 하였다.
속도가 안된다면, check와 같은 boolean 타입으로 애당초 불가능한 경우에는 처리를 바로 하려고 했었으나,
이번 문제는 boolean 타입이 주어지지 않아도 속도에 문제가 없어서 다음과 같이 썼다.import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); for (int i = 0; i < num; i++) { String row = sc.next(); Stack<Character> stack = new Stack<>(); for (int j = 0; j < row.length(); j++) { if(row.charAt(j) == ')'){ if(stack.isEmpty()){ stack.push(row.charAt(j)); }else { if(stack.peek() == '(') stack.pop(); else stack.push(row.charAt(j)); } } // '(' 일 때, else { stack.push(row.charAt(j)); } } //stack 확인 if(stack.isEmpty()){ System.out.println("YES"); }else { System.out.println("NO"); } } sc.close(); } }
느낀점
이전값과 최근값을 비교하는 문제에 stack 자료구조가 많이 쓰이는 것을 알았다.
이유는 당연하겠지만, stack은 FILO(First In Last Out) 구조이기 때문이다.
문제 구현을 넘어서 보기 좋은 코드를 짜는 법도 많이 고민을 해야겠다.
'알고리즘' 카테고리의 다른 글
11279 - 최대 힙 (0) 2023.05.30 4949 - 균형잡힌 세상 (0) 2023.05.30 1021 - 회전하는 큐 (0) 2023.05.26 1874 - 스택 수열 (1) 2023.05.26 18258 - 큐2 (0) 2023.05.24