프로그래머스 (카카오) | LV. 2 k진수에서 소수 개수 구하기 - 단순 구현 문풀 (Java)

⬛ 프로그래머스 (카카오) | LV. 2 k진수에서 소수 개수 구하기 - 단순 구현 문풀  (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

문제 설명

---

💚 문제 접근 방식

문제 접근이나 구현 자체는 단수하고 비교적 쉬운 편이었다.

기출 문제가 생각보다 쉬워보이면 엣지 케이스를 모두 고려하는 습관을 들여야한다.........

이 문제의 경우, n이 100만인데 일단 데이터 크기가 10만 넘어가면 주의를 해야 된다 더 효율적인 알고리즘을 쓰던지, 자료형 범위를 생각하던지.

 

1) n을 k진수로 변환하기 : String.toString(n,k) 를 하면 10진수를 k진수로 변환하여 String으로 준다.

2) 0을 기준으로 split(”0”) 하기

→ 중간에 00 이 낀 경우를 어떻게 처리하나 생각했었는데 어차피 0이 끼면 그걸 기준으로 split() 하기 때문에 빈 문자열을 담게 된다. 그래서 빈 문자열인 경우 continue 처리하면 0 제외한 숫자만 처리할 수 있따.

3) isPrime으로 소수 판별하며 answer++

---

💚 제출 코드

import java.util.*;
class Solution {
    //소수 확인용 
    private boolean isPrime(long val){        
         if(val < 2) return false;
         for(int i=2; i<=(int) Math.sqrt(val); i++){
            if(val % i == 0){
                return false;
            }
        }
        return true;
    }
    //솔루션 함수 
    public int solution(int n, int k) {
        int answer =0;
        
        String val = Integer.toString(n, k);//10진수를 k진수로 변환
        //0기준으로 split 하면 됨
        String[] tmp = val.split("0");
        
        for(String x : tmp){
            if(x.equals("")) continue;
            if(isPrime(Long.parseLong(x))) answer++;
        }
        
        return answer;
    }
}

---

1차 시도 | 테케 1, 11번 실패 ⇒ 오버플로우 터짐

1번 11번 실패

원인 : n은 최대 100만이다. 그래서 이를 k진수로 변환하게 될 경우 그 길이가 int형 범위를 넘어갈 수 있다. 그런데, 난 단순히 k진수로 변환된 String을 int형으로 변환해서 이진수를 판별했다. 그 부분이 문제였다. 최악의 경우에 오버플로우가 터질 수 있다는 것을 놓쳤다.

import java.util.*;
class Solution {
    //소수 확인용 
    private boolean isPrime(int val){        
         if(val < 2) return false;
         for(int i=2; i<= (int) Math.sqrt(val); i++){
            if(val % i == 0){
                return false;
            }
        }
        return true;
    }
    //솔루션 함수 
    public int solution(int n, int k) {
        int answer =0;
        
        String val = Integer.toString(n, k);//10진수를 k진수로 변환
        //0기준으로 split 하면 됨
        String[] tmp = val.split("0");
        
        for(String x : tmp){
            if(x.equals("")) continue;
            if(isPrime(Integer.parseInt(x))) answer++;
            //[원인] -> int형으로 변환하던 부분
			//0이 하나도 없다고 가정하면 k진수로 바뀐 문자열 길이가 int형 길이 벗어날 수 있다. (오버플로우)
        }
        
        return answer;
    }
}

---

💚 회고와 반성

시간 복잡도만 생각하면서 n이 백만이긴 하지만 이중 for문 쓰는 부분 없으니 k진수로 변환해서 구하면 되겠다고 단순하게 생각했다.

그런데, 시간 복잡도가 문제가 아니라 최악의 데이터 크기 100만을 k진수로 변환 시 그 길이가 자료형 범위를 넘어설 수 있따는 건 생각 못했다. 반성한다....