[테코테코] 2주차 Stack

주제

금주 테코테코의 주제는 Stack입니다.

 

Stack 자료구조를 활용하거나 Stack자료구조의 작동원리를 이해하여 아래 문제를 해결하였습니다.

 

문제

1.  올바른 괄호

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

 

코드

public class 올바른_괄호 {

    boolean solution(String s) {

        Node first = null;
        Node last = null;

        int len = s.length();
        for(int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if(c == '(') {
                if(first == null) {
                    first = new Node();
                    last = first;
                    continue;
                }
                last = last.newNextNode();
                continue;
            }
            if(first == null) return false;
            Node prev = last.removeNowNode();
            if(prev == null) {
                first = null;
            }
            last = prev;
        }

        return last == null;
    }

    public static class Node {
        public Node prevNode;
        public Node nextNode;

        public Node() {
        }

        public Node(Node prevNode) {
            this.prevNode = prevNode;
        }

        public static Node from (Node prev) {
            return new Node(prev);
        }

        public Node newNextNode() {
            this.nextNode = Node.from(this);
            return this.nextNode;
        }

        public Node removeNowNode() {
            Node prev = this.prevNode;
            if(prev == null) return null;
            prev.nextNode = null;
            return prev;
        }
    }
}

 

2.  괄호_회전하기

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

코드

package com.codingTest.programers.level2;

import java.util.*;

public class 괄호_회전하기 {
    Map<Character, Integer> map;

    public 괄호_회전하기() {
        map = new HashMap<>();
        map.put('(', 0);
        map.put('[', 1);
        map.put('{', 2);
        map.put(')', 3);
        map.put(']', 4);
        map.put('}', 5);
    }

    public int solution(String s) {
        int len = s.length();

        int answer = 0;

        boolean flag;
        Stack<Character> checkPoint;

        int point = 0;
        for(int i = 0; i < len; i++){
            flag = false;
            checkPoint = new Stack<>();
            for(int j = 0; j < len; j++){
                char c = s.charAt((j + point)%len);
                int index = map.get(c);
                if(index < 3) {
                    checkPoint.push(c);
                } else {
                    if(checkPoint.isEmpty()) {
                        flag = true;
                        break;
                    }
                    char check = checkPoint.pop();
                    int prevIndex = map.get(check);
                    if(prevIndex != index%3) {
                        flag = true;
                        break;
                    }
                }
            }
            if(checkPoint.isEmpty() && !flag) {
                answer++;
            }
            point++;
        }

        return answer;
    }
}