인기 상품 구하기

문제. 온라인 쇼핑몰에서 상품을 팔려고 합니다. 상품은 A, B, C, D, E로 등록되어있고 팔릴때마다 자동으로 기록됩니다. 팔린 총 횟수는 n번이고 이 중 가장 많이 팔린 인기상품은 어떤 상품인지 출력하십시오 .

 

입력예시 

15
BACBACCACCBDEDE

 

답 : C

 

나의 답변 

import java.util.HashMap;
import java.util.Scanner;

public class Main {	
	public char solution(int n, String s){
		char answer= ' ';
		int max = Integer.MIN_VALUE;
		HashMap<Character, Integer> map = new HashMap<>();
		for( char x: s.toCharArray()) {
			if(map.containsKey(x)) {
				map.put(x, map.get(x)+1);
			} else {
				map.put(x, 1); 
			}
		}
		for( char key : map.keySet()) {
			int cnt = map.get(key);
			if(cnt>max) {
				max=cnt; 
				answer = key; 
			}
		}
		return answer;
	}
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s = sc.next(); 
		System.out.println(T.solution(n, s));
	}
}

 

 

상품과 그 상품이 팔린 횟수가 1대1로 쌍을 이루고 있다.

이 문제에서는 순서는 중요하지 않으므로 HashMap을 사용해서 구하였다.

 

HashMap이란?

 

키(Key)와 값(Value)의 쌍으로 데이터를 저장합니다.

• 순서가 없다 - 첫번째로 저장한다고 해서 첫번째 자리에 저장되는 것은 아니다.
• 빠른 검색과 삽입이 가능하다 - 특정한 키를 통해 검색하고 그것은 1 대 1로 쌍을 이루므로 시간복잡도가 O(1)이다.

HashMap과 ArrayList 비교하며 총 정리 

• HashMap
  • 순서 없음 
  • 특정한 키를 통해 빠른 검색
  • 데이터 개수가 일정한 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘리는 방식으로 동작  
•  ArrayList 
  
  • 순서 있음
  • 순차적인 데이터에 접근이 자주 필요 / 크기가 동적으로 변할 시 
  • 데이터가 늘어나는 만큼 크기가 동적으로 늘어나 메모리 효율적 사용