코딩테스트 - 프로그래머스/JAVA
[프로그래머스 / 2022 KAKAO BLIND RECRUITMENT / 자바(JAVA)] k진수에서 소수 개수 구하기
읁;
2024. 5. 17. 19:41
[프로그래머스 / 2022 KAKAO BLIND RECRUITMENT / 자바(JAVA)] k진수에서 소수 개수 구하기
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/92335?language=java
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[ 요약 ]
더보기
시작 시간 : 17시 30분
종료 시간 : 18시 18분
소요 시간(분) : 48분
도전 횟수 (제출 횟수) : 3
로직 및 풀이 참고 여부 : O
[ 풀어보기 ]
정답 풀이
📌 로직
< 메인 로직 >
- n을 k진법으로 변환한 String intToString을 구해준다.
- Integer.toString(n, k)를 통해, 10진법인 n을 k진법으로 변환할 수 있다.
- 반대로, k진법인 String num을 10진법으로 바꾸기 위해서는 Integer.parseInt(num, k)를 해주면 됨
- 이를 char Array로 변환한다.
- intToString.toCharArray() 를 통해 String을 char 배열로 변환한다.
- StringBuffer 객체 sb를 만든다.
- "2"번에서 만든 charArray를 순회하는 확장 for문을 만든다. 각 요소는 char a로 받는다.
- StringBuffer에 a를 차례로 append 해준다.
- 이 때, a가 0이면 append 하지 않고, StringBuffer에 지금까지 쌓여 만들어진 숫자를
소수인지 판별한다.- 만약 소수라면 answer ++;
- 그리고 소수인지 아닌지와 상관없이, StringBuffer를 비워준다.
< 소수 판별 로직 >
- 소수인지 아닌지 판별할 숫자 num의 제곱근 n을 구한다.
- num을 2부터 n까지 나누었을 때,
- 나눠 떨어지는 숫자가 있다면 이는 소수가 아니다.
- 나눠 떨어지는 숫자가 없다면 소수이다.
📌 코드
class Solution {
public int solution(int n, int k) {
int answer = 0;
String intToString = Integer.toString(n, k); // n진법으로 바꾸기
char[] intArray = intToString.toCharArray(); // char 배열로 변환하기
StringBuffer sb = new StringBuffer(); // StringBuffer 객체 생성
for(char a : intArray) {
if(a == '0') { // 만약 a가 0이면
if(sb.length()!= 0 && isPrime(sb.toString()))
answer++;
sb.setLength(0); // StringBuffer 비워주기
} else { // a가 0이 아니면
sb.append(a);
}
}
// for문의 순회가 끝난 후, StringBuffer가 비워지지 않았다면
// 여기 남은 숫자들 또한 소수 판별을 해주어야 한다.
if(sb.length() != 0 && isPrime(sb.toString()))
answer++;
return answer;
}
// 해당 숫자가 소수인지, 아닌지 판별하는 메소드
private boolean isPrime(String n) {
long number = Long.parseLong(n);
// int -> long으로 바꾸어 런타임오류 해결
if(number < 2) return false;
long sqrt = (long)Math.sqrt(number);
for(int i=2; i<=sqrt; i++) {
if(number % i == 0) return false;
}
return true;
}
}
📌 채점 결과
정확성 테스트
테스트 1 〉 통과 (16.06ms, 85.5MB)
테스트 2 〉 통과 (0.21ms, 76.3MB)
테스트 3 〉 통과 (0.19ms, 71.3MB)
테스트 4 〉 통과 (0.21ms, 78.3MB)
테스트 5 〉 통과 (0.20ms, 75.9MB)
테스트 6 〉 통과 (0.28ms, 77.6MB)
테스트 7 〉 통과 (0.16ms, 72.5MB)
테스트 8 〉 통과 (0.16ms, 70.2MB)
테스트 9 〉 통과 (0.16ms, 77.8MB)
테스트 10 〉 통과 (0.20ms, 75.6MB)
테스트 11 〉 통과 (0.18ms, 73.9MB)
테스트 12 〉 통과 (0.19ms, 74.6MB)
테스트 13 〉 통과 (0.23ms, 71.3MB)
테스트 14 〉 통과 (0.17ms, 70.9MB)
테스트 15 〉 통과 (0.17ms, 76.7MB)
테스트 16 〉 통과 (0.12ms, 76.7MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0
오답 풀이 1
📌 코드
class Solution {
public int solution(int n, int k) {
int answer = 0;
// n진법으로 바꾸기
String intToString = Integer.toString(n, k);
char[] intArray = intToString.toCharArray();
StringBuffer sb = new StringBuffer();
for(char a : intArray) {
if(a == '0') {
if(sb.length()!= 0) {
if(isPrime(sb.toString())) answer++;
}
sb.setLength(0);
} else {
sb.append(a);
}
}
if(sb.length() != 0) {
if(isPrime(sb.toString())) answer++;
}
return answer;
}
// 해당 숫자가 소수인지, 아닌지 판별하는 메소드
private boolean isPrime(String n) {
int number = Integer.parseInt(n);
if(number < 2) return false;
if(number == 2) return true;
int sqrt = (int)Math.sqrt(number);
for(int i=2; i<sqrt; i++) {
if(number % i == 0) return false;
}
return true;
}
}
📌 채점 결과
정확성 테스트
테스트 1 〉 실패 (런타임 에러)
테스트 2 〉 통과 (0.19ms, 77.3MB)
테스트 3 〉 통과 (0.16ms, 72.3MB)
테스트 4 〉 통과 (0.16ms, 73.2MB)
테스트 5 〉 통과 (0.25ms, 77.1MB)
테스트 6 〉 통과 (0.15ms, 76.9MB)
테스트 7 〉 통과 (0.17ms, 72.3MB)
테스트 8 〉 통과 (0.11ms, 77.7MB)
테스트 9 〉 통과 (0.13ms, 81.9MB)
테스트 10 〉 통과 (0.15ms, 74MB)
테스트 11 〉 실패 (런타임 에러)
테스트 12 〉 통과 (0.23ms, 76.5MB)
테스트 13 〉 통과 (0.18ms, 72.6MB)
테스트 14 〉 실패 (0.10ms, 73.8MB)
테스트 15 〉 통과 (0.14ms, 86.4MB)
테스트 16 〉 실패 (0.09ms, 75.8MB)
채점 결과
정확성: 76.2
합계: 76.2 / 100.0
📌 오답 이유
- 테스트 1, 테스트 11 런타임 에러
- isPrime 메소드 내에서, String n이 int로 변환되기에는 int의 범위를 벗어났을 수도 있겠다고 생각함.
- 범위가 더 큰 long으로 수정.
- 테스트 14, 16 에러
- 일단 이건 런타임 에러 해결하고나서...
오답 풀이 2
📌 코드
class Solution {
public int solution(int n, int k) {
int answer = 0;
// n진법으로 바꾸기
String intToString = Integer.toString(n, k);
char[] intArray = intToString.toCharArray();
StringBuffer sb = new StringBuffer();
for(char a : intArray) {
if(a == '0') {
if(sb.length()!= 0 && isPrime(sb.toString()))
answer++;
sb.setLength(0);
} else {
sb.append(a);
}
}
if(sb.length() != 0 && isPrime(sb.toString()))
answer++;
return answer;
}
// 해당 숫자가 소수인지, 아닌지 판별하는 메소드
private boolean isPrime(String n) {
long number = Long.parseLong(n);
// 런타임 오류 해결을 위해 int -> long으로
if(number < 2) return false;
if(number == 2) return true;
long sqrt = (long)Math.sqrt(number);
for(int i=2; i<sqrt; i++) {
if(number % i == 0) return false;
}
return true;
}
}
📌 채점 결과
정확성 테스트
테스트 1 〉 통과 (12.67ms, 74.1MB)
테스트 2 〉 통과 (0.16ms, 81.5MB)
테스트 3 〉 통과 (0.18ms, 79.6MB)
테스트 4 〉 통과 (0.21ms, 74MB)
테스트 5 〉 통과 (0.22ms, 86.9MB)
테스트 6 〉 통과 (0.16ms, 85MB)
테스트 7 〉 통과 (0.22ms, 77.4MB)
테스트 8 〉 통과 (0.14ms, 70.9MB)
테스트 9 〉 통과 (0.17ms, 74.8MB)
테스트 10 〉 통과 (0.19ms, 80.6MB)
테스트 11 〉 통과 (0.16ms, 73.3MB)
테스트 12 〉 통과 (0.12ms, 73.2MB)
테스트 13 〉 통과 (0.22ms, 80MB)
테스트 14 〉 실패 (0.17ms, 72.2MB)
테스트 15 〉 통과 (0.16ms, 85.2MB)
테스트 16 〉 실패 (0.17ms, 73.5MB)
채점 결과
정확성: 89.3
합계: 89.3 / 100.0
📌 오답 이유
- 테스트 14, 테스트 16 런타임 에러
- isPrime 내 for문의 조건식을 보니, 제곱근을 포함하지 않고 있었다.
- number가 제곱근으로 나누어지면 소수로 판별되어야 하는데, 그러지 못하고 있음.
[ 좋은 풀이 ]
풀이자 이름
📌 코드
class Solution {
public int solution(int n, int k) {
int ans = 0;
String temp[] = Integer.toString(n, k).split("0");
Loop : for(String t : temp) {
if(t.length() == 0) continue;
long a = Long.parseLong(t);
if(a == 1) continue;
for(int i=2; i<=Math.sqrt(a); i++)
if(a%i == 0) continue Loop;
ans++;
}
return ans;
}
}
[배운 점]
📌 배운 것
- 반복문에 이름(?) 을 달아줄 수 있음! - 이름 붙은 반복문
- 이를 통해 여러 개의 반복문이 중첩되어 있을 경우, continue와 break를 사용할 때 어떤 반복문을 벗어나는 지 등을 지정해줄 수 있음.
- https://eunzzzzz1.tistory.com/42
- 해당 수가 소수인지 판별하는 방법