Leetcode 의 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers 문제를 풀면서 이건 좀 기록해둘 필요가 있다 생각했다.
문제
A decimal number is called deci-binary if each of its digits is either 0 or 1 without any leading zeros. For example, 101 and 1100 are deci-binary, while 112 and 3001 are not.
Given a string n that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up to n.
examples
발견된 규칙성
123454321 과 같이 숫자 문자열이 발견되면 여기서 가장 큰 숫자 만큼 deci-binary 가 발생된다.
•
n="8" → 1 이 8개 필요하다.
•
n="38" → (33): 11, 11, 11 + (1): 1 + 1 + 1 + 1+ 1 → 11은 3개 + 1은 5개 → 8
•
n="438" → 111, 111, 111, 101, 1, 1, 1, 1 → 8개
결국 문자열 n 에서 가장 큰 숫자를 찾아 반환하면 되는데 이 숫자를 찾는데 흥미로운 일이 생겼다.
int max = 0;
for (int i = 0; i < n.length(); i++) {
int num = Character.getNumericValue(n.charAt(i));
max = Math.max(max, num);
}
Java
복사
n 을 char[] 로 받아들여서 위와 같이 구했는데
int max = 0;
for (int i = 0; i < n.length(); i++) {
int num = Character.getNumericValue(
n.charAt(i));
max = Math.max(max, num);
}
return max;
Java
복사
runtime 21ms, 13.93% 음.. 뭐... 그래 좋긴한데 더 빠른 방법이 없나??
int max = 0;
for (int i = 0; i < n.length(); i++) {
int num = Integer.parseInt(
String.valueOf(n.charAt(i))
);
max = Math.max(max, num);
}
return max;
Java
복사
아 좀 별론데? 이건 ㄹㅇ 최악인것 같다
char 를 String 으로 바꾸고 이걸 Integer 로 바꾸는데 type 을 변경하는 연산만 2번 하니 뭐 그렇다 치자
return n.chars().max().getAsInt() - '0';
Java
복사
runtime 11ms 26.77%
int max = 0;
for (int i = 0; i < n.length(); i++) {
int num = n.charAt(i) - '0';
max = Math.max(max, num);
}
return max;
Java
복사
runtime 은 9ms 인데 그래도 38.24% 이다
내 머리속에서 나온 것 중에 그나마 빠른 방법이 이거다... 0%, 1% 안에 들어가는 코드는 어떤 코드일까?
확인하고 싶은 그래프를 클릭하면 그 곳에 코드가 나오는데
분석을 해보면
1.
Math.max() 를 사용하지 않는다. 그럼 나도 max를 사용하지 않도록 바꿔봐야겠다
2.
charAt(i) - '0' 빼기 연산도 딱 한번만 수행한다
Math.max 만 사용하지 않아본다.
int max = 0;
for (int i = 0; i < n.length(); ++ i) {
int num = n.charAt(i) - '0';
if (max < num) {
max = num;
}
}
Java
복사
runtime 5ms 이고 77.82% 이다.
charAt(i) - '0' 연산도 딱 한번만 수행해보자
char max = 0;
for (int i = 0; i < n.length(); ++ i) {
char num = n.charAt(i);
if (max < num) {
max = num;
}
}
return max - '0';
}
Java
복사
위에 결과와 같다
9가 있다면 더 for 를 수행하지 않고 9를 반환하게 해보자
char max = 0;
for (int i = 0; i < n.length(); ++ i) {
char num = n.charAt(i);
if (num == '9') {
return 9;
}
if (max < num) {
max = num;
}
}
return max - '0';
Java
복사
오히려 안하니만 못하다
뭔가 기가막힌 성능은 없는걸까?
결국 이 포스팅을 하면서 학습한 것은 String 을 char[] 로 다룰때 어떻게 하면 다루기 쉬운지 정도밖에 없다.
그래도 남는게 있어야 하니 String 을 char[] 로 변경하고, 그 값을 int 로 변경하는 방법을 정리하고 가자
문자열 → char[] → int 로 변경하는 방법
Character 를 사용한다
char c = n.charAt(i);
int num = Character.getNumericValue(c);
Java
복사
boxed char 를 사용해 숫자 값으로 변경한다 위의 코드 결과로 보면 runtime 21ms, 13.93% 으로 시도해본 방법중 2번째로 느린 방법이었다.
String 으로 변경하고 다시 parseInt 한다
String s = String.valueOf(n.charAt(i));
int num = Integer.parseInt(s);
Java
복사
가장 느린 방법이었다. 급하게 풀어야 하는데 다른 방법 생각안나면 가장 직관적으로 떠오르는 방법이다
그래서 알고리즘은 훈련이 필요한것 같다
chars() 이용하기
int num = n.chars().max().getAsInt() - '0';
Java
복사
char() 가 생소할 수 있는데 확인해보면 String 에 다음과 같이 구현되어 있다.
/**
* Returns a stream of {@code int} zero-extending the {@code char} values
* from this sequence. Any char which maps to a <a
* href="{@docRoot}/java.base/java/lang/Character.html#unicode">surrogate code
* point</a> is passed through uninterpreted.
*
* @return an IntStream of char values from this sequence
* @since 9
*/
@Override
public IntStream chars() {
return StreamSupport.intStream(
isLatin1() ? new StringLatin1.CharsSpliterator(value, Spliterator.IMMUTABLE)
: new StringUTF16.CharsSpliterator(value, Spliterator.IMMUTABLE),
false);
}
Java
복사
Spliterator 는 재밋는 것이니 다음에 다뤄야지
char - '0' 아스키 코드 규칙을 이용하기
int num = n.charAt(i) - '0';
Java
복사
- '0' 을 실행하는 이유는 변수 num 의 범위는 이러한 조건을 만족한다
ascii 코드표를 참조하면 확인할 수 있다.
•
숫자 0의 ascii 10진수 값은 48 이다.
n.charAt(i) - 48;
Java
복사
도 동일한 결과를 반환한다
알고리즘을 풀다보면 String 을 char[] 로 접근할 때 쉽게 풀리는 경우가 많아 정리했다.
