[1/28] Kakao Internship 기출문제 풀이

👉 사용 언어 : PYTHON3

캐시

✅ Solution

from collections import deque

def solution(cacheSize, cities):
    answer = 0
    cache = deque([])
    for j in range(len(cities)):
        cities[j] = cities[j].lower()
    for i in cities:
        if cacheSize == 0:
            answer = 5 * len(cities)
        elif i not in cache:
            if len(cache) < cacheSize:
                cache.append(i)
            else:
                cache.popleft()
                cache.append(i)
            answer += 5
        else:
            cache.remove(i)
            cache.append(i)
            answer += 1
    return answer

 

👉 아이디어

• cache hit일 경우 실행시간: 1 && cache miss일 경우 실행시간: 5
  • cache hit : 캐시 메모리에 찾는 데이터가 존재할 때
  • cache miss : 캐시 메모리에 찾는 데이터가 존재하지 않을 때
• 대소문자 구분 없이 비교하기 위해 cities의 모든 원소를 lower()를 사용하여 소문자로 변환하여 재할당한다.
• 이전 카카오 기출문제인 "두 큐 합 같게 만들기"와 같이 시간복잡도를 줄이기 위해 deque를 사용한다.
• if-elif-else문으로 각각의 케이스로 나누어 실행문을 작성한다.
  • 캐시 메모리 크기 == 0
    • 5 * 도시 이름 개수 반환
  • 데이터가 캐시 메모리에 없는 경우
    • 캐시 메모리 배열 길이 < cacheSize
      • 캐시 메모리에 데이터 추가만!
    • 캐시 메모리 배열 길이 >= cacheSize
      • 맨 앞 요소 pop 후, 새로운 데이터 추가
    • cache miss 이므로 +5
  • 나머지 _ 데이터가 캐시 메모리에 있는 경우
    • 원래 있던 데이터를 가장 최신 데이터로 업데이트해줘야 하므로
    • 원래 있던 데이터 pop 후, 다시 맨 끝에 추가
    • cache hit 이므로 +1

✅ 캐시(페이지) 교체 알고리즘은 LRU (Least Recently Used)

: 가장 오랫동안 사용되지 않은 페이지를 제거하는 알고리즘

 

✅ 다른 사람 풀이 참고

def solution(cacheSize, cities):
    import collections
    cache = collections.deque(maxlen=cacheSize)
    time = 0
    for i in cities:
        s = i.lower()
        if s in cache:
            cache.remove(s)
            cache.append(s)
            time += 1
        else:
            cache.append(s)
            time += 5
    return time

 

👉 깨달은 것 / 알게된 것

• 길이 제한을 collections.deque(maxlen=cacheSize)를 통해 두었다. (조건으로 따로 빼지 않아도 된다.)
• 새로운 데이터를 캐시에 저장된 데이터와만 비교하면 되므로 .lower()를 for문 안에서 사용하였다. (간결성 및 가독성 ↑)

k진수에서 소수 개수 구하기

✅ Solution

def solution(n, k):
    answer = 0
    k_base = []
    while n > 0:
        k_base.append(n%k)
        n = n // k
    k_base.reverse()
    k_base = ''.join(map(str, k_base)).split('0')
    for i in k_base:
        if i != '':
            i = int(i)
            for j in range(1, int(i**(1/2)) + 1):
                if i % j == 0 and j > 1:
                    answer += 1
                    break    
    return len(k_base) - answer - (k_base.count('1') + k_base.count(''))

 

👉 아이디어

• 0을 기준으로 숫자(문자열)을 나눈다.
  • .split('0')을 사용한다.
• k 진수로 바꾸는 법 > https://mungchstudy.tistory.com/58 참고
  • 10진수 > 2, 8, 16진수 함수만 지원되므로 10진수 > k진수로 변환하는 별도의 함수를 만든다.
  • 위의 풀이에서는 while문 을 돌려 나머지를 배열에 넣어준 후, 역순으로 정렬하여 k진수로 나타내었다.
• 배열 역순 정렬 : list.reverse()
  • 메모리 내의 배열 원소들을 직접 수정하므로 반환값은 None이다.
• 정수 배열 > 문자열 변환 : ''.join(map(str, k_base))
  • map으로 숫자를 담고 있는 리스트 값들을 string으로 바꾸고, join을 사용하여 최종적으로 string이 출력된다.
• 모든 가공 처리를 완료한 k_base에는 ''이 존재할 수 있으므로 for문 안에서 뽑아낸 원소가 ''이 아닐 경우에만 실행문을 작성한다.
  • '' 이 존재할 수 있는 경우 : n진수로 변환한 값에서 0이 연속으로 있는 경우
• 소수가 아닌 경우 를 찾고 나중에 리턴할 때 전체 길이에서 빼준다.
  • 소수는 값 전체를 순회하는 것이 아니라 제곱근 까지만 순회하도록 반복문을 구현한다.
  • 1은 소수가 아니므로 조건문을 사용하여 제외한다.
• 리턴값 : k_base 길이 - 소수 아닌 경우 - (1 또는 ''인 경우)

✅ 다른 사람 풀이 참고

# n을 k진법으로 나타낸 문자열 반환
def conv(n, k):
    s = ''
    while n:
        s += str(n%k)
        n //= k
    return s[::-1]

# n이 소수인지 판정
def isprime(n):
    if n <= 1: return False
    i = 2
    while i*i <= n:
        if n%i == 0: return False
        i += 1
    return True

def solution(n, k):
    s = conv(n,k)
    cnt = 0
    for num in s.split('0'):
        if not num: continue # 빈 문자열에 대한 예외처리
        if isprime(int(num)): cnt += 1
    return cnt

 

👉 n > k진수 변환 함수, 소수 판별 함수 모두 별도로 작성해주었다.

👉 깨달은 것 / 알게된 것

• 빈 문자열에 대한 예외처리 조건을 if not num 으로 하고 continue를 실행함으로써 코드의 가독성 ↑
• 코드 길이는 길지만 훨씬 보기 좋은 코드❗️