KOMAS

[JAVA] 자바 배열 array 사용법

자바의 배열

기본적으로 배열이란 하나의 공통 타입을 갖는 여러 개의 변수들을 모아서 관리하기 위해 사용합니다.

여러 변수들을 라인마다 입력하는 것 보다는 사진처럼 한 줄로 처리하는 게 더 깔끔하고 추후에 관리도 편합니다.

배열을 사용하기 위해 선언하는 방식은 자료형뒤에 [ ]를 붙여주시면 됩니다.

변수 뒤에 [ ]를 붙일 수도 있지만, 코드 가독성에서 자료형 뒤에 [ ]를 붙여주는 것이 "해당 자료형으로 선언된 배열이구나."라고 인식하기 더 좋습니다.

배열 선언의 방법 3가지

방법1은 선언 이후에 초기화를 다음 라인에서 합니다. 주의할 점은 new int [ ] { 요소 1, 요소 2... }를 반드시 작성해주어야 합니다.

방법 2와 방법 3은 동일하며, 방법 3이 간단하여 더 자주 사용합니다.

배열에 요소를 넣지 않고 빈 배열로 크기만 지정해서 사용하는 방법도 있습니다. 크기만 선언하면 요소들은 default로 자동 초기화 됩니다.

int형의 default값은 0이기 때문에 해당 배열은 0으로 모든 요소가 초기화 됩니다.

new int[ ] 내부에 개수를 얼마큼 잡을 것인지 숫자를 넣어주면 됩니다. 10을 넣으면 10개의 int 타입을 저장할 공간을 메모리에 잡습니다.

배열 크기의 확인은 배열변수.length 로 확인할 수 있습니다.

배열 사용의 주의점

배열은 첫번째 요소가 0번부터 시작합니다. 만약 첫 번째 요소를 찾고 싶다면 배열 변수[0]로 찾을 수 있습니다.

첫 번째 요소가 0이므로 마지막 요소는 배열의 크기-1입니다. 

배열 변수[배열 변수. length - 1]로 마지막 요소를 찾을 수 있습니다.

또한 배열 사용의 주의점은 한번 배열의 크기가 결정되면, 이 크기를 변경할 수 없습니다.

그 이유는 배열은 메모리에서 연이어서 생성이 되어있습니다.

배열 변수를 출력해보면 참조값이 나오는데 이 값은 배열 첫 번째 요소의 참조 주소 값입니다.

배열에서 index 위치에 해당되는 값을 (첫 주소의 위치 + 타입 크기 * 찾는 index)로 빠르게 접근할 수 있는 이유입니다. (이어서 연결되어있기 때문)

크기를 변경하면 사용 중인 배열 메모리의 뒷 메모리가 사용하고 있을 수 있기 때문에 배열 크기를 변경할 수 없습니다.

크기를 늘리고 싶다면 새로운 더 넓은 크기의 배열을 선언해서 요소들을 복사해주는 과정을 거쳐야 합니다.

[자바] PriorityQueue  우선순위 큐

• 우선순위 큐
• 시간 복잡도 O(logN)
• 자바 코드

우선순위 큐

자바에는 자료구조 heap을 구현한 우선순위 큐 클래스가 있다.

큐를 생각해보면 가장 먼저 들어온 요소가 가장 먼저 나가게 되는데, 우선순위 큐에서는 요소들이

우선순위를 가져서 들어온 순서와 상관없이 우선순위가 높은 요소가 큐에서 가장 먼저 나가게 된다.

이때 나오는 요소는 우선순위가 가장 높은 heap 자료구조의 최상단 root node이다.

heap 자료구조는 가장 적은 값이나 가장 큰 값을 항상 최상단 root node에 위치시켜 이 값을 내보내는 자료구조이다.

우선순위가 가장 적은 값을 root node로 두면 최소 힙, 우선순위가 가장 높은 값을 root node로 두면 최대 힙이다.

• 중복값을 허용한다.
• 완전이진트리이다.

우선순위큐는 배열로 구현할 수 있다.

부모 node index = (index - 1) / 2

자식 node index = index * 2 + 1 ,  index * 2 + 2

우선순위 큐의 시간 복잡도

우선순위 큐에서의 시간 복잡도는 삽입, 삭제 시 O(logN)의 시간이 걸린다.

삽입시 가장 마지막 위치에 요소를 추가시킨 후 부모 노드와의 비교 후 Swap 과정을 통해 알맞은 위치를 찾아간다.

upHeap

삭제 시 root node를 반환 후 가장 마지막 요소를 root node에 위치시킨 후 자손과의 비교를 통해 Swap 과정을 거쳐

알맞은 위치를 찾아간다. 

자손과의 Swap은 둘 중 우선순위가 큰 node와 Swap한다.

downHeap

큐와 비슷한 성질을 이용하지만, 큐에서는 front 요소의 반환 시간은 O(1)이다. 하지만 우선순위 큐에서는 가장 우선순위가

높은 값을 가져온 후 완전 이진트리로 다시 만드는 과정인 Swap 과정 때문에 O(logN)이 걸린다.

자바 코드

import java.util.*;   public class PriorityQueueT{     public static void main(String[] args) {         Queue<Integer> pq= new PriorityQueue<>();         pq.offer(1);         pq.offer(2);         pq.offer(3);         pq.offer(4);           System.out.println(pq);         System.out.println(pq.poll());           Queue<Integer> pqr= new PriorityQueue<>(Collections.reverseOrder());         pqr.offer(1);         pqr.offer(2);         pqr.offer(3);         pqr.offer(4);           System.out.println(pqr);         System.out.println(pqr.poll());             Queue<Item> qi= new PriorityQueue<>();         qi.offer(new Item(1,"가"));         qi.offer(new Item(3,"나"));         qi.offer(new Item(0,"다"));         qi.offer(new Item(2,"라"));         qi.offer(new Item(4,"마"));           System.out.println(qi);         System.out.println(qi.poll());       } }   class Item implements Comparable<Item>{     int number;     String name;       Item(int number, String name){         this.number = number;         this.name = name;     }     @Override     public int compareTo(Item i){         return this.number - i.number;     }       @Override     public String toString(){         return number +" "+ name;     } }   Colored by Color Scripter

cs

 

 

우선순위 큐를 사용하는 PriorityQueue 클래스를 이용하여 1, 2, 3, 4 요소를 넣었다.

각각 최소 힙을 사용하는 pq와 최대 힙을 pqr을 코드를 작성하고 결과를 봤다.

기본형이 아닌 객체 간의 비교를 통해 우선순위 큐를 이용하는 방법은

Item Class를 작성하여 Comparable 인터페이스를 구현하여 compareTo 함수를 통해 비교 후 

Item Class의 인스턴스 필드인 number를 통해 우선순위 큐의 최소 힙을 사용했다.