[Kotlin&Spring] 5기 ArrayList 와 HashMap - Kiosk 과제 트러블슈팅

Kiosk 과제 중에 자료를 저장할 곳이 두 개가 필요했다

첫번째는 가게 주인이 키오스크 프로그램 시작시 메뉴 객체를 생성해서 저장할 수 있는 자료형이었다

두번째는 키오스크 손님이 메뉴 객체를 담을 수 있는 장바구니 자료형이었다

 

내가 사용해 본 ArrayList, LinkedList, Array 등의 자료형 내에서는 구현하고자 하는 바를 완벽하게 하기 어려웠다

 

그래서 내가 필요한 자료형의 특징을 정리해봤다

 

메뉴 저장 자료형이 가져야할 기능

1. 메뉴 객체 생성 후 저장이 가능해야 함

2. 메뉴의 종류에 따라 저장하고 찾을 수 있어야 함

3. 메뉴를 출력할 때 빠르게 찾아서 가져와야 함

 

결국에 메뉴 저장 자료의 경우는 빠르게 찾아오는 것이 관건이었다

빠르게 찾을 수 있다는 것은 결국 인덱스가 있어서 탐색이 빨라야한다고 생각했다

또한 저장하는 객체의 종류는 MenuItem 을 상속하는 클래스들이기 때문에 타입의 경우 MenuItem 한 종류로 충분했다

그래서 내가 아는 자료 중 위의 특징을 모두 가진 자료구조는 ArrayList 라고 생각했다

 

그런데 문제는 MenuItem을 상속하는 여러 메뉴가 존재한다는 것이었다

그리고, 나는 메뉴의 가짓수를 제한하고 싶지 않았다

그래서 ArrayList[] 형태의 2차원 ArrayList를 생각하게 되었다

그리고 처음 메뉴 종류를 정한 후에 ArrayList 배열을 원하는 수 만큼 생성할 수 있도록 메서드를 생성했다

그 결과 아래와 같은 메뉴리스트 자료를 만들 수 있었다

메뉴 저장 ArrayList[]

 

장바구니 자료형에 대해서는 처음에 똑같이 ArrayList 로 저장을 했다

그런데 요구사항 중에 장바구니 출력시 메뉴와 함께 수량도 출력하도록 했다

또한 장바구니 출력할 때 정렬하는 기능을 넣고 싶었다

 

내가 생각해본 방법은 먼저 Collection의 sort() 메서드를 사용해 정렬하는 것이었다

그런데 sort() 메서드는 List 만 입력한다고 되지 않았다

왜일까? 하고 살펴보니 sort() 메서드의 내부적으로 Comparator의 compare() 라는 메소드를 이용해 정렬을 하는 구조였다

 

내가 만든 클래스인 MenuItem에는 Comparator 의 compare() 재정의메소드가 없기 때문에 값의 비교를 할 수 없어 정렬을 할 수 없었던 것이다

 

자체적으로 compare() 메소드를 구현하는 방법에는 두 가지가 있었다

첫번째는 MenuItem과 MenuItem을 상속하는 모든 클래스에 인터페이스인 Comparable 을 구현해서 compare() 메소드를 재정의하는 것이었다

두번째는 sort() 메소드 내에 새로운 Comparator 을 생성해 그 내부에 compare() 메서드를 구현하는 것이다

나는 모든 클래스에 Comparable 인터페이스 구현은 중복코드가 많이 발생할 것 같아 두 번째 방식을 택했다

그리고 각 클래스 필드에 int compareNum 을 부여해 그 값으로 compare() 함수를 재정의했다

Collections.sort(shoppingCart, new Comparator() {
            @Override
            public int compare(MenuItem menu1, MenuItem menu2) {
                return menu1.compareNum - menu2.compareNum;
            }
        });

 

compare() 함수를 재정의해서 정렬의 문제는 해결했으나 주문 수량을 체크하는 문제가 남아있었다

int count 라는 변수를 선언해 주문이 생길 때 1 을 더하는 방식으로 하려고 했다

그런데 어떻게 매뉴마다 그 값을 카운팅할지 방법이 생각나지 않았다

결국 활용할 수 있는 다른 Collection 을 찾아보기로 마음먹었다

그리고 어떠한 자료형이 필요한지 정리해보았다

 

장바구니 자료형이 가져야할 기능

1. 존재하는 메뉴 객체 중 선택한 객체 저장

2. 객체(MenuItem)와 객체의 수량(Integer) 2개의 타입과 값을 저장

3. 장바구니를 출력할 떄 중복이 없고 정렬이 되어야함

 

2개의 값을 저장하는 대표적인 Collection 은 Map 과 Map 을 구현하는 HashMap, HashTable 등이 있다

Map 을 구현해보는 것은 처음이여서 가장 많이 쓰이는 HashMap 을 채택해보았다

HashMap은 hashCode() 메소드와 equals() 메소드를 통해 둘 중 하나의 메소드라도 true 값이 나오면 중복 저장을 하지 않는다

이러한 기능은 정렬 메소드와 그를 위한 필드가 필요 없어져서 적합하다고 생각했다

그리고 MenuItem, Integer(수량) 을 간단하게 표현할 수 있어서 적합하다고 생각했다

또한 수량을 카운팅할 때 외부에 드러내지 않고 Map.put() 메소드로 중복 Key 값이 있을 경우 다른 Value 값을 갱신할 수 있다

위의 요구사항을 충족한 나의 장바구니는 아래와 같다

장바구니 HashMap

그러나 자료구조에는 항상 장단점이 함께 존재한다

위의 hashCode() 함수는 해시 함수(Hash function)이다

해시 함수란, 임의 길이의 입력값을 고정 길이의 암호화된 출력으로 변환해주는 함수이다

해시 함수의 단점은 해시 충돌(Hash Collision)이다

해시 충돌이란, 입력값이 달라도 같은 결과값이 나오는 경우가 있다는 것이다

 

해시함수는 Key를 배열의 인덱스로 매핑할 때 사용된다

이 배열의 인덱스를 버킷(bucket)이라고 한다

해시 충돌 발생시 HashMap 은 버킷에 Key-Value 쌍을 저장하기 위해 추가적으로 LinkedList 또는 Tree 의 자료구조를 사용한다

이 경우에 Java 8 이전에는 LinkedList 를 생성해 데이터를 추가했는데 이때 LinkedList 특성상 순회 방식의 탐색이 매우 느리기 때문에 문제가 된다

그러나 Java 8 이후로 추가적인 자료구조에 Tree 를 채택하여 이진 트리(자바: Red-Black Tree)의 빠른 탐색 방식으로 시간 복잡도의 문제를 완화했다

 

이번 과제를 통해 효율적인 자료구조를 사용하기 위해 자료구조 채택 과정에서도 많은 고민이 필요하다는 것을 깨달았다

또한 장단점이 뚜렷한 자료구조가 대부분이기 때분에 같은 기능을 구현해도 개발자의 역량이 중요하다는 것을 깨달았다

이렇게 오늘도 하나 알아가서 좋다

다음에는 시간복잡도의 개념도 공부하고 싶다 화이팅 ~