Collection과 Iterator

알고리즘 문제 '나무 재테크' 백준-16235 문제를 풀다가

PriorityQueue를 이용할 일이 생겼다. 앞으로 줄여서 pq라고 하겠다.

푸는 과정에서, pq에 있는 값들을 모두 조회해야 하는 일이 발생했다.

처음에는 일반적인 반복문인 for(int i = 0; i < pq.size(); i++)를 이용해 pq.get(index)를 하려고 했다. 앞으로 fori문이라 하겠다.

하지만 pq는 get() 메서드를 가지고 있지 않았고, poll(), peek(), element() 등만 가졌을 뿐이라. 인덱스로 전체를 조회하는게 불가능하단 것을 알았다.

하지만 뭔가 향상된 for문은 될 것 같은 느낌이 들어서 이용해봤더니 pq 내부 모든 요소에 조회가 가능했다 !

 

pq내부 메서드에는 .get()이 없다..!!

 

궁금증이 들었다.

그동안 fori나 foreach문이나 똑같이 반복을 도는 줄로만 알고 있었고, 단지 foreach문은 빠르게 모든 내용을 간편하게 조회할 때 사용하고, fori문은 index를 이용하여 접근해야할 때 사용하면 좋다고만 알고있었는데,

내 상식에서는 같은 pq에 있는 값들을 조회하는데 fori는 안되고 foreach는 가능하다는 것이 이해할 수 없었다.

 

그래서 원인을 찾아보았다.

 

먼저 pq가 구현하고 있는 Collection이라는 개념을 알아야 한다. Collection은 대부분 알다시피 List, Set, Map, Queue 등 다양한 컬렉션 클래스들이 구현하는 기본 인터페이스이다. 말그대로 자료들의 모음이라고 볼 수 있겠다. ex) 이것들이 내 건담 컬렉션이야! = 내 건담 모음이야. = 같은 자료형(건담)을 모아놨어.

여기서 중요한 점은 Collection은 Iterable 인터페이스를 구현한다는 것이다.

 

그리고 Iterable 인터페이스는 

 

Iterator 객체를 반환하는 iterator() 메서드를 가지고 있다.

 

* 여기서 잠깐, 위 Iterable 인터페이스에 존재하는 forEach()메서드 발견했을 것이다.

그래서 향상된 for문이 이 forEach()메서드 인거냐! 란 생각이 들 수 있을 것이다. (나만 했을지도 ...)

하지만 여기서의 forEach()메서드는 Java 8에서 추가된 메서드이다. 이쯤이면 감이 오시는 분들도 계실텐데,

forEach()는 람다 표현식이나 메서드 참조를 사용하여 컬렉션의 각 요소에 대해 실행할 작업을 정의할 수 있게 해주는 메서드인 것이다. forEach() 메서드는 내부적으로 컬렉션의 Iterator를 사용하여 각 요소를 순회하며, 사용자가 지정한 액션을 각 요소에 대해 수행한다. (ex. collection.forEach(item -> {   }); 즉, 함수형 프로그래밍에 주로 쓰이는 메서드인 것이다. 

 

다시 돌아와서, 

향상된 for문(Enhanced for loop)는 자바 5때 도입된 문법일뿐이다. 즉, 언어 개발자들이 우리랑 한 약속이라는 말이다.

(자바 : 향상된 for문을 쓰면 이 Iterator 기능을 하게 해줄게~)

java는 컬렉션 또는 배열의 순회를 편리하게 하기 위해 향상된 for문을 도입했고, 특징은 Iterable 인터페이스의 iterator() 메서드를 이용해 컬렉션을 순회한다는 것이다.

그렇다면 iterator() 메서드가 뭐길래 컬렉션 내부를 다 순회하게 도와줘??란 의문이 들텐데, 앞 코드에서 봤듯이, iterator() 메서드는 Iterator 인터페이스를 반환한다. 그리고 Iterator 인터페이스는 hasNext()와 next() 메서드를 가진다.

hasNext()는 다음 값이 있는지 확인하고 true/false를 반환하는 메서드고,

next()는 다음 값을 가져와서 반환하는 메서드이다!

헉, 이제 보니 우리가 흔히 쓰는 Scanner도 Iterator를 구현하잖아 !?

 

즉, Collection이 Iterable 인터페이스를 구현하고,

Iterable 인터페이스 안에 iterator()라는 메서드가 있는데, 이 메서드는 Iterator를 반환한다. 

그리고 이 Iterator 인터페이스에는 hasNext()와 next()가 존재하므로

그래서 foreach문을 사용할 때, java는 이 iterator() 메서드를 호출하여 얻은 Iterator 인터페이스의 메서드들을 사용할 수 있게 되면서 모든 요소 순회가 가능한 것이다.!!

 

흐름을 정리해 보자면,

1. 향상된 for문 사용 (반복하고자 하는 Collection의 iterator() 메서드 호출)
2. 컬렉션은 Iterable 인터페이스를 구현하므로 iterator() 메서드 호출 가능.
3. iterator() 메서드는 Iterator 를 반환.
4. Iterator 내부의 hasNext(), next()를 통해 모든 요소 순회 가능.

즉, Iterable 인터페이스를 구현하고 있는 클래스(대표적으로 Collection)만이 향상된 for문을 사용할 수 있다는 것이다.

다르게 말하면 Iterable 인터페이스를 구현한다는 것은 그 클래스의 인스턴스가 '반복 가능'하다는 것을 의미한다.

 

하지만 또 의문이 들 것이다. 난 향상된 for문 아니여도 그동안 fori문으로 .get()을 통해 Collection들 잘 조회해왔는데??

맞다. 가능하다. 하지만 반만 맞다. 왜냐하면 순서가 있는 Collection에만 가능하기 때문이다.

왜냐하면 순서가 없다면 fori문에서 요소에 접근하기 위해 인덱스를 사용할 수 없기 때문이다.!

예를 들어 HashSet은 요소의 순서가 없다. = 요소에 인덱스로 접근하면 매번 값이 바뀐다. = 즉, 말이 안된다. 조회가 불가능하다. = 개별 조회는 값이 계속 바뀌니 불가능하고 차라리 전체 조회는 가능하다. 단, Iterator를 통해서!

 

이제 진짜 내가 처음에 원하던 물음에 근접했다. 왜 pq는 .get()으로 모든 요소 조회가 안되지??

그 이유는 Heap 자료구조의 특성때문이다. pq는 일반적으로 힙(Heap)을 통해 구현되며, Heap은 완전 이진 트리의 일종이다. 즉, 각 노드가 자식 노드보다 우선순위가 높거나 같은 특성을 가진다는 것이다. 자세한 내용은 생략하고,

한마디로 pq 의 목적은 우선순위이다.

하지만 pq는 내부에 배열을 통해 값을 관리한다. 어? 그러면 배열을 통해 관리하니까 인덱스로 접근하면 되는거 아니에요? 라 생각할 수 있겠다.

pq 내부의 배열 존재.

하지만 pq 내부 배열은 단순히 리스트가 아니라 힙(Heap) 구조로 조직된다.

즉, 우리가 흔히 아는 배열과는 다르다고 생각하면 된다. 값을 넣고 뺄때 배열의 위치가 시시각각 변한다.

예를 들어, pq에 3, 1, 2를 차례대로 넣으면 힙 구조를 유지하기 위해 1, 2, 3으로 조직될 것이다. 이토록 인덱스와 값의 위치가 계속 바뀐다. 

 

이 힙 구조는 요소가 우선순위에 따라 정렬되어 있지만, 배열의 순서대로 요소가 저장되어 있는 것이 아니다. 따라서 인덱스를 사용하여 특정 위치의 요소를 조회하는 것이 의미가 없고, 실제 우선순위와 배열 내의 위치가 일치하지 않을 수 있다!

이 상황에서 .get()메서드와 같이 특정 인덱스에 접근하는 것은 pq의 사용 목적과 구조상의 이유로 알맞지 않은 것이다. 왜냐하면 pq는 우선순위에 기반하여 요소를 관리하기 위해 특별히 설계된 자료구조이기 때문이다.

 

사실, 여기서 든 의문은 그래도 내부 배열로 관리하니까 .get(index)를 하면 값이 반환되긴 할 것 같은데?? 이다. 아무리 값이 시시각각 변한다해도 물론 원하는 값 조회는 안되겠지만 어차피 전체를 조회할 거면 상관 없고, fori문을 통해 모두 .get()을 통해 가져올 수 있지 않을까? 라는 생각이 들었는데

예를 들어보자.

순서가 없는 HashSet에 1, 3, 2가 존재하고, 값 전체 조회를 위해 fori문 .get()으로 조회를 한다면 get(0)일 때, 3이 나오고, get(1) 일때도 3이 나올 수 있으므로 전체 조회가 불가능하다. = fori문을 통한 전체 조회는 절대 불가능하다.

pq 도 비슷한 원리이다.! 단지 pq는 fori문을 통한 .get(index)로 순회할 때 같은 값이 중복해서 나올 수는 없다. 하지만 앞서 말한 pq의 사용 목적과 구조상 막아놓았다고 생각한다.

* 더 찾아보니, pq는 요소의 우선순위에 따라 정렬이 되지만, 내부적인 저장 순서는 우선순위와는 독립적으로 관리될 수 있기 때문에 인덱스를 통한 접근이 일관성 있는 순서를 보장하지도 않는다고 한다.

 

 

* fori문도 for(Interator<Integer> it = list.iterator(); it.hasNext();) {   sout(it.next());    } 이런식으로 조건문에 hasNext()를 걸고, 초기값에 객체 생성해서 iterator 를 통한 순회가 가능하다. 하지만 이럴거면 향상된 for문을 쓰는게 좋다. iterator()를 자동으로 해주니까.

 

 

 

 

 

 

 

 

* 더 공부할 것 (아직 잘 모름)

Iterable 인터페이스 구현하지 않는 클래스를 향상된 for문을 사용하려면?

- 향상된 for문, 즉 Java에서의 `for-each` 루프는 내부적으로 `Iterable` 인터페이스를 사용합니다. 클래스가 `Iterable` 인터페이스를 구현한다는 것은 그 클래스의 인스턴스가 "반복 가능"하다는 것을 의미하며, 이는 해당 클래스가 `iterator()` 메소드를 제공하여 클래스의 요소들을 순회할 수 있는 `Iterator` 객체를 반환한다는 것을 의미합니다. 따라서, 어떤 클래스가 `Iterable` 인터페이스를 구현하지 않는다면, 그 클래스의 인스턴스는 향상된 for문에서 직접 사용될 수 없습니다. 예를 들어, `Iterable` 인터페이스를 구현하지 않는 클래스의 객체를 향상된 for문에 사용하려고 하면 컴파일 에러가 발생합니다. 이러한 제한에도 불구하고, 해당 클래스가 반복 가능한 특성을 가지고 있다면 (즉, 내부적으로 순회할 수 있는 요소들을 가지고 있다면), 클래스 내에 `Iterable` 인터페이스를 구현하거나 클래스 외부에서 해당 클래스의 인스턴스를 순회할 수 있는 `Iterator`를 제공하는 래퍼 클래스(wrapper class)나 메소드를 구현함으로써 향상된 for문에서 사용할 수 있게 할 수 있습니다. 예를 들어, 자바의 `java.util` 패키지에 있는 대부분의 컬렉션 클래스들은 `Iterable` 인터페이스를 구현하고 있어서, 이들은 모두 향상된 for문에서 사용될 수 있습니다. 그러나 특정 클래스가 이 인터페이스를 구현하지 않는다면, 해당 클래스의 객체들을 향상된 for문에서 직접 사용하기 위해서는 추가적인 작업이 필요합니다.

 

 

 

stream.forEach() 자세히 공부하기

 

 

 

 

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

16235번: 나무 재테크