[프로그래머스 코딩테스트] 문자열 묶기(Java)

  문제 설명

  문자열 배열 strArr이 주어집니다. strArr의 원소들을 길이가 같은 문자열들끼리 그룹으로 묶었을 때 가장 개수가 많은 그룹의 크기를 return 하는 solution 함수를 완성해 주세요.

 

  제한사항

• 1 <= strArr의 길이 <= 100,000
• 1 <= strArr의 원소의 길이 <= 30
• strArr의 원소들은 알파벳 소문자로 이루어진 문자열입니다.

 

  입출력 예

strArr	result
["a", "bc", "d", "efg", "hi"]	2

class Solution {
    public int solution(String[] strArr) {
        int max = 0;
        for (int i = 0; i < strArr.length; i++) {
            max = Math.max(strArr[i].length(), max);
        }
        int[] num = new int[max + 1];
        for (int i = 0; i < strArr.length; i++) {
            num[strArr[i].length()]++;
        }
        int nMax = 0;
        for (int i = 0; i < num.length; i++) {
            if (nMax < num[i]) {
                nMax = num[i];
            }
        }
        int answer = nMax;
        return answer;
    }
}

  이 문제는 최빈값을 구하는 문제와 유사합니다. 배열에서 주어지던 정수가 배열의 길이로 바뀐다는 점 정도의 차이만 있습니다.

  최빈값을 구하는 문제에서 그러했듯, 빈 배열을 만들어야 합니다. 배열의 크기를 구하기 위해 max 변수를 생성했습니다. for문이 strArr의 길이만큼 순회합니다. Math 클래스의 max 메소드를 이용하여 최대값을 구합니다. strArr의 i번째 원소의 길이와 max를 비교합니다. 이 과정에서 strArr 배열에서 가장 긴 문자열의 길이를 구합니다.

  num 배열을 생성합니다. 크기는 앞서 구한 max + 1로 지정합니다. + 1을 하는 이유는 인덱스가 0번에서 시작하기 때문입니다. 배열의 각 길이에 대응하여 인덱스에 저장할 것입니다. 예를 들어 길이가 1인 문자열은 1번 인덱스가, 길이가 3인 문자열은 3번 인덱스가 증가해야 합니다. 0번 인덱스는 없는 셈 치는 것입니다. 따라서 + 1을 하지 않는다면 num 배열의 길이는 필요한 길이보다 짧아지므로 오류가 발생할 수 있습니다.

  for문이 strArr의 길이만큼 순회합니다. num의 strArr의 i번째 길이의 인덱스가 증가합니다. 입출력 예를 예로 들어보겠습니다.

 

strArr = ["a", "bc", "d", "efg", "hi"] strArr[0] = 1 strArr[1] = 2 strArr[2] = 1 strArr[3] = 3 strArr[4] = 2 num = [0, 2, 2, 1]

 

  nMax 변수를 생성하고  0으로 초기화 합니다. 이는 앞서 증가한 num 배열 원소의 최댓값을 담을 변수입니다. for문이 num의 길이만큼 순회합니다. 만약 nMax의 값보다 num의 i번째 원소가 크다면 nMax의 값을 num의 i번째 원소로 갱신합니다.

  answer에 nMax를 할당합니다. nMax를 사용하지 않고 answer에 바로 할당해도 되지만, 명시적인 변수를 이용하고 싶어서 생성했습니다.

  그러나 이 방법에는 치명적인 단점이 존재합니다. 이 문제에서 제한사항을 보면 strArr의 길이는 1에서 30까지로 적은 범위입니다. 그러나 극단적인 예로 원소의 길이가 만약 1과 100,000으로 나뉜다면 어떨까요. 두 값을 구하기 위해 이 코드는 100,001만큼 크기의 배열을 생성하여 메모리가 낭비될 것입니다. 이러한 단점을 보완하기 위하여 HashMap을 쓸 수 있습니다. 예시는 아래 코드와 같습니다.

 

import java.util.HashMap;
class Solution {
    public int solution(String[] strArr) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (String str : strArr) {
            int len = str.length();
            if (map.containsKey(len)) {
                map.put(len, map.get(len) + 1);
            } else {
                map.put(len, 1);
            }
        }
        int max = 0;
        for (int len : map.keySet()) {
            int count = map.get(len);
            if (max < count) {
                max = count;
            }
        }
        int answer = max;
        return answer;
    }
}

  HashMap을 생성합니다. 제네릭 타입은 둘 다 Integer 입니다. for-each문에서 문자열 str은 strArr의 원소를 하나씩 받습니다. len 변수를 생성하여 str의 길이를 할당합니다. 만약 map에 len이 키에 해당하는 값이 있다면 get 메소드로 가져와 1을 더한 후 put으로 저장합니다. 없다면 1로 초기화하여 put으로 값을 저장합니다.

  max 변수를 생성합니다. 가장 많이 등장하는 배열 길이의 횟수를 담을 변수입니다. for-each문에서 변수 len은 map의 key값을 하나씩 받습니다. count 변수를 생성하여 map의 len을 get, 즉 key에 해당하는 value를 가져옵니다. 만약 max보다 count의 값이 크다면 max의 값을 count로 갱신합니다. 이렇게 구한 max를 answer에 할당합니다.