백준 1157번 : 단어 공부

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

1157번: 단어 공부

문제

알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.

 

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

오답

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        String str = scan.nextLine();

        String bestChar = "";
        int bestCount = 0;
        for(int i=0; i<str.length(); i++) {
            int count = 0;
            String s1 = String.valueOf(str.charAt(i));
            for(int j=0; j<str.length(); j++) {
                String s2 = String.valueOf(str.charAt(j));
                if(s1.equalsIgnoreCase(s2)) { //대소문자 무시 비교
                    count++;
                }
            }
            if(count > bestCount) {
                bestCount = count;
                bestChar = s1;
            } else if(count == bestCount && !bestChar.equalsIgnoreCase(s1)) {
                bestChar = "?";
            }
        }
        System.out.println(bestChar.toUpperCase());
        System.out.println(bestCount);
    }
}

문제 보고 그냥 간단하게 이중반복문 사용해서 1:1로 풀어서 제출했더니 바로 메모리 초과가 나버렸다.

그래서 사람들은 어떻게 풀었나 검색해보니까..역시 이중반복문을 사용하지 않고 알파벳 배열을 하나 만들어서 푸는 방법으로 시간복잡도를 낮춰서 풀었다.

 

정답

알파벳 크기만큼의 정수배열을 만들어서 사용한다.

ASCII코드표를 참고해서 Char문자의 크기를 비교해서 대소문자 구분을 해준다.

A는 10진법으로 65이고, a는 97

import java.util.Scanner;
    public class Main {
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int[] arr = new int[26];  //알파벳의 개수만큼 배열을 만든다. (arr[0] = A에 해당하게 된다)
        String str = scan.next();

        for(int i=0; i<str.length(); i++) {  //한글자씩 순회하면서 카운트한다.(만약 A가 3번 카운트되면 arr[0] = 3)
            if(str.charAt(i) >= 'A' && str.charAt(i) <= 'Z') {
                arr[str.charAt(i)-'A']++;
            } else if(str.charAt(i) >= 'a' && str.charAt(i) <= 'z') {
                arr[str.charAt(i)-'a']++;
            }
        }
        
        int max = 0;
        char maxChar='A';
        for(int i=0; i<arr.length; i++) {
            if(max < arr[i]) {
                max = arr[i];
                maxChar = (char)(i+65);
            } else if (max == arr[i]) {
                maxChar='?';
            }
        }
        
        System.out.println(maxChar);

    }
}

charAt을 사용한 비교 부분에서 연사자와 'A' 를 사용해도 되고 숫자를 사용해도 됨

        for(int i=0; i<str.length(); i++) {
            if(str.charAt(i) >= 65 && str.charAt(i) <= 90) {
                arr[str.charAt(i)-65]++;
            } else if(str.charAt(i) >= 97 && str.charAt(i) <= 122) {
                arr[str.charAt(i)-97]++;
            }
        }