[Java] 베스트셀러 [1302번]

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

• 예제 입력1

5
top
top
top
top
kimtop

• 예제 출력1

top

• 예제 입력2

9
table
chair
table
table
lamp
door
lamp
table
chair

• 예제 출력2

table

• 예제 입력3

6
a
a
a
b
b
b

• 예제 출력3

a

• 예제 입력4

8
icecream
peanuts
peanuts
chocolate
candy
chocolate
icecream
apple

• 예제 출력4

chocolate

• 예제 입력5

1
soul

• 예제 출력5

soul

---

• 문제 접근
  • N개의 책의 제목이 입력 됨
  • 입력된 책의 제목 중 가장 많이 입력된 것을 출력
  • value가 동일할 경우 사전 순 이름 출력
• 문제 해결
  • TreeMap을 이용하여 책 이름(Key)을 추가
  • 이미 존재한다면 수량(Value) 증가
  • MaxValue를 가장 많이 팔린 양 저장

• 슈도 코드

sellCont(책 개수 저장)
Map bookMap 선언
maxValue(가장 높은 수량 저장)
bestSeller(가장 높은 수량의 책 이름 저장)
for(N번 반복){
	bookName에 책 이름 저장
	if(bookMap에 이미 있다면){
		value 1증가
		bookMap의 해당 키(bookName)의 값 갱신
		if(maxValue보다 value가 크면)
			maxValue에 value 저장
		bestSeller에 책 이름 저장
		continue;
	}
	bookMap에 책 이름과 수량 1개로 저장
	if(bestSeller가 null이면){
		bestSeller에 bookName 저장
		maxValue 1 저장
	}
}
if(maxValue가 2이상이라면)
	bestSeller = searchBestSeller(maxValue)
bestSeller 출력

searchBestSeller(value) {
	for(bookMap.entrySet()){
		if(value와 같으면)
			해당 키 반환
	}
}

• 코딩하기

static TreeMap<String, Integer> bookMap = new TreeMap<>(); // 오름 차순 정렬
public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int sellCount = Integer.parseInt(br.readLine());
    int maxValue = 0; // 가장 많이 팔린 값 저장
    String bestSeller = null; // 가장 많이 팔린 책 이름 저장
    for(int i = 0; i < sellCount; i++){
        String bookName = br.readLine();
        if(bookMap.containsKey(bookName)){ // 이미 존재하는 책 이름이면
            int value = bookMap.get(bookName) + 1;
            bookMap.put(bookName, value); // 해당 책의 value를 1 증가
            if(maxValue < value) maxValue = value;
            continue;
        }
        bookMap.put(bookName, 1);
        if(bestSeller == null){ // bestSeller가 null인 1번만 실행
            // sellCount가 1일 경우 해당 책이 베스트 셀러
            bestSeller = bookName;
            maxValue = 1;
        }
    }
    if(maxValue >= 2) // 최고 판매량이 2개 이상이라면
        bestSeller = searchBestSeller(maxValue);

    System.out.println(bestSeller);
}

private static String searchBestSeller(int value) {
    for(Map.Entry<String, Integer> entry : bookMap.entrySet()){
        // 오름차순 정렬이기 때문에 가장 처음 나온 Key이름이 사전순 정렬된 이름
        if(entry.getValue() == value)
            return entry.getKey();
    }
    return null;
}