99클럽 코테 스터디 3일차 TIL + [프로그래머스] 숫자 문자열과 영단어

💡문제

[level 1] 숫자 문자열과 영단어 - 81301

문제 링크

성능 요약

메모리: 71.7 MB, 시간: 24.66 ms

 

 

 

 

 

---

🤔접근법

문제 요약

• 숫자와 영어로 된 숫자가 띄어쓰기 되지 않은 상태로 문자열로 주어진다.
• 부분부분 영어로 되어 있는 숫자로 바꿔서 정수형으로 출력하라.

범위 체크 및 시간복잡도 예상

• 1 ≤ 주어지는 문자열의 길이 ≤ 50
• 모든 문자열이 숫자라고 하더라도 50이므로 시간복잡도가 null~null~한 아주 착한 문제

풀이법

⭕ 접근 방법. 완탐

1. 주어진 문자열에서 1 ~ 9 까지 검색 , zero ~ nine 까지 검색
2. 만약 존재한다면 존재하는 문자열의 첫번째 인덱스을 반환받아 result 배열에 영문숫자와 치환되는 숫자를 기입
3. 중복되는 숫자가 존재할 수 있으므로 이미 검색된 문자열을 @로 치환
4. 더이상 검색되는 영문숫자와 숫자가 없다면 result 배열을 처음부터 순회하면서 숫자 합치기

substring 시간복잡도 → $O(N)$

indexOf 시간복잡도 → $O(NM)$ (m은 찾고자하는 문자열의 길이인데 영문숫자 최대 길이는 5이다)

➡️ 해당 풀이법의 시간 복잡도 : $O(N^2M)$

 

 

---

😎SUCCESS

단박에 성공하지 못한 이유는 ?

• String 관련 메소드를 다 까먹어서 검색했다.
• 시간복잡도도 기억안남
• repeat 이라는 좋은 메소드를 알아냈다 ㅎ

👩‍💻 코드

import java.io.*;
import java.util.*;

class Solution {
    // 숫자에 해당하는 영어 단어 배열
    static String[] engNum = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
    // 결과를 저장할 배열
    static int[] result = new int[51];
    // 더 이상 숫자를 찾지 못했는지 여부를 나타내는 플래그
    static boolean flag = true;
    
    public static int solution(String s) {
        int answer = 0;
        // result 배열을 -1로 초기화하여 초기값을 설정
        Arrays.fill(result, -1);
        
        while (true) {
            flag = true;
            // 0부터 9까지의 숫자와 해당하는 영어 단어를 체크
            for (int i = 0; i < 10; i++) {
                s = checkNumber(s, i);
                s = checkEngNumber(s, i);
            }
            // 더 이상 숫자를 찾지 못하면 루프 종료
            if (flag) {
                break;
            }
        }

        // result 배열을 이용해 최종 숫자를 만듦
        answer = Integer.parseInt(makeNum());
        return answer;
    }

    private static String makeNum() {
        String answer = "";
        // result 배열에서 숫자를 하나의 문자열로 결합
        for (int i = 0; i < 51; i++) {
            if (result[i] != -1) {
                answer = answer + result[i];
            }
        }
        return answer;
    }

    private static String checkNumber(String s, int i) {
        // 숫자 문자의 첫 번째 위치를 찾음
        int idx = s.indexOf(String.valueOf(i));
        if (idx != -1) {
            flag = false;
            result[idx] = i;
            // 찾은 숫자 문자를 '@'로 대체
            s = s.substring(0, idx) + "@" + s.substring(idx + 1);
        }
        return s;
    }

    private static String checkEngNumber(String s, int i) {
        // 영어 단어의 첫 번째 위치를 찾음
        int idx = s.indexOf(engNum[i]);
        if (idx != -1) {
            flag = false;
            result[idx] = i;
            // 찾은 영어 단어를 같은 길이의 '@' 문자열로 대체
            s = s.substring(0, idx) + "@".repeat(engNum[i].length()) + s.substring(idx + engNum[i].length());
        }
        return s;
    }
}