Your Name

I am an amazing person.

1 분 소요

문제 설명

프로그래머스 181855번 문자열 묶기

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

제한 사항

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

입출력 예시

strArr result
[“a”,”bc”,”d”,”efg”,”hi”] 2

입출력 예 설명 1

  • 각 문자열들을 길이에 맞게 그룹으로 묶으면 다음과 같습니다.
문자열 길이 문자열 목록 개수
1 [“a”,”d”] 2
2 [“bc”,”hi”] 2
3 [“efg”] 1

코드 구현

Python

def solution(strArr):
    numbers = [0] * 30

    for num in strArr:
        numbers[len(num) - 1] += 1

    return max(numbers)

시간 복잡도 - Python

  • strArr 배열을 순회하므로 시간 복잡도는 $O(n)$이다.
  • 문자열 길이 세기, 최댓값 찾기는 시간 복잡도가 각각 $O(1)$, $O(30)$이므로 $O(1)$이다.

개선할 점 - Python

  • Counter 함수를 사용하면 자동으로 길이별로 갯수를 세어준다.
def solution(strArr):
    from collections import Counter

    # 문자열 길이 카운트
    length_counts = Counter(len(s) for s in strArr)
    
    # 가장 큰 그룹의 크기 반환
    return max(length_counts.values())

Java

class Solution {
    public int solution(String[] strArr) {
        int[] numbers = new int[30];
        int answer = 0;

        for (String s : strArr) {
            numbers[s.length() - 1] += 1;
        }

        for (int num : numbers) {
            if (num > answer) {
                answer = num;
            }
        }

        return answer;
    }
}

시간 복잡도 - Java

  • strArr 배열을 순회하므로 시간 복잡도는 $O(n)$이다.
  • 문자열 길이 세기, 최댓값 찾기는 시간 복잡도가 각각 $O(1)$, $O(30)$이므로 $O(1)$이다.

개선할 점 - Java

  • HashMap을 사용하면 문자열 길이별로 갯수를 셀 수 있다.
  • 최댓값을 구하는 반복문을 없앨 수 있다.
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int solution(String[] strArr) {
        Map<Integer, Integer> lengthCounts = new HashMap<>();
        int maxCount = 0;

        for (String s : strArr) {
            int length = s.length();
            lengthCounts.put(length, lengthCounts.getOrDefault(length, 0) + 1);
            maxCount = Math.max(maxCount, lengthCounts.get(length));
        }

        return maxCount;
    }
}

참고