구현 - 백준 1157

BOJ/백준 1157 - 단어 공부

백준 1157 - 단어 공부

1. 문제 분석

문제 이해

알파벳 대소문자로 된 단어가 주어지면, 그 단어에서 가장 많이 사용된 알파벳을 출력하는 문제이다
단, 대문자와 소문자를 구분하지 않음

입력

• 첫째 줄에 알파벳 대소문자로 이루어진 단어 S가 있다
• S의 길이는 1,000,000을 넘지 않는다

출력

• 첫째 줄에 단어 S에서 가장 많이 사용된 알파벳을 대문자로 출력
• 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ? 출력

---

2. 시간 복잡도

• 첫 번째 for문 : 문자열 길이 만큼 순회하니까 문자열 길이가 N이라고 했을 때 O(N)
• 두 번째 for문 : 알파벳 빈도 배열 크기 많은 순회하니까 총 26번 돌아간다 O(1)

💡 가장 큰 영향을 미치는 항만 고려하므로 O(N) 이다

---

3. 코드 구현

import java.io.*;

public class No_1157 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 1. 알파벳 빈도 저장 배열
		int[] alphaCount = new int[26];
		
		// 2. 입력 문자열을 모두 대문자로 변환
		String S = br.readLine().toUpperCase();
		
		// 3. 문자열 길이만큼 순회
		for(int i = 0; i < S.length(); i++) {
			 alphaCount[S.charAt(i) - 'A']++;
		}
		
		int max = 0;
		char mostChar = 'A';
		
		// 4. 알파뱃 빈도 배열 크기 만큼 순회
		for(int i = 0; i < 26; i++) {
			if (alphaCount[i] > max) {
				// 새로운 최대값을 max에 갱신
				max = alphaCount[i];
				mostChar = (char) ('A' + i);
			} else if (alphaCount[i] == max) {
				mostChar = '?';
			}
		}
		System.out.print(mostChar);
	}
}

---

이 문제를 풀 수 있는 핵심은 알파벳 개수 26개 만큼의 배열을 만들고 그 배열에게 빈도수를 계산한 뒤 최빈값이 유일한 지 아니면 같은지 확인하는게 핵심이다