이번 문제는 고민 했던 것보다 꽤 쉽게 풀어져 가져와보았습니다.

위와 같이 문제가 주어졌습니다.

쉽게 생각해보면 점이 n개 주워졌을 때 x나 y에 평행이 되는 선의 갯수를 구하라는 뜻인데,

여기서 살짝 생각해보면 좋은 점은 x와 y에 평행이 되려면 어떤 조건을 가져야하는가 입니다.

x에 평행이 되려면 두 점의 y좌표는 동일해야할 것이고, y에 평행이 되려면 x좌표가 동일해야할 것 입니다.

즉, x점을 기준으로 묶은 자료와 y점을 기준으로 묶은 자료만 있다면 쉽게 문제를 풀 수 있는 것입니다.

public class Main {

    static Map<Integer, Integer> xLineMap = new HashMap<>();
    static Map<Integer, Integer> yLineMap = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++) {
            String[] strs = br.readLine().split(" ");
            int x = Integer.parseInt(strs[0]);
            int y = Integer.parseInt(strs[1]);
            xLineMap.put(x, xLineMap.getOrDefault(x, 0) + 1);
            yLineMap.put(y, yLineMap.getOrDefault(y, 0) + 1);
        }
        int answer = 0;
        for (int count : xLineMap.values()) {
            if (count > 1) {
                answer++;
            }
        }
        for (int count : yLineMap.values()) {
            if (count > 1) {
                answer++;
            }
        }
        System.out.println(answer);
    }
}

위 문제를 확인해보면 2초의 시간초가 주어지고, n은 최대 100,000이라고 합니다.

이를 통해보면 알고리즘은 O(n)의 성능을 가지고 있도록 작성하는 것이 합리적이라 생각합니다.

위 알고리즘을 보면 n을 받아 n번 반복함으로 O(n)의 시간복잡도를 가지고 있다고 볼 수 있습니다.

또한, n을 받아 사용하는 데이터들을 보면 n개의 데이터들만을 활용하는 것을 볼 수 있어 공간복잡도 또한 O(n) 혹은 O(2n)의 복잡도를 가지고 있습니다.

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)

들어가기에 앞서

해당 글을 작성하기에 앞서 이진트리는 어떤 것인지에 대한 사전 지식이 있어야 이해할 수 있는 글입니다.

만약 이진트리가 무엇인지 모른다면 이 글을 읽고 오시기 바랍니다.

이진 트리 순회

이진 트리를 순회하는 방법에는 어디서부터 확인하느냐로 4가지로 나눌 수 있습니다.

순회 방법에 따라 사용처가 다르게 나오게 되고, 이를 학습함으로써 좀 더 본인이 사용하고자 하는 목적에 알맞은 방법으로 알고리즘을 작성할 수 있습니다.

아래 보이는 이진 트리를 통해 각각의 순회 결과에 대해 알려드리겠습니다.

아래 이진 트리는 이 곳에서 코드로 확인해 보실 수 있습니다.

전위 순회 ( Pre-order Traversal )

전위 순회는 부모 노드 -> 왼쪽 노드 -> 오른쪽 노드 순으로 재귀하며 출력하는 방법입니다.

즉 가장 왼쪽부터 라인부터 탐색하며, 가장 깊은 Level의 오른쪽 노드부터 차근차근 탐색할 수 있게 해줍니다.

public void traversePreOrder(TreeNode<Integer> node) {
    if (node != null) {
        System.out.print(" " + node.getValue());
        traversePreOrder(node.getLeft());
        traversePreOrder(node.getRight());
    }
}

결과

사용처

• DFS 탐색
• 트리 복사

중위 순회 ( In-order Traversal )

중위 순회는 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식노드 순으로 순회하는 방법입니다.

public void traverseInOrder(TreeNode<Integer> node) {
    if (node != null) {
        traverseInOrder(node.getLeft());
        System.out.print(" " + node.getValue());
        traverseInOrder(node.getRight());
    }
}

결과

사용처

• 오름차순 정렬
• 정렬된 데이터 탐색

후위 순회 ( Post-order Traversal )

후위 순회는 왼쪽 자식노드 -> 오른쪽 자식노드 -> 부모 노드 순으로 순회하는 방법입니다.

public void traversePostOrder(TreeNode node) {
    if (node != null) {
        traversePostOrder(node.getLeft());
        traversePostOrder(node.getRight());
        System.out.print(" " + node.getValue());
    }
}

결과

사용처

• 메모리 해제
• 파일 구조 삭제
• 후위 표기법을 통한 연산

레벨 순회 ( Level-order Traveral )

레벨 순회는 root 부터 각 레벨마다 순차적으로 왼쪽부터 오른쪽으로 순회하는 방법입니다.

public void traverseLevelOrder(TreeNode root) {
    if (root == null) return;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(" " + node.getValue());

        if (node.getLeft() != null) queue.add(node.getLeft());
        if (node.getRight() != null) queue.add(node.getRight());
    }
}

결과

사용처

• 최단 경로 탐색
• Bfs 탐색

Reference

https://www.w3schools.com/dsa/dsa_data_binarysearchtrees.php

이진 트리란?

이진 트리는 트리 자료구조의 한 종류로, 각 노드가 최대 2개의 자식노드를 가질 수 있는 구조입니다.

이진 트리를 구성하는 노드들은 3가지로 분리할 수 있습니다.

• 루트 노드 ( Root Node ): 트리의 시작점으로, 부모 노드가 존재하지 않고 이진트리에서 하나만 존재합니다.
• 자식 노드 ( Child Node ): 부모 노드에 속한 노드로써 Left Child와 Right Child로 구분.
• 잎 노드 (Leaf Node): 트리의 마지막에 존재하는 노드로써 자식이 존재하지 않는 노드를 의미합니다.

위와 같이 3가지로 분류할 수 있지만 때에 따라 하나의 노드가 의미하는 바가 겹칠 수 있습니다.

이진 트리 유형

이진 트리는 속한 노드들의 상태에 따라 아래와 같은 유형들로 분류할 수 있습니다.

균형 이진 트리 ( Balanced Binary Tree )

모든 자식 노드들의 Level차이가 최대 1 이하 차이나는 트리입니다.

즉, 한 노드에 쏠림 현상이 발생하지 않고 아래와 같이 규형 잡힌 상태를 의미합니다.

포화 이진 트리 ( Full Binary Tree )

모든 자식 노드가 0개 혹은 2개씩 채워진 상태를 의미합니다. 

완전 이진 트리 ( Complete Binary Tree )

완전 이진트리는 마지막 레벨을 제외 모든 노드들이 채워져 있는 상태를 의미합니다.

이때 자식 노드는 왼쪽부터 차 있어야 합니다.

이진 트리 표현

이진 트리는 배열과 링크드 리스트를 통해 표현할 수 있습니다.

Array 표현

배열을 통해 이진트리를 표현할 경우 아래와 같은 규칙을 통해 표현할 수 있습니다.

• 루트는 배열의 0번째 인덱스 혹은 1번째 인덱스에 존재한다.
• 왼쪽 자식인덱스 = 루트 인덱스 == 0 ? 부모 인덱스 * 2 + 1 : 부모 인덱스 * 2;
• 오른쪽 자식 인덱스 = 루트 인덱스 == 0 ? 부모인덱스 * 2 + 2; 부모 인덱스 * 2 + 1;

위와 같은 규칙을 가지고 이진트리를 표현하였을 때 단점이 존재하는데,

이는 배열로 구현하다 보니 초기 이진트리의 크기가 특정된다는 점이고, 이는 이진트리 내 데이터가 골고루 분포되지 않다면 메모리 자원을 비효율 적으로 사용한다는 단점이 존재합니다.

public static void main(String[] args) {
        int[] arr = new int[7];
        // Root
        arr[0] = 1;
        // Level 1
        arr[1] = 2;
        arr[2] = 3;
        // Level 2
        arr[3] = 4;
        // Level 3
        arr[5] = 6;
        arr[6] = 7;
        printTree(arr);
}

코드로 작성하면 위와 같이 작성을 할 수 있고, Terminal에 출력할 경우 위와 같이 출력해 볼 수 있습니다.

public static void printTree(int[] arr) {
        int level = 0;
        int index = 0;
        while (index < arr.length) {
            int nodesInLevel = (int) Math.pow(2, level); // 해당 레벨의 노드 개수
            for (int i = 0; i < nodesInLevel && index < arr.length; i++) {
                System.out.print(arr[index] + " ");
                index++;
            }
            System.out.println(); // 각 레벨 출력 후 줄바꿈
            level++;
        }
 }

Linked List 표현

Linked List로 표현할 경우 좀더 효율적으로 생성이 가능하다는 장점이 있지만, 균형 이진 트리인 경우 배열로 구현하는 것이 더욱 효율적이라 생각합니다.

우선 우리가 알고 있는 java.util.LinkedList 구현체로 구현하는 것은 아닙니다.

LinkedList의 구현체 중 데이터 저장 클래스인 Node를 확인해보면 Node안은 아래 필드들로 구현되어있습니다.

• E item
• Node<E> next
• Node<E> prev

위와 같이 이전과 이후에 대한 주소를 얻을 수 있지만 우리가 원하는 이진트리를 구현하기 위해서는 next가 leftNext와 rightNext로 나눠져야합니다.

그리하여 직접 구현한다면 아래와 같이 구현할 수 있습니다.

public static class TreeNode<E> {
        private E item;
        private TreeNode<E> left;
        private TreeNode<E> right;

        public TreeNode(E item) {
            this.item = item;
        }

    }

    public static class BinaryTree {
        TreeNode<Integer> root;

        public void add(Integer item) {
            root = addRecursive(root, item);
        }
        private TreeNode<Integer> addRecursive(TreeNode<Integer> current, Integer item) {
            if (current == null) {
                return new TreeNode<>(item);
            }

            if(current.item > item) {
                current.left = addRecursive(current.left, item);
            } else {
                current.right = addRecursive(current.right, item);
            }

            return current;
        }
}

root를 기준으로 왼쪽은 작은값, 오른쪽은 큰값으로 셋팅되게 구현하였습니다.

검색의 성능을 높이기 위해 최소 힙, 최대 힙, 탐색 이진 트리 등등 다양한 방법으로 구성될 수 있으며,

해당 내용들은 다음 글에 작성하도록 하겠습니다.

Reference

https://www.w3schools.com/dsa/dsa_data_binarysearchtrees.php

개요

우리들에게 URL은 매일 수십 번을 적고, 복사하고, 붙여 넣는 혹은 알게 모르게 사용하고 있는 자원입니다.

이렇듯 우리가 여러 사이트들을 접근하기 위해서는 URL을 사용하여 접속을 해야 하는데,

어떻게 접근할 수 있는 것인지 그리고, URL자원들은 어떤 의미를 가지는지를 알아보도록 하겠습니다.

URL

우리가 URL를 통해 어떻게 사이트를 호출할 수 있는지를 알기 위해서는 URL이 뭔지 그리고 내부 요소들은 무엇이 존재하고, 어떤 의미를 가지는지를 먼저 이해하는 게 중요합니다.

URL은 인터넷에서 고유한 식별 주소입니다.

여기서 중요한 게 URI와 URL를 혼동할 수 있는데,

URI는 식별자이고, URL은 식별자 + 프로토콜 + 행위 등을 전부 포함한 것입니다.

그럼 식별자는 무엇이고, 프로토콜, 행위들이 URL의 어떤 부분인지 알아보도록 하겠습니다.

URL해부

Naver의 환율 계산하는 사이트의 주소를 해부해 보도록 하겠습니다.

https://finance.naver.com/marketindex/?tabSel=exchange#tab_section 

Schema

처음 나오는 부분은 Schema입니다.

이는 브라우저가 요청을 처리할 시 사용할 프로토콜을 나타내게 됩니다.

Authority

권한 부분입니다.

이는 많은 URL마다 다른 부분인데 현재 색칠되어 있는 부분 finance.naver.com은 도메인이라고 부릅니다.

원래 IP와 Port가 명시되어 있어야 하지만 사이트마다 다 다른 IP와 Port를 외우는 것은 너무 힘들겠죠??

그리하여 DNS라는 도메인과 IP정보를 가지고 있는 서버를 사용하여 도메인을 명시할 경우 서버에게 해당 도메인의 IP를 받아와서 호출하고자 하는 서버를 호출하는 방식으로 통신을 하고 있습니다.

Path to resource

경로입니다.

이는 앞서 도메인을 통해 서버를 호출하였다면, 해당 경로 정보를 통해 원하는 콘텐츠를 제공하는 API 혹은 페이지를 접근할 수 있도록 즉 웹서버에서 해당 요청을 처리할 수 있는 위치를 특정하는 경로입니다.

Parameters

매개 변수입니다.

콘텐츠를 제공받기 위해 필요한 정보를 나타내며,

시작지점은 /가 아닌?로 표기하게 되고 이 뒤에 붙는 자원들은 Key Value형태로 명시되게 됩니다.

여러 개를 요청할 경우 &를 붙여 동일하게 Key Value형태로 명시하게 됩니다.

이는 Path to resource를 통해 콘텐츠를 제공해 줄 수 있는 서버 내 위치를 특정하고,

콘텐츠를 제공받기 위해 받아야 하는 정보들을 Parameters로 제공을 받게 됩니다.

Anchor

해당 페이지 내 행위입니다.

이는 페이지 내에서 원하는 행위를 표기하게 됩니다.

이는 무엇인가??

우리는 앞서 원하는 콘텐츠를 제공받기 위해 서버의 위치를 특정하고, Parameters로 원하는 정보까지 넘겨줬습니다.

하지만 우리가 받은 콘텐츠에서 어떤 행위를 의도하고 싶으면 어떻게 해야 할까요??

아리송한 말이죠? 우리가 네이버에 접속했다고 생각해 봅시다.

만약 우리가 네이버에만 접속하는 게 아닌, 접속했을 때 달력이 펼쳐져 있길 원한다면 어떻게 해야 할까요?

이렇듯 서버로부터 제공받은 콘텐츠에서 어떤 행위가 발생한 시점으로 처음부터 가기를 원한다면 Anchor를 통해 명시한다로 보면 될 것 같습니다.

콘텐츠를 서버로부터 받고 난 이후 처리하는 자원이기 때문에 당연히 서버에서는 사용하지 않는 자원입니다.

Reference

https://developer.mozilla.org/en-US/docs/Learn/Common_questions/Web_mechanics/What_is_a_URL

개요

Web Developoer로써 활동을 하고 있으면서 평소 당연하게 생각한 것들에 대해 다시 돌아보는 와중

WebServer와 WAS에 대해 설명할 수 있나 라는 생각이 들었습니다.

이에 기본기를 돌아보며 정리를 해보려 합니다.

WebServer란?

WebServer는 주로 HTTP통신을 처리하는 서버입니다.

클라이언트가 웹브라우저에서 URL를 통해 서버로 요청을 보내면, 서버는 해당 요청을 받아 일치하는 정적 콘텐츠( HTML, CSS, Javascript, image,... )를 제공하게 됩니다.

WebServer의 특징으로는 동일한 요청에 대해 동일한 파일을 반환합니다.

즉 WebServer는 웹 브라우저의 화면을 구성하는 요소들을 반환한다고 보면 좋을 것 같습니다.

주로 Apache Server, Nginx 등을 사용하고 있습니다.

WAS(Web Application Server)란?

WAS란 Web Server와 Web Container를 가지는 서버입니다.

주로 사용자의 요청을 받아 비즈니스 로직을 통해 처리하며, 데이터베이스 연동이 이뤄지는 작업이 있을 때 사용하는 서버로, 동적 콘텐츠를 제공받게 됩니다.

WebServer와 다르게 화면을 구성하는 요소들을 반환하는 것이 아닌,

화면을 구성하는데 필요한 데이터들을 연산, 데이터베이스 연동을 통한 CRUD 등의 작업들을 수행하고 반환하는 역할을 담당합니다.

주로 Tomcat 등을 사용하고 있습니다.

사용처

위에서 소개했듯이 용도에 따라 사용하는 서버가 다른데요,

페이지를 만들 때는 WebServer, 데이터를 필요로 할 때는 WAS를 사용하면 될 것으로 보입니다.

그럼 실제로는 어떻게 사용하고 있을 까요??

실제로는 두 개를 병합하여 사용하고 있습니다.

Tomcat의 경우 Apache Tomcat으로도 부르는데 이는 2008년부터 Tomcat에 Apache 즉 WebServer가 추가되어 있기 때문입니다.

그럼 Tomcat은 WAS이니 Tomcat만 쓰면 되겠네요???

제가 경험한 개발은 상황에 따라 다르게 사용하는 점이 많다는 것인데요.

Apache Tomcat만 사용해도 제작은 가능합니다.

하지만 Web Browser에서 WebServer로 요청을 보내고, WebServer에서 데이터를 얻기 위해 WAS에 요청을 보내게 됩니다.

이렇듯 서비스가 제대로 동작하려면 다수의 요청을 수용가능해야 하는데요,

WAS로 띄워버린다면 하나의 서버가 너무 많은 요청을 처리해야 하게 되는데 이는 좋지 않은 상황을 발생할 수 있습니다.

또한 WebServer는 요청에 대한 처리가 정적 콘텐츠를 제공하는 만큼 많은 자원을 필요로 하지는 않지만,

WAS의 경우 다양한 비즈니스로직 처리, DB와의 연동을 통해 데이터를 주고받으려면 어쩔 수 없이 많은 자원을 소모할 수밖에 없습니다.

그럼 많은 요청을 처리하기 위해서는 어떻게 해야 할까요??

만약 Apache Tomcat으로 모든 것을 처리할 경우 WAS만 여러 대 띄우게 될 것입니다.

이는 WebServer도 같이 여러 대 뜬다는 것인데요, 이는 불필요하게 서버 자원을 소모하는 요인으로 만약 이렇게 한다면 서버를 띄우는 컴퓨터 혹은 클라우드의 비용이 들게 됩니다.

그렇기에 WebServer와 WAS를 분리하여 가져가며 WebServer는 하나, WAS는 여러 개를 띄움으로써 많은 요청들을 효율적이게 처리하게 하는 방법을 현재 많이 사용하고 있습니다.

하지만 사용자가 많지 않고 WAS로 띄운 서버 성능도 별로 좋지 않아도 된다 하면,

Apache Tomcat에 한 번에 개발하는 것이 번거롭지 않고 편하겠죠.

즉 상황에 맞게 적용하시는 것이 좋을 것으로 보입니다.

References

https://developer.mozilla.org/en-US/docs/Learn/Common_questions/Web_mechanics/What_is_a_web_server

https://www.ibm.com/topics/web-server-application-server

Stack이란?

Stack은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO( Last In First Out ) 자료구조입니다.

추상자료형( abstract data type, ADT )이며, 이는 논리적인 기능을 명시해 놓은 것이라 볼 수 있고, 이는 구현체가 이를 상속받아 구현하는 방식으로 자료형은 Stack이지만 구현은 여러 방법으로 구현할 수 있음을 의미합니다.

Stack은 Vector를 상속받아 구현을 하고 있는데 이는 Vector를 구현되 LIFO방식으로 데이터를 다룰 수 있게 다루기 위해 Stack이란 자료형이 존재한다 생각해 볼 수 있습니다.

우선 기본적인 기능을 확인해 보겠습니다.

Stack은 Vector를 상속한 ADT이기 때문에 기본적으로 Object []인 elementData로 데이터를 관리하고 있습니다.

배열의 크기는  기본적으로 10의 크기로 생성하고 있으며, resizing을 통해 많은 데이터가 들어오더라도 수용할 수 있습니다. 이렇듯 대부분의 기능은 동일하지만, 외부에서 접근할 수 있는 pop메서드를 확인해 보면 elemtnData의 Size를 확인하여 맨 마지막 데이터만을 추출할 수 있도록 구현되어 있는 것을 확인할 수 있습니다.

public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

제공하는 기능

사용처

그럼 Stack은 어떤 곳에서 사용하게 될까요??

웹브라우저 History 즉 뒤로가기 앞으로가기 와 같은 기능처럼 history를 쌓아두고 이를 최신 것부터 접근하는 상황이 있다면 이럴때는 Stack을 사용함으로써 편하게 관리할 수 있습니다.

또한 재귀함수와 같이 연산이 루프를 도는 방향의 알고리즘을 구현을 한다면,

최근 접근 한 것들을 접근 할 수 있는 Stack을 통해 쉽게 최근에 넣은 데이터를 꺼내 연산을 하면서 손쉽게 구현할 수 있습니다. 백준 코딩 테스트

References

https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

스펙

OS: MAC OS

VM Tool: UTM

설치 OS: Ubuntu-22.04.3

설치

UTM 설정

 1. Virtualize와 Emulate중 선택

2. 설치할 OS선택

3. 설치할 Linux image 선택 및 적용

4. 스펙 설정

5. 저장공간 설정

6. VM이름 설정 및 Setting

7. VM설치시 처음 접하는 화면 

Try or Install Ubuntu Server 선택 이후 기다리면 다시시작된다.

8. 언어 설정

9.

10. 언어설정

11.

12. 네트워크 설정

13. 프록시 설정

14. storage layout설정

15. Storage 설정

16. Ubuntu Pro 업그레이드 설정

17. SSH 설정

18. 인기많은 서버 Snaps 설정

19. Ubuntu 기본 셋팅 

기다리다 Reboot now 버튼이 생기면 Reboot now버튼을 클릭하여 리붓

20. 설치완료

이후 다시 접속 시 아래와 같이 UbuntuOs VM완성 초기 설정한 ID와 Password로 접속 가능하다.

주제

금주 테코테코의 주제는 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;
    }
}