[LeetCode- Part. 3] 4. 숫자를 영어 단어로 변환 # (+분할과 정복)

https://leetcode.com/problems/integer-to-english-words/

Integer to English Words - LeetCode

 

 

참고 자료

https://and-some.tistory.com/897

[LeetCode- Ch3. 배열] 5. 빗물 담기 # [+ 분할과 정복]

 

---

규칙을 찾아 분할과 정복을 수행

1. 1000단위마다 Thousand, Million, Billion이 들어간다

2. 1000단위 미만 생성 함수 작성

3. 1000단위로 나누기 위해 뒤부터 1000씩 분리해 넣는다.

 

 

(1) substring으로 시도 -> String으로 바꾸고 다시 int형으로 바꿔야한다.

(2) 재귀 이용

 

class Solution {
    public String numberToWords(int num) {
        //Divide & Conquer
        
        //Hundred
        //백
        //Thousand
        //천
        //Million
        //백만
        //Billion
        //십억
        if(num==0) return "Zero";
        
        ArrayList<Integer> list = new ArrayList<>();
        String tmp=Integer.toString(num);

        if(tmp.length<=3){
            divide(tmp);
        }
        else{
            while(tmp.length()>3){
                list.add(Integer.parseInt(tmp.substring(tmp.length()-3,tmp.length())));
                tmp=tmp.substring(0,tmp.length()-3);
            }
            list.add(Integer.parseInt(tmp));
        }
        
        //for(int x: list) System.out.println(x);
        String answer="";
        for(int x:list){
            answer+=convert(x);
        }
        
        return answer;
    }
    
    String[] ten = new String[] { "", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine" };
	String[] twenty = new String[] { "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen","Seventeen", "Eighteen", "Nineteen" };
	String[] hundred = new String[] { 
	"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty","Ninety" };
    private String convert(String s){
        //3가지 조건 분기 
        //(1) 10단위 미만
        //(2) 20단위 미만
        //(3) 100단위 미만
        
        //몫과 나머지로 표현가능
        String res=
        
    }
    private String divide(String s){
        if(num<10){
            s=ten[num];
        }else if(num<20){
            s=twenty[num-10];
        }else if(num<100){
            s=hundred[num-10]+" "+ten[num%10];
        }
    }
}

 

(2) 재귀 이용

 

+) 세련된 풀이

class Solution {
    String[] ten = new String[] { "", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine" };
	String[] twenty = new String[] { "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen","Seventeen", "Eighteen", "Nineteen" };
	String[] hundred = new String[] { 
	"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty","Ninety" };

    public String numberToWords(int num) {
        if(num==0) return "Zero";
        return helper(num);
    }
    private String helper(int num){
        String s="";
        if(num<10){
            s=ten[num];
        }else if(num<20){
            s=twenty[num-10];
        }else if(num<100){
            //100단위 + 10단위는 재귀
            //나머지
            if(num%10==0)
                s=hundred[num/10];
            else
                s=hundred[num/10]+" "+helper(num%10);
        }else if(num<1000){
            //몫과 나머지
            if(num%100==0) s=helper(num/100) +" Hundred";
            else s=helper(num/100) +" Hundred "+helper(num%100);
        }else if(num<1000000){
            //몫과 나머지
            if(num%1000==0) s=helper(num/1000) +" Thousand";
            else s=helper(num/1000) +" Thousand "+helper(num%1000);
        }else if(num<1000000000){
            //몫과 나머지
            if(num%1000000==0) s=helper(num/1000000) +" Million";
            else s=helper(num/1000000) +" Million "+helper(num%1000000);
        }else
            //몫과 나머지
            if(num%1000000000==0) s=helper(num/1000000000) +" Billion";
            else s=helper(num/1000000000) +" Billion "+helper(num%1000000000);
        return s;
    }
}

 

---

class Solution {
    String[] one={"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
String[] ten={"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen","Twenty"};
String[] twen={"","","Twenty","Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty","Ninety"};
    static String answer="";
    public String numberToWords(int num) {
  //몫과 나머지 이용
        //Hundred, Thousand, Million, Billion 순서
        //1단위
        //10단위
        //20단위
        //100단위
        //1000단위
        //1000000단위
        if(num==0) return "Zero";
        return solve(num);
    }
    private String solve(int num){
        if(num<10){
            answer=one[num];
        }else if(num<20){
            //ten[num-10]
            answer=ten[num-10];
        }else if(num<100){
            if(num%10==0) answer=twen[num/10];
            else answer=twen[num/10]+" "+solve(num%10);
        }else if(num<1000){
            if(num%100==0) answer=one[num/100]+" Hundred";
            else answer=one[num/100]+" Hundred "+solve(num%100);
        }else if(num<10000){
            if(num%1000==0) answer=one[num/1000]+" Thousand";
            else answer=one[num/1000]+" Thousand "+solve(num%1000);
        }
        else if(num<1000000){
            if(num%1000==0) answer=solve(num/1000)+" Thousand";
            else answer=solve(num/1000)+" Thousand "+solve(num%1000);
        }else if(num<1000000000){
            if(num%1000000==0) answer=solve(num/1000000)+" Million";
            else answer=solve(num/1000000)+" Million "+solve(num%1000000);
        }else{
            if(num%1000000000==0) answer=solve(num/1000000000)+" Billion";
            else answer=solve(num/1000000000)+" Billion "+solve(num%1000000000);
        }
        return answer;
    }
}