패스트캠퍼스 Java 코딩테스트 강의 2주차

자자~ 오늘도 학습 인증샷부터 시작하는 내 Java 코딩테스트 준비 글이다.

오늘 풀이해볼 문제는 BOJ의 1157번: 단어 공부이다.

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

1157번: 단어 공부

Python으로 PS를 시작했을 때 이 문제를 푼 기억이 난다.

간단하게 이 문제의 요구사항에 대해 정리해보면,

 

1. 영어 대/소문자로 이루어진 문자열을 하나 줄게.

2. 여기서 제일 많이 쓰인 알파벳(대/소문자 구분)을 찾아서 대문자로 출력해봐.

3. 단, 제일 많이 쓰인 알파벳이 여러개면 "?"를 출력하면 돼!

 

이렇게 3개로 요약할 수 있다. 단순한 구현 문제이자, 특정 자료구조를 사용할 수 있는지 물어보는 문제이기도 하다.

Python으로 풀 때에는 내부 요소가 "키 : 값" 형태로 저장되는 "딕셔너리"라는 자료구조(엄밀히 말하면 Hash)를 사용해서 풀었다.

 

Java로는 어떻게 풀 수 있을까?

일단 강의에서 풀이를 위해 초기에 제시한 코드는 다음과 같다.

import java.util.Scanner;

public class Main {
    public static int[] getAlphabetCount(String str) {
        int[] count = new int[26];
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if('A' <= ch && ch <= 'Z')
                count[ch - 'A']++;
            else count[ch - 'a']++;
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();

        int[] count = getAlphabetCount(str);

        int maxCount = -1;
        char maxAlphabet = '?';
        for (int i = 0; i < 26; i++) {
            if (count[i] > maxCount) {
                maxCount = count[i];
                maxAlphabet = (char)('A' + i);
            }
            else if (count[i] == maxCount) {
                maxAlphabet = '?';
            }
        }
        System.out.println(maxAlphabet);
    }
}

풀이 로직은 간단하다. 문자열을 받은 뒤 문자열을 이루는 알파벳의 개수를 계산해서 int형 배열에 저장하고 그걸 반환하는 getAlphabetCount() 메소드로 문자열을 넘겨서 결과 배열을 저장한 뒤, 등장 횟수가 가장 많은 자리의 인덱스를 계산하고, 해당 인덱스에 해당하는 알파벳을 출력하는 방식이다. 이 때 현재 최대 등장 횟수값과 같은 값이 나오면, 알파벳은 ?로 만들어서 출력하게 된다.

 

위 코드로 정답 판정을 받을 수 있는데, 여기서 그치지 않고 부분 코드 변형을 통해 전체 코드의 효율성을 증가시켜보자.

 

우선 문자열을 받을 때, 어차피 출력되는 알파벳은 모두 대문자이므로, 입력되는 문자열의 알파벳을 모두 대문자로 통일시켜줘도 괜찮다.

String str = sc.next().toUpperCase();

그러면 getAlphabetCount()는 대소문자를 구분하는 로직이 빠지니까 이렇게 간단하게 변한다.

    public static int[] getAlphabetCount(String str) {
        int[] count = new int[26];
        for (int i = 0; i < str.length(); i++) {
            count[str.charAt(i) - 'A']++;
        }
        return count;
    }

이렇게 변형한 코드를 제출해도 마찬가지로 예제도 통과하고,

 

Mississipi

zZa

최종 정답 판정을 받을 수 있는데, 이상하게 결과를 확인해보면

코드 길이만 짧아졌을 뿐, 시간도 늘고 메모리 사용량도 늘어난 것을 확인할 수 있다.

코드 길이가 짧아진다고 시간 복잡도나 공간 복잡도에서 무조건 이득을 보는 것은 아닌 것 같다.

 

강의 상세 페이지 : https://fastcampus.co.kr/dev_online_codingtest 

핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 with Java 초격차 패키지 Online. | 패스트캠퍼

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.