[알고리즘] 백준 > #5076. Web Pages

문제링크

백준 #5076. Web Pages

풀이방법

괄호 관련 문제랑 비슷했다. 이런 규칙을 가진 문제의 경우, 스택으로 해결할 수 있다. 스택을 사용하는건 어렵지 않았지만 문자열을 다루는게 조금 까다로웠다; keyword를 뽑아오는 함수와 오른쪽 꺽쇠 인덱스를 찾는 함수를 따로 구현해 문제를 해결했다!

코드

class Solution5076 {

    private final char LEFT_BRACKET = '<';
    private final char RIGHT_BRACKET = '>';
    private final char CLOSE = '/';
    private final char EMPTY = ' ';

    Solution5076() {}

    boolean isLegal(String html) {
        Stack<String> stack = new Stack<>();

        int index = 0;

        while (index < html.length()) {
            if (html.charAt(index) == LEFT_BRACKET) {
                if (!((index + 1) < html.length() && html.charAt(index + 1) == CLOSE)) {
                    String keyword = getKeyword(index, html);

                    index = getRightBracketIndex(index, html);
                    if (html.charAt(index - 1) != CLOSE) stack.push(keyword);
                }
            } else if (html.charAt(index) == CLOSE) {
                String keyword = getKeyword(index, html);

                if (stack.isEmpty()) return false;
                else if(!keyword.equals(stack.pop())) return false;

                index = getRightBracketIndex(index, html);
            }

            index++;
        }

        return stack.isEmpty();
    }

    private int getRightBracketIndex(int index, String html) {
        while ((index < html.length()) && (html.charAt(index) != RIGHT_BRACKET)) index++;

        return index;
    }

    private String getKeyword(int index, String html) {
        int length;
        for (length = 1; (html.charAt(index + length) != RIGHT_BRACKET) && (html.charAt(index + length) != CLOSE && (html.charAt(index + length) != EMPTY)); length++);

        return html.substring(index + 1, index + length);
    }
}