[백준 1157] 단어 공부 JAVA - LinkedHashSet, HashMap 사용

 
 
 
 
 

---

 
 
 
 
 
기존 코드 - LinkedHashSet 사용

import java.util.LinkedHashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String s = sc.next().toUpperCase();
		Set<Character> hs = new LinkedHashSet<Character>();
		
		for (int i = 0; i < s.length(); i++) {
			hs.add(s.charAt(i));
		}

		Character[] cArr = hs.toArray(new Character[0]);
		int[]arr = new int[hs.size()];
		
		int max = 0;	//가장 많은 수
		int temp = 0;	//현재 수 담을 변수
		int idx = 0;	//max인 index
		int cnt = 0;

            
		for (int i = 0; i < cArr.length; i++) {
			for (int j = 0; j < s.length(); j++) {
				if(cArr[i].equals(s.charAt(j))) {
					temp++;
				}
			}
			arr[i] = temp;
			if(max < temp) {
				max = temp;
				idx = i;
			}
			temp = 0;

		}
		for (int i = 0; i < arr.length; i++) {
			if(arr[i] == max) {
				cnt++;
				if(cnt > 1) {
					break;
				}
			}
		}
		
		if(cnt > 1) {
			System.out.println("?");
		}
		else {
			System.out.println(cArr[idx]);
		}
	}
}

 
코드 55라인, 성능 O(n^2)
 
입력받을 때부터 toUpperCase()으로 대문자로 변환
입력받은 문자열의 중복을 제거하기 위해 HashSet을 사용할건데,
HashSet은 순서가 없기 때문에 LinkedHashSet을 사용
중복 제거한 배열을 다시 Character형으로 변환했다.
 
각 알파벳의 개수를 구하고, 최대값 저장.
이후 최대값이 여러번이면 물음표 출력, 그렇지 않으면 알파벳 출력
 
 
 
 
 
문제는 풀렸지만 성능이 너무 낮은 것 같아 코드를 개선해보았다.
 
 
 
 
 
 
변경 코드 - HashMap 사용

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String s = sc.next().toUpperCase();  
        Map<Character, Integer> freqMap = new HashMap<>();
        
        for (char c : s.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }

        int maxCount = 0;  // 최댓값
        char maxChar = '?';  // 가장 많이 나온 문자
        int duplicateCount = 0;  // 동일 최댓값을 가진 문자의 수
        
        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
            int count = entry.getValue();
            if (count > maxCount) {
                maxCount = count;
                maxChar = entry.getKey();
                duplicateCount = 1;  // 최댓값을 가진 새로운 문자가 발견되면 중복카운트 리셋
            } else if (count == maxCount) {
                duplicateCount++;  // 동일한 최댓값을 가진 문자가 발견되면 중복 카운트 증가
            }
        }
        
        if (duplicateCount > 1) {
            System.out.println("?");
        } else {
            System.out.println(maxChar);
        }
    }
}

 
코드 37라인, 성능 O(n)
 

Map
키-값 쌍(key-value pair)으로 데이터를 저장하는 자료구조
Map을 사용하여 각 문자(키)가 문자열에서 몇 번 등장했는지(값)를 기록

 
Map<알파벳, 빈도 수>를 저장하여 사용한다.
 
 
 
 
 
 

for (char c : s.toCharArray()) {
    freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
}

 

getOrDefault(Object key, V defaultValue)
Map인터페이스에서 제공하는 메서드
특정 키에 대한 값을 조회할 때 유용하게 사용
지정된 키가 존재하지 않으면 기본값을 반환해주는 기능

 
for-each 문으로 빈도 수를 계산한다.
문자가 이미 freqMap에 있으면 그 값을 가져오고, 없으면 기본값 0을 가져와서 +1 하는 원리
 
문자열 ABAB에 대해 freqMap의 변화 
 

• 첫 번째 A -> freqMap은 {'A': 1}             
• 첫 번째 B -> freqMap은 {'A': 1, 'B': 1}     
• 두 번째 A -> freqMap은 {'A': 2, 'B': 1}
• 두 번째 B -> freqMap은 {'A': 2, 'B': 2}

 
 
 
 
 
 

    // 최댓값과 중복 검사
    for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
        int count = entry.getValue();
        if (count > maxCount) {
            maxCount = count;
            maxChar = entry.getKey();
            duplicateCount = 1;  // 최댓값을 가진 새로운 문자가 발견되면 중복카운트 리셋
        } else if (count == maxCount) {
            duplicateCount++;  // 동일한 최댓값을 가진 문자가 발견되면 중복 카운트 증가
        }
    }

Map.Entry
키(Key)와 값(Value)을 하나의 쌍으로 표현

 
ntry.getKey()는 문자를, entry.getValue()는 그 문자의 등장 횟수를 반환
 
 
 
 
 
 
 

    // 결과 출력
    if (duplicateCount > 1) {
        System.out.println("?");
    } else {
        System.out.println(maxChar);
    }

 
결과 출력 후 종료
 
 
 
 
 
 

채점 결과