[Swift | 프로그래머스 Lv.2] k진수에서 소수 개수 구하기 (2022 KAKAO BLIND RECRUITMENT)

Minji Kim·2022년 3월 2일
0
post-thumbnail

문제

문제 설명

양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.

  • 0P0처럼 소수 양쪽에 0이 있는 경우
  • P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우
  • 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우
  • P처럼 소수 양쪽에 아무것도 없는 경우
  • 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.
    • 예를 들어, 101은 P가 될 수 없습니다.

예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진법으로 보았을 때 소수여야 한다는 점에 주의합니다.) 211은 P0 형태에서 찾을 수 있으며, 2는 0P0에서, 11은 0P에서 찾을 수 있습니다.

정수 nk가 매개변수로 주어집니다. nk진수로 바꿨을 때, 변환된 수 안에서 찾을 수 있는 위 조건에 맞는 소수의 개수를 return 하도록 solution 함수를 완성해 주세요.


제한사항

  • 1 ≤ n ≤ 1,000,000
  • 3 ≤ k ≤ 10

입출력 예

nk
4376743
11001110

입출력 예 설명

입출력 예 #1
문제 예시와 같습니다.
입출력 예 #2
110011을 10진수로 바꾸면 110011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 11, 11 2개입니다. 이와 같이, 중복되는 소수를 발견하더라도 모두 따로 세어야 합니다.


제한시간 안내

  • 정확성 테스트 : 10초

풀이

나의 풀이

  1. n을 k진수로 바꾸기
  2. 0을 기준으로 나누기(split)
  3. 소수 구해서 개수 리턴하기
import Foundation

func solution(_ n:Int, _ k:Int) -> Int {
    var result = 0
    let split = String(n, radix: k).split(separator: "0").map { Int($0)! }   // k진수 변환 후 0 split
    let filter = split.filter { $0 != 1 } // 1 제외
    
    // 소수 구하기
    filter.forEach { num in
        var prime = true
        for i in 2...Int(sqrt(Double(num))) + 1 {
            if num % i == 0 && i != num {   // 자기 자신이 아닌 수로 나누어 떨어지면
                prime = false
                break
            }
        }
        
        if prime {
            result += 1
        }
    }
    
    return result
}
정확성테스트정확성테스트
테스트 1 〉통과 (14.28ms, 16.4MB)테스트 2 〉통과 (0.10ms, 16.2MB)
테스트 3 〉통과 (0.10ms, 16.4MB)테스트 4 〉통과 (0.14ms, 16.5MB)
테스트 5 〉통과 (0.10ms, 16.4MB)테스트 6 〉통과 (0.11ms, 16.3MB)
테스트 7 〉통과 (0.10ms, 16.4MB)테스트 8 〉통과 (0.11ms, 16.3MB)
테스트 9 〉통과 (0.12ms, 16.2MB)테스트 10 〉통과 (0.11ms, 16.5MB)
테스트 11 〉통과 (0.11ms, 16.2MB)테스트 12 〉통과 (0.11ms, 16.2MB)
테스트 13 〉통과 (0.11ms, 16.4MB)테스트 14 〉통과 (0.10ms, 16.3MB)
테스트 15 〉통과 (0.10ms, 16.3MB)테스트 16 〉통과 (0.12ms, 16.6MB)

다른 사람의 풀이

로직은 내 풀이와 유사하다. 하지만 다른 점이 있다면 소수를 찾는 부분이다. 나는 for 문을 이용해서 2부터 제곱 근까지 반복하며 소수를 찾는데, 자기 자신이 아닌 수로 나누어지면 break 하여 그 뒤에 수는 검사하지 않는다.

아래 풀이에서는 while 문을 이용했고 2부터 제곱 근까지 쭉 검사한다. 그래서 테스트 결과의 실행 시간을 보면 미세하게 내 풀이가 빠른 걸 볼 수 있다. 아마 이 부분 때문에 차이가 나지 않았나 싶다.

그래도 아래 풀이는 따로 함수를 만들어서 더 깔끔하다.

import Foundation

func solution(_ n: Int, _ k: Int) -> Int {
    let s = String(n, radix: k)
    return s.split(separator: "0").filter { p in !p.isEmpty && p != "1" && isPrime(Int(p)!) && (s.contains("0\(p)0") || s.contains("\(p)0") || s.contains("0\(p)") || s.contains(p)) }.count
}

private func isPrime(_ n: Int) -> Bool {
    var i = 2

    while i <= Int(sqrt(Double(n))) {
        guard n % i != 0 else {
            return false
        }
        i += 1
    }
    return true
}
정확성테스트정확성테스트
테스트 1 〉통과 (18.01ms, 16.2MB)테스트 2 〉통과 (0.12ms, 16.2MB)
테스트 3 〉통과 (0.13ms, 16.7MB)테스트 4 〉통과 (0.12ms, 16.3MB)
테스트 5 〉통과 (0.12ms, 16.3MB)테스트 6 〉통과 (0.14ms, 16.7MB)
테스트 7 〉통과 (0.14ms, 16.6MB)테스트 8 〉통과 (0.11ms, 16.3MB)
테스트 9 〉통과 (0.17ms, 16.4MB)테스트 10 〉통과 (0.12ms, 16.4MB)
테스트 11 〉통과 (0.10ms, 16.3MB)테스트 12 〉통과 (0.10ms, 16.5MB)
테스트 13 〉통과 (0.12ms, 16.4MB)테스트 14 〉통과 (0.10ms, 16.2MB)
테스트 15 〉통과 (0.10ms, 16.4MB)테스트 16 〉통과 (0.15ms, 16.4MB)

정리


목표 풀이 시간 : 1시간
실제 풀이 시간 : 46분
정답률 : 55.82%

이 문제는 2021년 9월에 진행된 2022 KAKAO BLIND RECRUITMENT 1차 코딩 테스트에 출제된 문제로 총 7문제 중 두 번째로 출제되었다.

해설

이 문제는 진법 변환 후에 변환된 숫자를 0을 기준으로 파싱하고, 파싱 한 숫자를 소수 판별해 해결할 수 있는 문제입니다.

소수 판별하는 데에는 대표적으로 2가지 방법이 있습니다. 첫 번째로 에라토스테네스의 체가 있고, 두 번째는 어떤 수 n을 2부터 루트(n)까지 나눈 나머지가 모두 0이 아님을 확인하는 방법이 있습니다. 효율적인 소수 판별 알고리즘인 에라토스테네스의 체를 사용해서도 풀 수 있지만, 이 문제에서는 두 번째 방법으로도 충분히 해결할 수 있습니다.

이 문제의 제한사항을 살펴보면 n이 1부터 1,000,000까지이고 k는 3부터 10까지이므로, 1,000,000을 3진수로 바꾸면 1,212,210,202,001입니다. 일반적으로 진법 변환은 문자열을 사용해 구현하므로, 진법 변환된 문자열을 0을 기준으로 파싱 한 후에 소수를 판별하는 과정에서 정수 자료형으로 변환이 필요하게 됩니다. 이때, 개발 언어에 따라서 int 자료형의 표현 범위를 벗어날 수 있음을 유의해서 문제를 풀어야 합니다. 예를 들어 997,244를 3진수로 바꾸면 1,212,122,221,222가 됩니다. 이 숫자는 0이 없기 때문에 진법 변환된 숫자 그대로 정수 자료형으로 변환해서 소수 판별을 해야 하는데, 이는 int 자료형의 표현 범위를 벗어난다는 것을 알 수 있습니다.


후기

이번 문제는 레벨 2 치고 쉬웠다. 오히려 레벨 1 문제가 더 오래 걸렸다. 하지만 한 가지 놓친 게 있다면 제한사항을 간과했다는 점이다. 해설을 보고 알았는데, int 범위를 벗어날 수도 있으니 이에 유의해야 한다는 점이다. 문제를 풀면서 전혀 이 부분에 대한 문제를 생각하지 않고 풀었다. 다행이라 하기엔 애매하지만 실행했을 때 에러가 나지 않아서 잘 푼 줄 알았다.

다음부턴 문제 설명뿐만 아니라 제한사항까지 꼼꼼히 살펴보면서 코딩하자!👊

profile
iOS Developer

0개의 댓글