문자열을 char 로 다루는 여러가지 방법들 String, char, int

태그
String
Array
char
공개여부
작성일자
2021/01/07
문제를 푸는것 보다 문자열 → char[] → int 로 변경하는 코드를 보고 싶으신 분들은 여기를 눌러 바로 이동하세요
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[] 로 받아들여서 위와 같이 구했는데
Screen_Shot_2021-01-07_at_23.51.42.png
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% 음.. 뭐... 그래 좋긴한데 더 빠른 방법이 없나??
Screen_Shot_2021-01-07_at_23.45.16.png
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
아 좀 별론데? 이건 ㄹㅇ 최악인것 같다
charString 으로 바꾸고 이걸 Integer 로 바꾸는데 type 을 변경하는 연산만 2번 하니 뭐 그렇다 치자
Screen_Shot_2021-01-07_at_23.49.31.png
return n.chars().max().getAsInt() - '0';
Java
runtime 11ms 26.77%
Screen_Shot_2021-01-07_at_23.47.35.png
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% 안에 들어가는 코드는 어떤 코드일까?
Screen_Shot_2021-01-07_at_23.54.41.png
확인하고 싶은 그래프를 클릭하면 그 곳에 코드가 나오는데
분석을 해보면
1.
Math.max() 를 사용하지 않는다. 그럼 나도 max를 사용하지 않도록 바꿔봐야겠다
2.
charAt(i) - '0' 빼기 연산도 딱 한번만 수행한다
Math.max 만 사용하지 않아본다.
Screen_Shot_2021-01-07_at_23.57.59.png
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' 연산도 딱 한번만 수행해보자
Screen_Shot_2021-01-08_at_0.01.39.png
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를 반환하게 해보자
Screen_Shot_2021-01-08_at_0.02.58.png
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
오히려 안하니만 못하다
Screen_Shot_2021-01-08_at_0.04.12.png
뭔가 기가막힌 성능은 없는걸까?
결국 이 포스팅을 하면서 학습한 것은 Stringchar[] 로 다룰때 어떻게 하면 다루기 쉬운지 정도밖에 없다.
그래도 남는게 있어야 하니 Stringchar[] 로 변경하고, 그 값을 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
__ascii.png
- '0' 을 실행하는 이유는 변수 num 의 범위는 이러한 조건을 만족한다
48num<5848 ≤ num <58
ascii 코드표를 참조하면 확인할 수 있다.
숫자 0의 ascii 10진수 값은 48 이다.
n.charAt(i) - 48;
Java
도 동일한 결과를 반환한다
알고리즘을 풀다보면 Stringchar[] 로 접근할 때 쉽게 풀리는 경우가 많아 정리했다.
Made with 💕 and Oopy