백준 1302 베스트셀러 (JAVA 자바 풀이)

백준 1302 베스트셀러 (JAVA 자바 풀이)

 

---

 

 

 

---

 

중복되는 값을 찾는 로직을 사용하면 시간 복잡도가 급격하게 올라간다. 검색 수행을 hash로 한다면 O(n^2)은 피할 수 있고 또 시간도 넉넉하기 때문에 그렇게 해도 풀릴 수 있지만 

 

정렬의 특성을 이용하면 보다 간단하게 풀 수 있다. 

 

즉, 정렬이 된 후에 값들이 한 곳으로 모여 있게 된다는 특성을 이용한다. 

 

예를 들어 아래와 같은 데이터를 받아서 정렬하면 

9
table
chair
table
table
lamp
door
lamp
table
chair

 

 

[chair, chair, door, lamp, lamp, table, table, table, table]로 정렬된다. 

 

이러한 값들에 대해서 하나씩 카운팅을 해주면 한 번의 반복문으로 카운팅을 완료할 수 있으므로, O(n)의 시간 복잡도가 된다. 

 

 

---

한편 맵을 이용해서 풀이할 수도 있다. 이때 hashMap을 사용하면 put, remove, containsKey, get 연산에 대해 O(1) ~ O(비교복잡도 * log(size))의 시간 복잡도를 보장 받는다. 

 

따라서 containsKey를 통해 

i) 원소가 존재하는지 

ii) 존재하지 않는지에 따라서 나누고 

 

존재한다면 

get으로 해당하는 key의 value를 가져와 plus 1 시켜 put으로 추가하고 

 

존재하지 않는다면 

그냥 put을 시켜주면 된다. 

 

put 연산은 존재하는 key 값이라면 덮어씌우기 때문에 map에 key와 value를 수정할 수 있는 로직 구현이 가능하다. 

 

이와 동일한 로직을 map의 메서드인 getOrDefault를 통해서 한 번에 해결할 수 있다. 

 

Map<String, Integer> books = new HashMap<>();

while(bookCount-->0){
	String title = bufferedReader.readLine();	
	books.put(title, books.getOrDefault(title, 0) +1);
}

 

 

 

💡 코드 구현

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class Main {

	private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

	public static void main(String[] args) throws IOException {

		int bookCounts = Integer.parseInt(bufferedReader.readLine());

		String[] books = new String[bookCounts];
		while(bookCounts-->0){
			String bookTitle = bufferedReader.readLine();
			books[bookCounts] = bookTitle;
		}

		Arrays.sort(books, Comparator.naturalOrder());

		String topBook =books[0];
		int count = 1;
		int max = 1;
		for (int i =0; i<books.length; i++){
			if (i==0){
				continue;
			}
			if (books[i].equals(books[i-1])){
				count++;
				if (max < count) {
					max = count;
					topBook = books[i];
				}
			} else{
				count = 1;
			}
		}
		System.out.println(topBook);
	}
}