프로그래머스 : k진수에서 소수 개수 구하기 (진수변환, 소수)

이번문제도 풀어서 구현하는거는 어렵지 않았다.

 

다만, 예외사항들이 존재해 중간중간 디버깅하면서 처리해 주는것도 어렵지 않았다.

 

여기서 나는 크게 두가지 구현을 생각했다.

1. 진수변환 2. 소수찾기

 

진수변환은 계속 나누어 나머지를 역순으로 적용하는 방법을 사용.

소수찾기는 소수란 1과 자기자신으로만 나눠지기에 둘을 제외한 나머지 값으로 나누었을때 안나눠지면 소수로 판단

 

이렇게 구현을 하고 나니 2가지 케이스에서 이슈가 발생했다.

1번째는 런타임 이슈, 2번째는 느낌상 0 값을 넣었을때였다.

 

2번째는 역시 0을 넣었을때 1이 나와, 0이 나오도록 예외처리를 해주었다.

 

여기서 핵심은 1번 이슈인거 같은데, 소수를 구할때 1~자기자신까지 모두 나눌 필요 없이 제곱근까지만 나눠보면 판단 할 수 있다는 점이다. 이렇게하면 반복문이 확연히 줄어들어 시간이 단축됨을 알 수 있다.

 

이렇게해서 결국 정답을 맞았다. ~!!!

 

추가로, 다른 사람의 풀이를 보니 진법변환을 간편하게 하는 방법을 발견했다.

 

10진수 -> n진수

Integer.toString(100, 2) : 100을 2진수로 변환

 

n진수 -> 10진수

Integer.parseInt("110011",2) : 110011의 2진수를 10진수로 변환

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = -1;
        
        // k진수로 변환
        List<String> nList = new ArrayList<String>();
        while(n >= k) {
        	nList.add(String.valueOf(n%k)); //나머지
        	n = n/k;
        }
        nList.add(String.valueOf(n)); //마지막 몫 넣기
        
        List<String> bList = new ArrayList<String>(); //역순으로 넣기
        for(int i= nList.size()-1; i >=0; i--) {
        	bList.add(nList.get(i));
        }
        
        //규칙에 맞는 숫자 찾기
        List<Long> lList = new ArrayList<Long>();
        String tmp = "";
        for(int i=0; i < bList.size(); i++) {
        	String b = bList.get(i);
        	if("0".equals(b) && !tmp.isEmpty()) {
        		lList.add(Long.parseLong(tmp));
        		tmp = ""; //초기화
        	}
        	else if(i == bList.size()-1) {
        		tmp +=b;
        		lList.add(Long.parseLong(tmp));
        	}
        	else  {
        		tmp +=b;
        	}
        }
        
        // 소수찾기
        int count =0;
        for(long l : lList) {
        	boolean check = true; //소수인지 체크
        	if(l == 1 || l ==0) { // 1, 0은 소수가 아님.
        		continue;
        	}
        	
        	for(int i=2; i <= Math.sqrt(l); i++) { // 소인수분해시 1과 자기자신만 나와야함.
        		if(l%i == 0) { //한번이라도 나눠떨어지면 소수가 아님
        			check = false;
        			break;
        		}
        	}
        	
        	if(check == true) {
        		count++;
        	}
        }
        
        answer = count;
        return answer;
    }
}