MA VPD Tech Blog.

배열과정렬

July 11, 2019 | 8 Minute Read

배열과 정렬 (로또 프로그램)

작성 2019년 7월 11일 이정도

개발조건

  • 입력한 Game수(1~10만) 만큼 로또번호(6개) 추출 Consol 출력(정렬하지 말 것)
  • 모든 숫자(6게임이면 총 36개의 숫자)들 중 가장 많이 나온 숫자 순
    • 동 순위시 작은숫자 순으로 추가 1게임을 더 추출하여 출력해 주는 프로그램.

1차 결과

  • Game수가 1만이 넘어가면서 연산시간이 기하급수적으로 늘어남

  • 중복값 정렬를 위해, 버블정렬를 쓴게 원인으로 판단됨

      // *** 이중 배열 정렬 ***
  int iTmpXvalue = 0;
  int iTmpYvalue = 0;
  for(int x=0; x<iSortArry.length; x++){
      for(int y=0; y<iSortArry.length-x-1; y++){
          if(iSortArry[y][1]<iSortArry[y+1][1]){
              iTmpXvalue = iSortArry[y][0];
              iTmpYvalue = iSortArry[y][1];
              iSortArry[y][0] = iSortArry[y+1][0];
              iSortArry[y][1] = iSortArry[y+1][1];
              iSortArry[y+1][0] = iTmpXvalue;
              iSortArry[y+1][1] = iTmpYvalue;
          }        		
      }
  }

개선을 위한 학습

링크드리스트

  • ArrayList는 데이터들이 순서대로 쭉 늘어선 배열의 형식을 취하고 있는 반면 LinkedList는 순서대로 늘어선 것이 아니라 자료의 주소 값으로 서로 연결되어 있는 구조를 하고 있습니다.
  • 삽입 / 삭제가 빈번하게 발생하는 프로세스의 경우 LinkedList를 사용하여 시스템을 구현 하는것이 바람직하다 할 수 있겠습니다.

b>LinkedList와 ArrayList 비교그림</b>

Dev_JAVA_20190627_001

  • LinkedList는 몇 개의 참조자만 바꿈으로써 새로운 자료의 삽입이나 기존 자료의 삭제를 위치에 관계없이 빠른 시간안에 수행 할 수 있습니다.
  • LinkedList는 무한 개수의 자료를 삽입할 수 있는 반면 (메모리의 용량이 무한정하다고 가정할 때), ArrayList는 크기가 한정되어 있기 때문에 결국 포화 상태에 이르게 됩니다.
  • ArrayList에서는 무작위 접근(random access)이 가능하지만, LinkedList에서는 순차접근(sequential access) 만이 가능합니다.

해쉬맵

Dev_JAVA_20190627_002

  • 예전에는 데이터를 저장하고자 하면 배열에다가 차곡차곡 쌓아놓적이 있습니다. 받는 데이터들을 그대로 저장만 하면 되니 간편하지만, 반대로 데이터를 가져올 때 매우 불편하였습니다. 커질수록 한없이 늘어나는 데이터 속에서 내가 원하는 데이터를 찾는다면 점차점차 느려지게 하였습니다.
  • 그에 따라 이 방법을 보안하고자 점차 발달한게 Key-Value 컨셉입니다. 데이터를 저장하고 특정 키로 검색하면 값을 바로 받아볼 수 있기 때문에 데이터량이 증가되도 빠르게 원하는 데이터를 찾을 수 있었습니다.

링크드해쉬맵

Dev_JAVA_20190627_003

  • HashMap이 순서대로 자료를 유지하기 위한 자료구조가 아님
    • 키-값 쌍이 필요하다 (사진을 찍은 시간과 같은).
    • 전체 크기는 알지 못한다 (실시간 동영상을 찍으므로 전체 프레임 크기가 변할 가능성이 있다).
    • 순서를 알아야 한다 (사진을 찍은 순서대로 동영상으로 변환해야 한다).
    • 이러한 필요가 있을 때, 간편하게 쓸 수 있는 자료구조가 바로 LinkedHashMap입니다. - Hash를 통해 자료를 보관할 필요가 있지만, 원할 때 순서대로 가져와야 하는 경우이죠.
  • LinkedHashMap은 HashMap을 확장합니다. HashMap의 모든 기능을 사용하되, Doubly-Linked List를 내부에 유지함으로써 입력된 자료의 순서를 보관

이터레이터

  • Iterator는 인터페이스이다

  • Iterator 는 자동으로 Index 를 관리해주기 때문에,사용에 편리함이 있을수 있으나 Iterator 를 열어보면 객체를 만들어 사용하기 때문에 느릴수 밖에 없다. 그러므로, list 의 size를 받아와서 사용것이 더 좋다.

  • Map에 값을 전체 출력하기 위해서는 entrySet(), keySet() 메소드를 사용하면 되는데 entrySet() 메서드는 key와 value의 값이 모두 필요한 경우 사용하고, keySet() 메서드는 key의 값만 필요한 경우 사용합니다.

  • Iterator 인터페이스를 사용할 수 없는 컬렉션인 Map에서 Iterator 인터페이스를 사용하기 위해서는 Map에 entrySet(), keySet() 메소드를 사용하여 Set 객체를 반환받은 후 Iterator 인터페이스를 사용하시면 됩니다.

소스

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.LinkedHashMap;
 
public class LottoGame{ 
	 
    public static void main(String[] args) {
    	
    	long start_time = System.currentTimeMillis();
  
        @SuppressWarnings("resource")
		Scanner sc = new Scanner(System.in);
               
        System.out.print("로또번호 추출 개수 입력: ");
        int gameCnt = sc.nextInt();

        List<Integer> lottoNum = new ArrayList<Integer>();
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        for (int i = 1; i <= 45; i++) {
            lottoNum.add(i);                         // 1차원 배열
            map.put(i, 0);                           // 2차원 배열 (숫자, 중복값)
        }

        for (int i = 1; i <= gameCnt; i++) {
        	
            Collections.shuffle(lottoNum);
            
            int[] lottoNums = new int[6];
            for (int j = 0; j < 6; j++) {
                lottoNums[j] = lottoNum.get(j);
                
                int tmp = map.get(lottoNums[j]);
                map.put(lottoNums[j], new Integer(tmp+1));
            }
            
            System.out.println(i + "번째 로또번호: " + Arrays.toString(lottoNums));
        }
        
        List<Map.Entry<Integer, Integer>> list = new LinkedList<>(map.entrySet());
        
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                int comparision = (o1.getValue() - o2.getValue()) * -1;
                return comparision == 0 ? o1.getKey().compareTo(o2.getKey()) : comparision;
            }
        });
        
        Map<Integer, Integer> sortedMap = new LinkedHashMap<>(); 
        for(Iterator<Map.Entry<Integer, Integer>> iter = list.iterator(); iter.hasNext();){
            Map.Entry<Integer, Integer> entry = iter.next();
            sortedMap.put(entry.getKey(), entry.getValue());
        }
        
        System.out.print("보너스 번호: [");
        {
        	Iterator<Map.Entry<Integer, Integer>> iter = list.iterator();
        	for(int i=0; i <6; i++){
        		iter.hasNext();
        		Map.Entry<Integer, Integer> entry = iter.next();
        		
        		if(i == 5){
        			System.out.println(entry.getKey()+"]");
        			break;
        		} else {
        			System.out.print(entry.getKey()+", ");
        		}
        	}
        }
        
        long end_time = System.currentTimeMillis();
        long result_time = end_time - start_time;
        
        System.out.println("[DEBUG] "+ gameCnt +" 게임, 걸린 시간: " +result_time / 1000 + " 초");
    }
}

실행결과

System.out.println를 쓰면 아무래도 출력 때문에 속도가 느리다.

[CASE1] 보너스 번호만 찍을 경우

로또번호 추출 개수 입력: 100000
보너스 번호: [30, 7, 43, 24, 21, 45]
[DEBUG] 100000 게임, 걸린 시간: 5 초

[CASE2] 로또번호와 같이 찍을 경우

100000번째 로또번호: [30, 23, 13, 7, 21, 9]
보너스 번호: [15, 16, 37, 23, 33, 44]
[DEBUG] 100000 게임, 걸린 시간: 10 초

참고자료

로고

© 2023 MarkAny V.P.D Powered by GITHUB