https://school.programmers.co.kr/learn/courses/30/lessons/81301
제출코드
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
int singleNumber;
StringBuilder sb = new StringBuilder();
// 1. 정수인 경우
if (Character.isDigit(c)) {
singleNumber = Character.getNumericValue(c);
// 정수 처리 로직
sb.append(singleNumber); // 예시: StringBuilder 객체에 추가
}
// 2. 알파벳인 경우
else if (Character.isLetter(c)) {
// 알파벳 처리 로직
sb.append(c); // 예시: StringBuilder 객체에 추가
}
}
문제 해결을 위한 접근 방식은 다음과 같았다.
- 문자열을 한 글자씩 순회하면서, 각 문자가 숫자인지 아니면 알파벳(영단어의 일부)인지를 판별한다.
2.문자가 숫자라면, 해당 숫자를 StringBuilder 객체에 바로 추가한다.
3.문자가 알파벳이라면, 해당 문자를 임시 문자열에 계속 추가하면서 이 임시 문자열이 사전에 정의된 숫자에 해당하는 영단어와 일치하는지 확인한다.
여기까지는 문제 없이 진행되었다.
하지만, 어려움이 있었던 부분은 영단어로 표현된 숫자를 정확히 식별하고 처리하는 과정이었다.
예를 들어, 입력값이 "1fourfive"인 경우를 생각해 봅시다. '1'과 'four'를 잘 처리하여 StringBuilder 객체에 "14"로 추가했다고 가정하자.
이후 문제는 'five'라는 문자열을 어떻게 처리할 것인가였다.
'five'와 같이 이미 처리된 숫자 뒤에 이어진 영단어를 식별하고 처리하는 데 있어 명확한 방법을 찾는 데 어려움을 겪었다.
제출코드(수정)
class Solution {
public int solution(String str) {
Map<String, Integer> wordToNumber = new HashMap<>();
wordToNumber.put("zero", 0);
wordToNumber.put("one", 1);
wordToNumber.put("two", 2);
wordToNumber.put("three", 3);
wordToNumber.put("four", 4);
wordToNumber.put("five", 5);
wordToNumber.put("six", 6);
wordToNumber.put("seven", 7);
wordToNumber.put("eight", 8);
wordToNumber.put("nine", 9);
///////////////////////////////
StringBuilder tempWord = new StringBuilder();
StringBuilder result = new StringBuilder();
for (char c : str.toCharArray()) {
// 숫자인 경우: result에 추가
if (Character.isDigit(c)) {
result.append(c);
}
// 알파벳인 경우: tempWord에 추가
if (Character.isLetter(c)) {
tempWord.append(c);
// 영단어에 해당하면 result에 추가
if (wordToNumber.containsKey(tempWord.toString())) {
result.append(wordToNumber.get(tempWord.toString()));
tempWord.setLength(0); // StringBuilder 초기화
}
}
}
return Integer.parseInt(result.toString());
}
}이를 해결하기 위한 방법은 2개의 StringBuilder를 사용하는 방법이다.
임시 sb와 결과 sb를 만든 다음, 알파벳인 경우 tempWord라는 sb에 더한다음,
아래 코드를 통해 map이 tempWord를 포함하는지 확인한다.
만약 포함하면 result에 포함시킨다.
if (wordToNumber.containsKey(tempWord.toString())) {
result.append(wordToNumber.get(tempWord.toString()));
// StringBuilder 초기화
tempWord.setLength(0);
}모범답안1
class Solution {
private static final String[] words = {
"zero", "one", "two", "three", "four", "five",
"six", "seven", "eight", "nine"
};
public int solution(String str) {
for (int i = 0; i < words.length; i++) {
str = str.replace(words[i], Integer.toString(i));
}
return Integer.parseInt(str);
}
}- 영단어 문자열을 구성한다.
- 영단어 배열을 순회하며 입력 문자열에 등장하는 모든 영단어를 치환한 문자열을 생성한다.
- 문자열을 정수로 변환한다.
간단한 방법이지만 전체 문자열을 새로 구성하므로 최적의 방식보다는 비효율적이다.
replace()를 한번 실행하는데 O(N)이 소요된다.
이를 M번 반복하므로 O(NM)이 소요된다.
문제에서 N의 최댓값은 50, M의 최댓값은 10이므로 아주 넉넉한 시간복잡도다.
replace() 이모저모
replace()의 시간복잡도가 어떻게 O(N)인걸까??
변환하려면 문자열을 원본 문자열에서 찾아야 하는데, 찾는 문자열의 길이가 시간 복잡도에 영향을 미치지는 않을까?
놀랍게도 찾는 문자열의 길이는 문자열 검색에서 중요하지 않다.
이는 문자열 검색 알고리즘 중 KMP 알고리즘을 살펴보면 알 수 있다.
이 알고리즘은 원본 문자열의 길이를 N, 찾는 문자열의 길이를 M이라고 하면 O(N+M) 시간복잡도를 갖는다. 찾는 문자열의 길이가 원본 문자열의 길이보다 크다면 애초에 검색할 수 없는 문자열이기 때문에 둘 중 더 큰 값인 O(N)으로 표기할 수 있다.
배운점
- Character.isLetter, isDigit을 통해 character의 타입을 알 수 있다.
- StringBuilder를 초기화하려면, sb.setLength(0); 을 사용해야 한다.
- replace()의 시간복잡도는 O(N)이다.
