[2022 KAKAO BLIND RECRUITMENT] 풀어보기 (✨진수 변환, ✨소수 찾기)

✏️ [1번] 신고 결과 받기 (Level 1)

• 신고하는 정보, 신고받는 정보 담는 dict() 자료구조 2개 활용 & 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다. 조건 예외 처리

https://github.com/sallyy1/Algorithm/issues/135

✏️ [2번] k진수에서 소수 개수 구하기 (Level 2)

- 문제

- 개선 POINT ✨

• 💡 문제의 모든 조건을 충족하는 하나의 조건은 결국, ➡️ split("0")으로 쪼개진 각 단위 String들이 소수(prime)에 해당되는지를 판별하는 것 ..!!
• (빡구현해도 정답 나오지만, 훨씬 쉽고&빠르게 접근 가능하며 실행속도도 빠름)

- 풀이 과정

https://github.com/sallyy1/Algorithm/issues/136

☑️ 진수 변환 알고리즘 (10진수 숫자 n ➡️ k진수로 변환)

- 방법 1. (풀이에서 내가 사용한 함수)

def convert(n, base): ## base: 변환할 k진수
    T = "0123456789ABCDEF"
    q, r = divmod(n, base)


    if q == 0:
        return T[r]
    else:
        return convert(q, base) + T[r]

- 방법 2. (다른 사람의 코드)

    result_str = '' ## 빈 문자열 생성

    while n:
        result_str += str(n % k) ## (1)나머지는 이어붙이고
        n = n //  k ## (2)몫을 다음으로 넘기기

    result_str = result_str[::-1] ## 결과 문자열 뒤집기 !!

☑️ 진수 변환 알고리즘 (k진수 숫자를 표현한 문자열 ➡️ 10진수로 변환)

int(string_number, base_k)

☑️ 소수 찾기 알고리즘

- 방법 1. ((루트 n +1) 이전 수까지만 체크) - for문 사용 ✨

def is_prime(n):
    if n <= 1:
        return False
    
    for pre in range(2, int(n ** 0.5)+1): ## (주의) 루트 값까지만 살펴보기 !!
        if n % pre == 0:
            return False
        
        
    return True

- 방법 2. ((루트 n +1) 이전 수까지만 체크) - while문 사용 ✨

def is_prime(n):
    if n < 2: # (예외 처리) 1은
        return False # 소수가 아님

  	i = 2
    while i*i <= n: # 파이썬 for문 대신 while문으로 표현 가능 (2 ~ 루트N 까지 약수인지 확인)
        if (n % i) == 0: # 중간에 약수가 존재한다면
            return False # 소수가 아님
    
    i += 1

  #else: # 무사히 다 돌았다면
  return True # 소수가 맞음

- 방법 3. (check 배열에 저장) - ❌ 이 문제에선 런타임 에러 case 2개 발생

MAX = 1000000
check = [0] * (1000000+1)
check[0] = check[1] = True # (예외 처리) -> 소수가 아님 -> 지움 처리


for i in range(2, MAX+1): # (2 ~ 루트 N) 동안 체크
    if not check[i]:  # False
        j = i+i # j는 i의 배수
        while j <= MAX:
            check[j] = True # 지움 처리
            j += i # 다음 배수

- 🙋‍ 이유:

• 자료형 문제...? 🤔 (소수 판별 알고리즘에서 int 대신 long long int 를 사용하면 해결된다는 Java 질문글 존재)
• 내 경우엔 MAX 값 에서 발생하는 check 배열 관련 런타임 에러 ..? 🤔