시간 복잡도를 보다 빠르게~ 고대어 사전 / ALGOSPOT

문제링크 : https://algospot.com/judge/problem/read/DICTIONARY

이전 포스팅에서 답은 나오지만, 너무 느린 O(N^2) 시간 복잡도를 가진 코드로 작성해서, 이번에는 시간 복잡도를 개선하는 코딩방법에 대해서 알아 보겠습니다.

DICTIONARY / ALGOSPOT 문제는 Topological sort를 사용해서 푸는 문제입니다.

Topological sort는 그래프에 속해있는 vertex와 edge에 따라서 정렬하는 방식임으로, 우선 그래프(graph)를 어떻게 코딩할지를 알아 보겠습니다.

그래프 코딩 방법

크게 2가지 방법이 있구요, 리스트와 2차원 배열을 이용하는 방식입니다.

HashMap과 같은 container를 사용해서, vertex와 edge를 구현하는 것도 가능합니다. 이 부분은 뒤에 여기서 다루겠습니다.

2차원 배열을 이용한, 그래프 코딩 방법

Vertext i와 j가 있고, i 에서 출발해서 j에 도착하는 directed edge가 있을 때, map[i][j] == 1 이라고 표시 한다면 vertex의 갯수가 N 가 일 때, map[N][N] 2차원 배열을 사용해서, 아래와 같이 그래프를 코딩할 수 있습니다.

• 0, 1, 2, 3개의 vertex가 있고, 아래의 2개의 edge가 있다고 가정하면,
• N 은 3 이되고
• {0, 1} 0번에서 출발해서, 1에 도착하는 edge
• {1, 2} 1번에서 출발해서, 2에 도착하는 edge

map[0][1] == 1
map[1][2] == 1

리스트 이용한, 그래프 코딩 방법

자바에서는 ArrayList(C++ 에서는 Vector 등)을 사용해서 edge가 존재하는 것을 코딩할 수 있습니다.

ArrayList<ArrayList<Integer>> all = new ArrayList<>();
all.add(new ArrayList<Integer>());
all.add(new ArrayList<Integer>());

all.get(0).add(1);
all.get(1).add(2);

직접 Vertex와 DirectedEdge를 코딩하는 방법

앞에서 설명한 2가지 방법 처럼, 리스트나 2차원 배열을 이용할 수 도 있지만, 직접 Vertex와 DirectedEdge를 코딩하는 방법도 있습니다.
이 방식을 사용하면, topologicalSort() 메서드에서 걸렸던 시간, O(N^2)을, O(N)으로 줄일 수 있습니다.

Vertex를 코딩한 Vertex 클래스 입니다.

• mV 가 Vertex의 번호, 이 문제 에서는, 입력받은 스트링의 한글자 - 'a'
• mal 은 Vertex에서 출발하는 edge들의 보관하는 리스트 입니다.

    public class Vertex {
        public int mV;
        public ArrayList<DirectedEdge> mal;

        public Vertex(int v) {
            mV = v;
            mal = new ArrayList<DirectedEdge>();
        }
    }

Edge를 코딩한 DirectedEdge 클래스입니다.

• mFm 출발한 Vertex
• mTo 도착한 Vertex

    public class DirectedEdge {
        public Vertex mFm;
        public Vertex mTo;

        public DirectedEdge(Vertex from, Vertex to) {
            mFm = from;
            mTo = to;
        }
    }

topologicalSort() 메서드에서, Vertex를 빨리찾기 위한 HashMap 입니다.

    HashMap<Integer, Vertex> hsmap;

이번 포스팅은 여기 까지하구요, 다음 포스팅 에서 만든 클래스들을 가지고, 문제를 풀어 보겠습니다.