백준 1157번 해답(정답 참고함)

1157번: 단어 공부 (acmicpc.net)

1157번: 단어 공부

1. 시간 초과한 내 답

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        
        // 입력 값 받기
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();

        int maxCount = 0;
        char maxChar = '?';
        for (int i = 0; i < s.length(); i++) {
            int count = 0;
            char c = Character.toUpperCase(s.charAt(i));

            for (int j = 0; j < s.length(); j++) {
                if(c == Character.toUpperCase(s.charAt(j))){
                    count++;
                }
            }

            if(maxCount< count){
                maxCount = count;
                maxChar = c;
            } else if (maxCount == count) {
                if(c != maxChar){
                    maxChar='?';
                    break;
                }
            }
        }
        System.out.println(maxChar);

    }
}

테스트 케이스에 대한 정답은 잘 나왔는데, 자꾸 시간 초과가 떴다. 나는 그 이유가, 내가 Scanner를 써서나 아니면 컬랙션 프레임 워크를 써서 인 줄 알고, 그것들을 바꿨다. 

그래도 안되자 그 이후에는 코드 수가 너무 길어서 그런 줄 알고, 배열을 쓰지 않고 풀 수 있도록 코드 수도 줄였다. 

그래도 안되어서 구글링 해서 답을 봤다.

 

답을 따라치진 않았다. 답의 구동 원리를 이해하니 왜 내 풀이가 시간초과에 계속 걸렸는지 바로 알 수 있었기 때문이다. 개념만 가져와서 다시 적어 보았다. 

2. 문제 진짜 해답 (정답 봄)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        // 알파벳 A~Z까지 각 알파벳이 몇 개 나왔나 카운트 하기 위함.
        int [] arr = new int[26];


        // 입력 값 받기
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String s = reader.readLine();

        // index가 알파벳의 순서, 원소 값이 해당 알파벳이 나온 횟수
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)>=65 && s.charAt(i)<=90){
                arr[s.charAt(i)-65]++;
            }else{
                arr[s.charAt(i)-97]++;
            }
        }

        // 뭐가 제일 큰 지 확인
        int max = 0;
        char maxChar = '?';
        for (int i = 0; i < 26; i++) {
            if(arr[i] > max){
                max = arr[i];
                maxChar = (char) (i+65);
            } else if (arr[i] == max) {
                maxChar='?';
            }
        }
        System.out.println(maxChar);
    }
}

3. 내가 못 풀었던 이유 & 배운 점

내 해답이 자꾸 시간 초과가 나고 끝내 못 풀었던 이유는 다음과 같다. 

내 풀이는 원소 하나하나를 배열 전체를 순회 시킨다. 원소 한 개에 대한 검사로 배열 전체를 무조건 다 돌아야 하니 BigO로 봤을 때, 배열 길이가 10000이고 한 번 돌 때 10000초가 든다고 했을 때, 

10000 * 10000초  이 되어버린다. 정말 비효율적인 풀이였다. 

 

이와 달리, 해답을 보면, 먼저 26칸 짜리 빈 배열을 만드는데 여기 index가 A-Z까지의 알파벳을 순서대로 의미하고, 값은 해당 알파벳이 나온 순서이다. 

아스키 코드를 보면 대문자는 65~90, 소문자는 97~122까지이다. 

이를 이용해 대문자를 만나면 -65해서 나온 값과 같은 인덱스의 값을 1 올려주고, 소문자는 문자 -97한 값과 같은 인덱스의 값을 +1 올려주었다. 

이러면 한 번의 순회로 모든 문자의 나온 횟수를 체크할 수 있다. 

내 풀이식과 비교했을 때 월등한 차이이다. 

 

나는 시간을 줄이려면, 고등 개념을 덜 쓰면 된다고만 생각했다. 

근데 그게 아니라 내 코드가 돌아가는 원리에 대해서 생각해야 한다는 것을 깨달았다. 

계속 답이 나오는 로직인데 시간 초과가 나온다고 억울해만 했는데, 이럴 때는 다른 문제를 풀거나 잠시 내려놓고 생각하는 시간을 가져야겠다. 

 

다음부터는 답을 되도록이면 찾지 말고, 묵혀두자!