📃 문제 설명

Partitioning Into Minimum Number Of Deci-Binary Numbers

[문제 출처 : LeetCode]

👨‍💻 해결 방법

0과 1로만 이루어지고, 1로 시작하는 수를 deci-binary라고 한다.

주어진 n을 deci-binary의 합으로 만들 때 필요한 최소 deci-binary의 개수를 구하면 된다.

처음에 문제가 이해가 안됐다.

결국 0과 1로만 이루어져 있는 수의 합으로 n을 만들어야 되기 때문에 n에 포함되어있는 수 중 최대값을 구하면 된다.(9를 만들려면 1을 9번 더하는게 최소)

그래서 나는 그냥 바로 max(n)으로 최대값을 구해서 풀었는데,
다른 풀이를 보면서 이마를 탁! 쳤다.

for i in range(9, -1, -1):
	if str(i) in n:
		return i

위와 같은 방법으로 n에서 최대값을 찾을 수도 있었고,

return max(set(n))

이렇게 set을 이용해서 시간복잡도를 줄일 수 있었다.

왜 이런 생각을 못했을까
사실 못한게 아니라 안한거다..

문제를 풀 때 항상 더 나은 방법이 있는지 고민하는 습관을 들여야겠다.
엑!

👨‍💻 소스 코드

class Solution:
    def minPartitions(self, n: str) -> int:
        for i in range(9, -1, -1):
            if str(i) in n:
                return i