leetcode 1399. Count Largest Group 리트코드 1399번 가장 큰 그룹의 숫자 세기 문제 풀이

<파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 파이썬으로 풀이한 포스팅이다.

 

문제는 모두 리트코드에 출제된 문제들이며, 직접 풀었지만, 책에서 주는 힌트와 풀이 과정들을 참고한 경우가 많다.

이곳은  정리한 책에 나온 문제에 대한 목록과 해설을 정리한 공식 깃허브 페이지 이며, 

다음 포스팅은 내가 푼 <파이썬 알고리즘 인터뷰> 문제 풀이 목록을 정리해 놓았다.

 

문제

https://leetcode.com/problems/count-largest-group/

Count Largest Group - LeetCode

입력: 양의 정수 n

출력: 양의 정수 n

 

문제 요약:  n이 주어지면, 1부터 n까지의 모든 수를 각 자릿수를 더한다. 예를 들어 11이면, 1, 2,3,4,5,6,7,8,9,1+0, 1+1 인 11개의 새로운 리스트가 만들어지는 것이다. 그러면, 1, 2는 중복이 되어, ([1, 1+0], [2, 1+1]) 1,2는 갯수가 2로 가장 큰 사이즈가 되고, 2인 것이 2개 있으니까 count largest group 은 2가 되는 것이다.

 

유의 사항:

13 이 1+3 이 되는 것을 생각해서 

n//10 + n%10 이런 식으로 생각했지만, 주어지는 숫자의 조건이 1 <= n <= 10^4 이다.

즉 113은  1+1+3이 되어야 하고, 1113은 1+1+1+3이 되어야 하는데 어떻게 해결할 것인가?

생각 과정

문제에 대해서 파악하는데 한참 걸렸다.

일단 n이 정해지면, 1부터 n까지 모든 수의 각 자릿수 숫자를 더해야 하기 때문에 for 문이 들어갈 수 밖에 없다.

그리고 각 자릿수 합의 빈도수를 구해야 하는데, 빈도수 관련 문제는 딕셔너리로 몇 번 풀어본 기억이 난다. (key : 값 value: 빈도수)

이렇게 해서 dictionary에서 가장 value값이 큰 item의 key를 구하면 그것이 답이 될 것이다. 

풀이

내가 제출한 답안은 아래와 같았다.

class Solution:
    def countLargestGroup(self, n: int) -> int:
        #어떤 숫자가 주어졌을 때 각 자릿수의 값을 서로 더해주는 함수
        def get_sum(value):
            res = 0
            while value:
                res += (value % 10)
                value //= 10
            return res
        d = {}
        #1부터 n 사이에 get_sum()함수 값을 구해서 (값: 빈도수)로 구성된 딕셔너리에 집어넣기 
        for i in range(1,n+1):
            d[get_sum(i)] = d.get(get_sum(i), 0) + 1
            #딕셔너리에서 빈도수 value가 가장 큰 key들의 갯수를 구하기
        return len([k for k,v in d.items() if v==max(d.values())])

정답으로 인정되긴 했지만, 하위 30%의 속도.

 

discussion에 올린 정답들 중에 파이써닉하게 잘 해결한 코드가 있었다.

https://leetcode.com/problems/count-largest-group/discuss/829977/Python-3-two-solutions-beautiful-and-fast-%3A)

def countLargestGroup(self, n: int) -> int:
    d = {}
    for i in range(1, n + 1):
        t = sum(map(int, list(str(i))))
        d[t] = d.get(t, 0) + 1
    return sum(1 for i in d.values() if i >= max(d.values()))

여기서 큰 아이디어는 2개인데, 

 

1. 자릿수마다 나눠서 더하는 걸 골치 아프게 while문을 쓰지 않고 str()함수를 써서, 숫자열 문자열로 바꿨다는 것이다. 문자열로 바꾼 것을 list() 로 씌우면, 각 글자마다 따로 리스트의 아이템으로 저장되고, 이 각 글자를 다시 int()로 숫자로 바꾼 다음, sum()으로 더해버린 것.

어떤 자릿수이던지 오류없이 한 번에 해결이 가능하다.

2.  마지막에 답을 구할 때 for문과 list를 활용한 것은 속도 효율성을 떨어뜨린다.

나와 거의 비슷한데, sum()을 사용했다. for문은 여전히 사용했는데, for문을 쓰지 않으면 더 효율성이 높아질 것이다.

 

훨씬 더 효율적으로 해결한 코드도 있었다.

https://leetcode.com/problems/count-largest-group/discuss/1221694/using-dynamic-programming-or-98-or-python

 

class Solution:
    def countLargestGroup(self, n: int) -> int:        
        dp={0:0}      
        counts=[0]*(100)       
        for i in range(1,n+1):           
            a=i%10           
            b=i//10
            
            dp[i]  = a+dp[b]
            
            counts[dp[i]]+=1           
        return counts.count(max(counts))

 

여기서 핵심은  두 가지

1.

dp[i]  = a+dp[b]

사실 174의 경우도 1+7+4 이지만, 17의 자릿수간 합 1+7에 4를 더해주어도 값이 같다.

그래서 자릿수가 3, 4개가 되어도 dp[i]  = a+dp[b] 만 해주면, 다 해결이 된다.

 

2. 미리 counts=[0]*(100) 로 빈 리스트를 만들어 놓고, 빈도수를 계산해서, 리스트 메서드인 .count로 쉽게 해결했다는 점이다. 

덕분에 위의 다른 코드들처럼 for문을 2번 돌지 않고 한 번으로 해결했다.