Algorithm 풀이를 위한 JAVA 자료구조 정리

본 포스트에서는 JAVA에서 Problem Solving을 위한 자료구조를 다룬다.

 

다룰 항목은 

 

1. ArrayDeque 2. PriorityQueue 3. HashMap 4. HashSet

 

이다. 사용빈도는 각각 다르지만 적절한 자료구조를 선택함에따라서, 시간을 크게 단축할수 있다.

 

ArrayDeque

 

ArrayDeque는 Queue를 상속받아 구현한 것이다. 양방향 큐와 Stack을 동시에 사용할수있는 자료구조이다.

입/출력의 속도가 빠르고 동기화의 부분을 줄이므로 시간을 단축하였다.

 

 

Java Tip #2 : 큐(Queue) 성능 테스트

자세한것은 위 포스팅을 참고하자.

 

선언은

ArrayDeque < Class > 변수이름 = new ArrayDeque<>(InitDeque_size);

 

간단한 주요 기능을 살펴 보자.

 

Queue의 기능과 Stack의 기능을 모두 가지고있다고 생각하면된다.

Queue에서 peek을 할때 First에서할것인지 Last에서 할것인지 선택할 수 있고,

offer (= add) 할때에도 양방향큐의 기능처럼 작동한다.

 

또한 Stack에 기능으로 사용할때에 push / pop 의 기능도 지원하기 때문에 사용자가 원하는대로 사용하면된다.

실행 화면

---

Priority_Deque ( 우선순위 큐 )

 

큐에 들어간 특정요소에 우선순위를 부여하고 싶을때에 사용한다. 

구조는 Tree 구조로 구현되어있으며 Max-heap을 통하여 구현하는데, 간단하게

완전이진트리구조에서 새로운 데이터가 추가되었다면, 맨 마지막남은 Leaf부분에 데이터를 추가하고

Leaf의 부모와 크기비교를하면서 크면 바꾸는 식으로 루트 노드까지 올라가서 적절한 자리에 위치한다.

 

우선순위를 비교하기위해 2가지 방법이 있다.

 

1. Class를 정의할때 compareTo()를 오버라이딩하여 재정의해서 사용하는 방법

2. PQ를 정의할때 Comparator객체의 compare() 메소드를 오버라이딩하는 방법

 

2가지중에서 한가지만 확실하게 다루어 보자

 

PriorityQueue Pq= new PriorityQueue<>(InitPriority_queue_size , Comparator 객체);

 

선언은 위와같이하고, Comparator를 따로 선언하지 않고, 자료형이 하나라면 최대힙구조로 구현되었으므로 

오름차순을 따른다.

 

내림 차순으로 출력하고 싶다면 Collections.reverseOrder()를 Comparator에 추가하자

사실 이런경우에 우선순위 큐를 사용하려는 것이아니다. 실제 BFS를 통해서 탐색할때에 내가 원하는 

 

클래스의 인스턴스에 우선순위를 부여하자.

 

 

Edge를 기준으로 내림차순 정렬

먼저 Pq에는 Node 클래스의 객체가 담긴다고 하자, 우리는 이러한 Node클래스에서 Edge값이 큰 순서대로

먼저 Queue에 앞부분에 오길 원한다.

 

이러한 경우 int 값을 리턴하는 compare메소드를 재정의하게 되는데,

비교할 두 클래스를 인자로 받아서 -1 , 0 , 1의 세 값중 하나로 리턴을하게된다.

 

리턴값이 -1 이나 0 이면 두 객체의 위치를 바꾸지 않고 

1인 경우에 바꾸게 된다.

 

쉽게 설명하기 위해서 Target node를 설정해보자, 우리는 Target Node에 우선순위를 부여할 것이다.

 

위와 같은 상황에서 우리의 타겟노드는 n2이다 즉 어떠한 값하고 비교했을때에 ( 내림차순 기준 ) 

Target에 해당되는 값이 다른 값보다 크면 우선순위를 1 주고, 아닌경우에 -1을 주자.

이렇게 진행한다면, 여러번의 비교로 우선순위가 정해지게 된다. 따라서

큐에 있는 객체들은 지정한 우선순위에 따라서 정렬되게 된다.

 

여러가지우선순위를 어떻게 처리할까? 

 

위와같은 상황에서,

node 객체의 edge를 우선순위로 잡고 edge가 같은 경우에는 number를 기준으로 정렬하고 싶을때에는?

 

적절하게 Comparator를 수정할 수 있다.

바로 예시를 통해서 본다면,

 

적절하게 Comparator를 수정해주자 타겟을 항상 생각해보고 타겟 입장에서 return 값을 결정하자.

 

PS를 위한 람다식

 

이러한 것이 익숙해졌다면 실제 문제를 푸는 상황에서는 두가지에 대한 우선순위를 부여하기 보다는 한가지에 대한 

우선순위로 큐를 정렬하는 경우가 많다, 매번 compare를 오버라이딩 하기보다는 lambda식을 통해서 한줄에 처리하자

 

이렇게도 선언할 수 있다. 

풀어서 생각해본다면,

우리는 node n1,n2를 오름차순으로 비교 할 것인데 Target은 n2 이다.

n1 과 n2의 edge값을 비교하는데 n2가 숫자가 작으면 n2에게 우선순위를 더 주어야겠다

 

정도로 풀어서 생각할 수 있다. 처음에는 익숙하지 않지만 관련 문제를 풀어보자.

 

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD

SW Expert Academy

ExpertAcademy - 보급로 문제

 

 

---

HashMap

 

Map은 Key와 Value로 이루어진 일대일 자료구조라고생각하면 된다. 

파이썬의 Dictionary와 아주 똑같고 Key를 통해서 Value를 가져온다

 

 

선언은 

HashMap<Key, Value> hm = new HashMap<>();

 

으로 선언하고 

Key에는 Wrapper Class나 Reference Type의 객체가 들어간다. 예시를보자

 

 

하나의 키에대해서 값을 여러번 넣는경우에는 마지막에 들어간 값이 그 키에 해당되는 값으로 저장되는 것을 볼수있다.

또한 Hashmap.get(Key) 로 내가 원하는 키에 해당되는 요소를 가져올 수 있다.

 

관련 문제를 풀어보자

 

https://www.acmicpc.net/problem/1620

1620번: 나는야 포켓몬 마스터 이다솜

---

 

HashSet

 

Set 자료구조는 자주사용하지 않지만, 중복을 제거면서 저장되는 자료구조이다.

내가 중복된 값을 넣어도 알아서 제거해준다. 때문에 자료간 순서는 보장되지 않으며,

toArray() 메소드로 들어간 요소를 추출할 수는있지만 PS에서는 중복제거용으로 많이 사용되기에

add() 와 size() 정도만 알면 된다.

 

 

 

---

 

이러한 자료구조를 몰라도 사실 하나하나 코딩 ( Max heap 구현 , 중복제거 ) 등을 구현 할 수있지만 

알고 적절하게 사용한다면 좋을것같아서 정리했다.