[TIL] 220112

ArrayList의 remove() 메서드가 수행되지 않음

원인

remove() 메서드의 매개변수로 Wrapper 클래스를 전달하면 remove(Object O) 메서드가 실행되기 때문에 실행되지 않음

해결방법

입력 변수로 primitive 타입을 넣어주자.

Integer indexWrapper = 0;
int indexPrimitive = 0;

ArrayList<Integer> ary = new ArrayList<>();

ary.add(1);
ary.add(2);
ary.add(3);

ary.remove(indexWrapper); //[1, 2, 3]
ary.remove(indexPrimitive); //[2, 3]

 

Min-Max heap

알고리즘 문제를 풀던 중 계속 시간초과가 발생하는 문제가 있었다.

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

7662번: 이중 우선순위 큐

 

시간제한이 6초이길래 넉넉할 줄 알았는데 정 반대였다.

시간 복잡도 O(log n)을 넘기면 안되는 문제였고, 나는 O(n log n)이 걸렸기 때문에 기존 풀이로는 해결할 수 없었다.

우선순위 큐를 정렬하는 부분에서 Collections.sort()를 사용한 부분이 문제였다.

Min-Max Heap 이란?

Min-Max Heap는 우선순위 큐의 일종이다.

우선순위 큐는 데이터들을 우선순위로 관리하고, 우선순위가 높은 데이터를 먼저 내보내는 자료구조이다.

 

우선순위 큐는 배열, 연결리스트, 힙 으로 구현이 가능하다. 이 중에서 힙(heap)으로 구현하는 것이 가장 효율적이다.

 

여기서 힙은 완전 이진트리의 일종으로, 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

 

 

min-max heap은 min heap과 max heap의 특징을 동시에 가진 힙이다. 두가지의 힙을 합친 형태에 가깝다.

 

나중에 해당 트리를 구현해보면 좋을 것 같다. 아직 나에게 너무 어려운 구현체인 듯 하다.

 

 

 

자료구조 TreeMap

java에서 제공하는 클래스인 TreeMap이 있다. 

최소, 최대값을 동시에 알아야 할때 시간에서 많은 이득을 얻을 수 있다.

 

TreeMap<Integer,Integer> map1 = new TreeMap<Integer,String>();

map.put(3, 10); //key, value 입력
map.put(2, 5); //key, value 입력

map.remove(1); //key값 1 제거
map.clear(); //모든 값 제거

map.get(2));//value얻기

map.firstEntry(); //최소 Entry 출력 : 2=5
map.firstKey(); //최소값을 가진 Key 출력 : 2
map.lastEntry()); //최대 Entry 출력: 3=10
map.lastKey()); //최댓값을 가진 Key 출력 : 3

 

 

 

 

---

Reference

 

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

https://blog.naver.com/heojh93/220020760884

https://hongssang.tistory.com/11

https://coding-factory.tistory.com/557