728x90
반응형
문제 요약
- 알고리즘 분류: 그리디, 수학
- 난이도: Medium
- 문제내용:
- 각 자리수는 0과 1만 올수 있다.
- 숫자 N을 주어 줬을때 0, 1만 오는10진수 조합된 숫자로 최소 몇번 더하면 되는지 구하여라.
- 사이트 주소: https://leetcode.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers/description/
문제풀이
이번 문제에는 그리디 문제이다. 그리디 관련 자세한 내용은 아래 글에서 참고 하면된다.
https://jih3508.tistory.com/70
[알고리즘 이론] 그리디(Greedy)
이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택할때 가장 좋은것을 선택하는 알고리즘이다. 이 알고리즘은 이론상 설명 단순하고 다른 알고리즘에서 기초적으로
jih3508.tistory.com
문제 접근방법
이번 문제는 간단하게 풀수 있는 문제 이다. 그이유는 각 자리수중 큰 값만 구하면 된다. 0과 1만 되어 있는 숫자중 최대 값이 나올라면 큰 값만큼 1씩 더하면 된다. 나머지 자리는 0과 1 중 어떤한 조합이 와도 가장 높은 수만큼 1의 개수만 채우면 된다. 그러면 N의 정수 자리수만큼 탐색 하기 때문에 시간 복잡도는 O(N)만큼 나온다.
Code
Python
class Solution:
def minPartitions(self, n: str) -> int:
for num in range(9, 0, -1):
if str(num) in n:
return num
Java
class Solution {
public int minPartitions(String n) {
char[] numbers = n.toCharArray();
char maxNum = '0';
for (char number : numbers) {
if(number > maxNum){
maxNum = number;
}
}
return (int) (maxNum - '0');
}
}
728x90
반응형
'알고리즘 > Leetcode' 카테고리의 다른 글
[Leetcode] 91. Decode Ways (1) | 2024.04.05 |
---|---|
[Leetcode] 207. Course Schedule (0) | 2024.03.22 |
[Leetcode] 1631. Path With Minimum Effort (0) | 2024.03.15 |
[Leetcode] 131. Palindrome Partitioning (0) | 2024.03.13 |
[Leetcode] 343. Integer Break (0) | 2024.03.09 |