[백준/BOJ][Java][1157] 단어공부

2023.08.21 - [Java] - Java String 이해

Java String 이해

 

---

 

 

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

1157번: 단어 공부

문제 : 문자열에서 가장 많은 등장한 알파벳 (대소문자를 구분하지 않음)

1. 각 알파벳의 개수를 구한다
2. 그 중 최댓값을 구한다

 

내가 푼 틀린 풀이

• 알파벳 개수를 계산하는건 애너그램에서 사용하던 방식으로 했고, 최대값구하는거 까지 완료했는데
• 물음표를 처리하는 과정에서 오래 걸렸다.
• 내림차순으로 정렬해서 맨 앞쪽에 있는 인덱스 값이 같으면 중복되었다고 생각해서 ‘?’로 처리했는데 틀렸다고 나와서 실패함
• 근데 또 예제 출력은 다 맞음..ㅜㅜ

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();

        int[] count = new int[26];
        // 알파벳 배열에서 해당 인덱스에 맞는 알파벳 개수 계산
        for (char c : a.toUpperCase().toCharArray()) {
            count[c - 'A']++;
        }
        int idx = 0;
        // 알파벳 배열에서 최대값 구하기
        int max = count[0];
        for (int i = 0; i < count.length; i++) {
            if (count[i] > max) {
                max = count[i];
                idx = i;
            }
        }
        char ans;
        // 알파벳 배열 내림차순 후, 앞쪽 인덱스 값이 서로 같으면 ? 반환
        Integer[] integers = Arrays.stream(count).boxed().toArray(Integer[]::new);
        Arrays.sort(integers, Collections.reverseOrder());
        if (integers[0] == integers[1])
            ans = '?';
        // 아닐 경우 알파벳 반환
        else {
            System.out.println("max = " + max);
            ans = (char) ('A' + idx);
        }

        System.out.println("answer = " + ans);
    }
}

내림차순 정렬을 하면 안되는 이유(GPT)

알파벳 배열을 내림차순으로 정렬하고 중복된 최대값을 확인하는 부분은 필요하지 않습니다.

이 부분은 코드의 논리를 복잡하게 만들 뿐만 아니라,

알파벳 배열을 이미 탐색한 후에 불필요한 추가 탐색을 수행하게 되므로 성능을 저하시킬 수 있습니다.

여러 개의 최대값이 있는지 여부를 확인하기 위해 알파벳 배열을 내림차순으로 정렬하는 대신,

이미 탐색한 배열에서 최대값의 개수를 카운트하여 중복 여부를 확인하는 방식으로 충분히 처리할 수 있습니다.

이렇게 하면 코드가 더 간결하고 성능도 좋아집니다.

다시 푼 풀이

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();

        int[] count = new int[26];
        // 알파벳 배열에서 해당 인덱스에 맞는 알파벳 개수 계산
        for (char c : a.toUpperCase().toCharArray()) {
            count[c - 'A']++;
        }

        // 알파벳 배열에서 최대값 구하기
        int max = count[0];
        for (int i = 0; i < count.length; i++) {
            if (count[i] > max) {
                max = count[i];
            }
        }
        char ans;
        int idx = 0;
        // count배열의 인덱스 값과 최댓값으로 구한 값이 같을 경우 중복개수 더하기
        int duplicateCount = 0;
        for (int i = 0; i < count.length; i++) {
            if (count[i] == max) {
                duplicateCount ++ ;
                idx =i;
            }
        }
        if (duplicateCount > 1)
            ans = '?';
        else
            ans = (char)('A' + idx);

        System.out.println(ans);
    }
}

메모리	시간	언어	코드 길이
30808KB	496ms	Java 11	1157B

 

강의 풀이 1 (for문 3개 사용하는 법)

 

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 a = sc.next();

        int[] count = getAlphabetCount(a);

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

메모리	시간	언어	코드 길이
28700KB	440ms	Java 11	1099B

 

내가 푼 풀이와 강의 풀이 1의 비교(GPT)

 

toUpperCase() 메서드를 사용할 때마다 새로운 문자열 인스턴스가 생성되며,

toCharArray() 메서드를 호출하면 또 다른 문자 배열이 생성됩니다. 이로 인해 메모리 사용량이 늘어납니다.

예를 들어, 문자열 "abc"가 주어졌을 때 toUpperCase().toCharArray()를 사용하면 다음과 같은 일련의 과정이 발생합니다:

1. "abc"를 대문자로 변환한 새로운 문자열 "ABC"가 생성됩니다.
2. "ABC" 문자열을 문자 배열로 변환한 새로운 배열 ['A', 'B', 'C']가 생성됩니다.

이러한 과정 때문에 메모리 사용량이 늘어나며, 이런 임시 객체들은 Java의 가비지 컬렉션(Garbage Collection)에 의해 정리되긴 하지만, 임시 객체 생성을 피하면 더 효율적인 메모리 관리가 가능합니다.

 

첫 번째 구현에서는 toUpperCase()와 toCharArray()를 반복적으로 호출하고 있습니다. 두 번째 구현은 이런 불필요한 생성을 피하고 대신 문자열을 원본 상태로 사용하여 메모리를 더 효율적으로 관리합니다.

 

느낀점 :

toCharArray()를 사용해서 배열을 만들지 않아도 String의 charAt(i)을 사용하면 된다는 걸 잊지 말자.

String은 immutable이라 toUpperCase() 메서드를 호출하면 원래의 문자열을 변경하는 것이 아니라, 대문자로 변환된 새로운 문자열 인스턴스가 생성된다. 이렇게 새로운 문자열 인스턴스가 생성되면 이전의 문자열 인스턴스와 메모리를 공유하지 않는다.

강의 풀이 2 (for문 2개 사용하는 법)

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 a = sc.next();

        int[] count = getAlphabetCount(a);
        // 구성 성분 디버깅용
//        for (int i = 0; i < 26; i++) {
//            if (count[i] > 0)
//                System.out.println((char)('A' + i) + ": " + count[i]);
//        }

        int maxCount = -1;
        // 알파벳 인덱스로 찾는게 아니라 바로 알파벳으로 출력
        char maxAlphabet = '?';
        for (int i = 0; i < 26; i++) {
            if (count[i] > maxCount) {
                // 조건에 따라 maxCount 갱신
                maxCount = count[i];
                // 조건에 따라 maxAlphabet 갱신
                maxAlphabet = (char)('A' + i);
            } else if (count[i] == maxCount)
                // 조건에 따라 maxAlphabet 갱신
                maxAlphabet = '?';
        }

        System.out.println(maxAlphabet);
    }
}

메모리	시간	언어	코드 길이
27952KB	452ms	Java 11	1337B

 

강의풀이 3 (대소문자 구별 안하고 처리)

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++) {
            count[str.charAt(i) - 'A']++;
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 들어온 문자열을 전부 대문자로 바꿔서 s에 대입해줌
        String a = sc.next().toUpperCase();

        int[] count = getAlphabetCount(a);

        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);
    }
}

메모리	시간	언어	코드 길이
28888KB	452ms	Java 11	889B

 

강의풀이 4 (배열의 인덱스라는 개념을 사용하지 않고 처리)

• 이전 getAlphabetCount()의 경우, String을 한번만 돌아서 모든 알파벳 카운트를 한번에 다 구한다
• 현재 getAlphabetCount()의 경우, 카운트 배열을 쓸 생각을 못하고, 매번 문자열을 돌면서 알파벳의 개수를 셀 경우
• 구현을 어떤식으로 할 경우에 대해서 나중에 시간복잡도 개념을 배우고나서 어떤게 더 적합한 풀이인가를 알아야 함

import java.util.Scanner;

public class Main {

    public static int getAlphabetCount(String str, char alp) {
        int count = 0;
        for (int i = 0; i < str.length(); i++)
            if (str.charAt(i) == alp) count ++;
        return count;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next().toUpperCase();

        int maxCount = -1;
        char maxAlphabet = '?';
        for (char alp = 'A'; alp <= 'Z'; alp++) {
            int count = getAlphabetCount(str, alp);
            if (count > maxCount) {
                maxCount = count;
                maxAlphabet = alp;
            } else if (count == maxCount)
                maxAlphabet = '?';
        }
        System.out.println(maxAlphabet);
    }
}

메모리	시간	언어	코드 길이
29712KB	480ms	Java 11	796B