Punch!

1. 문제 설명

양의 정수 n을 k 진수로 바꿨을 때, 변환된 수 안에 소수 (prime number)가 몇 개인지 알아보려고 한다.

- 0P0 : 소수 양쪽에 0이 있는 경우

- P0 : 소수 오른쪽에만 0이 있고, 왼쪽에는 아무것도 없는 경우

- 0P : 소수 왼쪽에만 0이 있고, 오른쪽에는 아무것도 없는 경우

- P : 소수 양쪽에 아무것도 없는 경우

예를 들어, 437674을 3진수로 바꾸면 211020101011이다.

소수는 211, 2, 11이므로 총 3개이다. 이때, 중복되는 원소에 대해서는 중복으로 세어준다.

2. 코드

(1) 1차 시도

def conversion(n, k):
    res = []
    
    while n > 0:
        res.append(str(n % k))
        
        n = n // k
    return ''.join(list(reversed(res)))

def is_prime(n):
    if n == 1:
        return False
    
    for i in range(2, n):
        if n % i == 0:
            return False
    
    return True
        
def solution(n, k):
    res = conversion(n, k)
    candidates = res.split('0')
    primes = 0
    
    for candidate in set(candidates):
        try:
            if is_prime(int(candidate)) == True:
                primes += candidates.count(candidate)
        except ValueError:
            continue
    
    return primes

(2) 2차 시도

def conversion(n, k):
    if k == 10:
        return str(n)
    
    res = ''
    
    while n > 0:
        n, mod = divmod(n, k)
        res += str(mod)
    
    return res[::-1]

def is_prime(n):
    if n == 1:
        return False
    
    for i in range(2, int(n ** (1/2)+1)):
        if n % i == 0:
            return False
    
    return True
        
def solution(n, k):
    res = conversion(n, k).split('0')

    primes = 0
    
    for candidate in set(res):
        try:
            prime_or_not = is_prime(int(candidate))
            
            if prime_or_not == True:
                   primes += res.count(candidate)
                   
        except ValueError:
            continue
        
    return primes

3. 설명

첫번째 시도 때에는 시간 초과가 발생해서, 최대한 줄일 수 있는 부분을 찾아서 고쳤다.

(1) conversion 함수

- 진수 변환에서 10진수인 경우에는 그대로 반환하기

- 진수 변환에서 직접 mod 연산과 몫 연산을 하기 보다는 divmod 함수 사용하기

- 리스트를 revered, join 하지 말고 string 타입으로 반환 시에는 [::-1]을 사용하여 역순으로 만들기

(2) is_prime 함수

- n까지 모두 다 검토하지 말고, n의 제곱근까지만 검토하기

(3) 동일한 코드

- 진수 변환한 문자열에 대해서 0을 기준으로 split 하기

- split한 문자열을 미리 정수로 바꾸지 말고, try ~ except를 사용해서 int로 바꿀 수 없는 문자열 (예. '')인 경우는 continue 해주기

- 동일한 문자가 존재할 수 있기 때문에 set을 사용해서 한번씩만 검토하되, count로 동일한 원소 개수를 정답에 더해주기

1. 문제 설명

여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는데, 규칙은 다음과 같다.

- 숫자를 0부터 시작해서 차례대로 말한다. 첫번째 사람은 0, 두번째 사람은 1, ... 열번째 사람은 9를 말한다.

- 10 이상의 숫자부터는 한 자리씩 끊어서 말한다. 즉, 열한 번째 사람은 10의 첫 자라인 1, 열 두번째 사람은 둘째 자리인 0을 말한다.

이렇게 게임을 진행할 경우,

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, ...

순으로 숫자를 말하면 된다.

이진법에서 십육진법까지 모든 진법으로 게임을 진행하기로 했다.

예를 들어 이집수로 게임을 진행한다면,

0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, ...

순으로 숫자를 말하면 된다.

2. 입출력 형식

- 입력 : 진법 n, 미리 구할 숫자의 개수 t, 게임에 참가하는 인원 m, 튜브의 순서 p

- 출력 : 튜브가 말해야 하는 숫자 t개를 공백 없이 차례대로 나타낸 문자열. 단, 10 ~ 15는 각각 대문자 A ~ F로 출력한다.

3. 코드

def jinbub(num, jinsu):
    jin = ' 0'

    for i in range(1, num+1):
        changed = []

        while i != 0:
            left = i % jinsu

            if left >= 10:
                if left == 10:
                    left = 'A'
                elif left == 11:
                    left = 'B'
                elif left == 12:
                    left = 'C'
                elif left == 13:
                    left = 'D'
                elif left == 14:
                    left = 'E'
                elif left == 15:
                    left = 'F'

            changed.append(str(left))
            i = i // jinsu

        temp = ''.join(list(reversed(changed)))
        jin += temp
        
    return jin
    
def solution(n, t, m, p):
    jin_str = jinbub(t*m, n)
    
    i = 1
    answer = ''
    
    if m == p: p = 0
    
    while len(answer) < t:
        if i % m == p:
            answer += jin_str[i]
        i += 1
    
    
    return answer

4. 설명

(1) jinbub(num, jinsu)

미리 숫자들을 진법으로 변환시켜두어야 하는데, 몇 개를 미리 만들어둘지가 고민 되었다.

jin_str = jinbub(t * m, n)

이렇게 최대 (말해야 하는 숫자의 개수) * (참가하는 인원) 만큼 진법 변환 결과를 구해두고,

함수에서 반환 받아서 말해야 하는 순서에 맞게 문자열에 추가만 해주도록 한다.

Python에서 제공하는 진법 변환 함수는 bin(), oct(), hex()로 2, 8, 16진수 변환만을 제공한다. 따라서 이 문제에서는 3진법, 4진법 등 다양하게 요구하므로 직접! 구현해주어야 한다.

몫과 나머지를 각각 구해가면서 하나씩 배열에 나머지들을 저장한다. (만약 10 이상의 나머지일 경우, 해당하는 문자로 바꾸기)

그리고 그 배열을 reverse 해서 순서를 바꿔주고 문자열로 (join) 만들어준다.

이때, 나는 공백을 두고 0으로 초기화 ( jin = ' 0' ) 했는데, 그 이유는 게임에서 말하는 순서가 0번째부터가 아니라 1번째부터이기 때문이다.

(2) solution(n, t, m, p)

진법 변환 함수 호출해서 문자열을 받아 오고, 말해야 하는 숫자의 개수가 채워질 때까지 while문을 반복한다.

인덱스 1부터 시작하고, 만약 3명의 인원에서 3번째 순서인 경우 몫과 나머지로 차례를 판단하기 어렵기 때문에, 미리 m == p 일때 p=0으로 만들어주었다.

하나씩 더한 문자들의 문자열을 반환하면 끝!

1. 문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려고 한다.

전화번호가 다음과 같은 경우, 구조대 전화번호는 영석이의 전화번호의 접두사이다.

- 구조대 : 119

- 박준영 : 97674223

- 지영석 : 1195524421

전화번호부에 적힌 전화번호를 담은 배열 phone_book이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 반환하라.

2. 코드

(1) 1차 코드 - 효율성 테스트 3, 4 실패 (시간 초과)

def solution(phone_book):
    phone_book = sorted(phone_book, key=len)

    for phone in phone_book:
        temp = phone_book.copy()
        temp.remove(phone)

        for t in temp:
            n = len(phone)
            
            if phone == t[:n]:
                return False
    return True

def solution(phone_book):
    phone_book = sorted(phone_book, key=len)

    for i, phone in enumerate(phone_book):
        
        for j, t in enumerate(phone_book):
            n = len(phone)
            
            if j != i:
                if phone == t[:n]:
                    return False
    return True

(2) zip, startswith 사용한 코드

def solution(phone_book):
    phone_book = sorted(phone_book)

    for p1, p2 in zip(phone_book, phone_book[1:]):
        if p2.startswith(p1):
            return False
    return True

(3) Hash Map 사용한 코드

def solution(phone_book):
    hash_map = {}

    for phone_number in phone_book:
        hash_map[phone_number] = 1

    for phone_number in phone_book:
        temp = ""

        for number in phone_number:
            temp += number
            
            if temp in hash_map and temp != phone_number:
                return False
    return True

3. 설명

(1) 1차 코드

- 전화 번호 길이를 기준으로 배열을 sorting하고, phone_book에 있는 전화 번호 하나씩 검토하면서 t[:n]과 배열의 전화번호가 일치하는지 비교한다.

- 아무래도 sorting 후에 2중 for문을 해서 그런지, 시간 초과가 계속 떴다.

(2) zip, startswith 사용한 코드

- 숫자로 되어 있는 문자열을 sorting하면, 왼쪽에서부터 크기 순서대로 배열된다.

예를 들어, ['119', '9767423', '1195524421']은 ['119', '1195524421', '97674223'] 이렇게 정렬된다.

- 따라서, zip(phone_book, phone_book[1:])로 그 다음 원소와 비교하면서 다음 원소가 이전 원소로 시작되는지 startswith()로 검토한다.

(3) Hash Map 사용한 코드

- 우선 Hash Map을 사용한 이유는, 리스트보다 원소의 존재를 파악하는데 더 낮은 복잡도를 가지고 있기 때문이다. (O(1))

- 전화번호를 hash_map에 key값으로 다 저장해둔다.

- 짧은 문자열 통째로 긴 문자열의 앞쪽과 비교하는 것이 아니라, 긴 문자열의 앞쪽부터 하나씩 temp에 더해가며 짧은 문자열과 동일한 요소가 있는지 확인하는 방식이다.

(나는 문자열 통째로를 긴 문자열의 앞쪽과 비교할 생각만 했어서.. 관점의 변화를 확 느낄 수 있었던 코드였다.)

- 원소의 개수를 파악하기 위해서도 Hash map이 사용되지만, 특정 원소의 존재를 확인하는데 빠른 속도를 가지고 있다는 장점으로 다양한 문제에서도 활용 가능하다고 생각한다!

1. 문제 설명

유사한 기사를 묶는 기준으로 "자카드 유사도"라는 방법을 채택했다.

자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있는데, 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.

이러한 자카드 유사도를 원소의 중복을 허용하는 다중집합에 대해서 확장한다.

- 예1)

다중집합 A는 원소 1을 3개 가지고 있고 (A = {1, 1, 1}), 다중집합 B는 원소 1을 5개 가지고 있다 (B = {1, 1, 1, 1, 1}). 이 다중집합의 교집합은 원소 1을 min(3, 5)인 3개, 합집합은 원소 1을 max(3, 5)인 5개 가지게 된다.

- 예2)

다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, 교집합은 {1, 2, 2}, 합집합은 {1, 1, 2, 2, 3, 4, 5}이므로 자카드 유사도는 3/7이다.

이를 문자열을 두 글자씩 끊어서 다중집합으로 만든 것에 응용하고자 한다.

- 예)

문자열 "France"와 "French"가 주어졌을 때, 이를 두 글자씩 끊어서 다중 집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로 자카드 유사도는 2/8이다.

2. 입력 형식

- 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. "AB"와 "Ab", "ab"는 같은 원소로 취급한다.

- 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 "ab+"가 입력으로 들어오면, "ab"만 다중집합의 원소로 삼고, "b+"는 버린다.

3. 코드

(1) Counter 사용하기

from collections import Counter

def solution(str1, str2):
	# 문자열 소문자로 변경
    str1 = str1.lower()
    str2 = str2.lower()
    
    arr1 = []
    arr2 = []
    
    # 특수문자 들어가지 않은 문자열만 취급하기
    for i in range(len(str1)-1):
        if str1[i:i+2].isalpha():
            arr1.append(str1[i:i+2])
    for i in range(len(str2)-1):
        if str2[i:i+2].isalpha():
            arr2.append(str2[i:i+2])
    
    # 중복 원소 고려를 위해 Counter 사용
    arr1_counter = Counter(arr1)
    arr2_counter = Counter(arr2)
    
    # 합집합, 교집합 구하기
    hab = list((Counter1 & Counter2).elements())
    kyo = list((Counter1 | Counter2).elements())
	
    # 집합 A, B가 모둔 공집합일 경우 J(A, B) = 1
    if len(union) == 0 and len(inter) == 0:
        return 65536
    else:
        return int(len(inter) / len(union) * 65536)

(2) 다중 집합 사용하기

def solution(str1, str2):
	# 문자열 소문자로 변경
    str1 = str1.lower()
    str2 = str2.lower()
    
    arr1 = []
    arr2 = []
    
    # 특수문자 들어가지 않은 문자열만 취급하기
    for i in range(len(str1)-1):
        if str1[i:i+2].isalpha():
            arr1.append(str1[i:i+2])
    for i in range(len(str2)-1):
        if str2[i:i+2].isalpha():
            arr2.append(str2[i:i+2])
    
    # 다중 집합 구하기
    arr1_result = arr1.copy() # 합집합
    intersection = [] # 교집합

    for i in arr2:
        if i in arr1:
            arr1.remove(i)
            intersection.append(i)
        else:
            arr1_result.append(i)
    
    if len(arr1_result) == 0 and len(intersection) == 0:
    	return 65536
    else:
    	return int(len(intersection) / len(arr1_result) * 65536)

4. 해설

(0) 공통

- 대문자와 소문자 구분이 없도록 string.lower() 함수로 문자열을 소문자로 변경해준다.

- 두 글자씩 끊어서 원소로 만들 때 영문자로 된 글자 쌍만 유효하도록 string.isalpha() 함수로 검토한다.

(1) Counter 사용하기

- 중복된 원소를 고려하기 위해서 원소의 개수를 Counter로 구한다.

- Counter는 '|', '&' 연산이 가능하다. 이때, 핵심은 Counter.elements()이다.

Counter.keys()를 하면 중복된 값이 존재해도 중복 없이 unique한 값이 반환된다. 따라서, elements()를 통해 중복된 개수만큼을 리스트로 저장한다.

(2) 다중 집합 사용하기

- 일반적인 Python의 집합은 중복 원소를 허용하지 않는다. 하지만, 다중 집합은 중복된 원소를 포함하기 때문에 실제로는 리스트에 저장하여 나타낸다.

- 마치 Sorting에서 stable sorting이 있고, unstable sorting이 있는 것처럼 생각하면 쉽다! 같은 '1'이지만 '1_a', '1_b'가 있는 것으로 생각하는 것이다.

- 다중집합에서 교집합과 합집합을 구하는 방법은 다음과 같다.

a = [1,2,2,3,4,5]
b = [1,1,2,3,4,6]

a_temp = a.copy()
a_result = a.copy()

for i in b:
	if i not in a_temp:
    		a_result.append(i)
      	else:
        	a_temp.remove(i)

a_temp는 a - b (차집합)이 되고, a_result는 합집합이 된다.

교집합은 a_result에서 a_temp 원소를 뺀 원소들이 된다.

a_temp가 필요한 이유는, a에서 remove 해버리면 원본 데이터가 손실되기 때문이다.

이 문제에서는 이후에 arr1이 필요하지 않아서 바로 arr1에서 remove를 한 것이다.

arr1_result = arr1.copy() # 합집합
intersection = [] # 교집합

for i in arr2:
    if i in arr1:
        arr1.remove(i)
        intersection.append(i)
    else:
        arr1_result.append(i)

reference : https://velog.io/@munang/%EA%B0%9C%EB%85%90%EC%A0%95%EB%A6%AC-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%8B%A4%EC%A4%91-%EC%A7%91%ED%95%A9

1. 문제 설명

어떤 게임은 일정 피로도를 사용하여 던전을 탐험할 수 있다.

이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있다.

- 최소 필요 피로도 : 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도

- 소모 피로도 : 던전을 탐험한 후 소모되는 피로도

예를 들어 '최소 필요 피로도'가 80, '소모 피로도'가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모된다.

하루에 한 번씩 탐험할 수 있는 던전이 있을 때, 한 유저가 오늘 최대한 많이 탐험하려고 할 때, 유저가 탐험할 수 있는 최대 던전 수를 반환하라.

2. 제한 사항

- k는 1 이상 5,000 이하인 자연수

- dungeons의 각 행은 각 던전의 ['최소 필요 피로도', '소모 피로도'] 이다.

3. 코드

(1) 완전 탐색 - DFS

answer = 0

def explore(power, cnt, is_visited, dungeons):
	global answer
	if cnt > answer:
    	answer = cnt
        
        for i in range(len(dungeons)):
            if power >= dungeons[i][0] and is_visited[i] == False:
                is_visited[i] = True
                explore(power - dungeons[i][1], cnt + 1, is_visited, dungeons)
                is_visited[i] = False

def solution(k, dungeons):
	global answer
        is_visited = [ False for _ in range(len(dungeons)) ]

        explore(k, 0, is_visited, dungeons)

        return answer

(2) 순열

from itertools import permutations

def solution(k, dungeons):
	answer = 0
    
        for pemutation in permutations(dungeons, len(dungeons)):
            power = k
            cnt = 0

            for need, spend in permutation:
                if power >= need:
                    power -= spend
                    cnt += 1
                else:
                    break

            answer = max(answer, cnt)

        return answer

4. 해설

(1) 완전 탐색 - DFS

깊이 우선 탐색 방식으로 모든 경우를 따져준다.

전역 변수 answer를 선언하여, 던전의 최대 탐험 개수를 갱신했을 때 answer 값을 바꿔준다.

이미 지나온 던전인지를 저장하는 is_visited 배열을 만들어주고 DFS를 수행하는 함수인 explore를 호출한다.

explore 함수는

- 전역 변수 answer보다 탐험한 던전의 개수가 더 많을 경우 갱신을 해준다.

- 던전의 경우를 for문으로 모두 검토하면서 방문하지 않았는지, 방문할 수 있는지 (최소 필요 피로도를 만족하는지) 확인하여 재귀적 호출을 진행한다.

- 핵심은 호출 이후로 is_visited[i] = False로 만들어주어, 다음 경우에는 다시 방문할 수 있도록 하는 것이다.

(2) 순열

from itertools import permutations를 통해서 가능한 모든 경우의 수를 구한다.

- for permutation in permutations(dungeons, len(dungeons))

예시 :

([80, 20], [50, 40], [30, 10])
([80, 20], [30, 10], [50, 40])
([50, 40], [80, 20], [30, 10])
([50, 40], [30, 10], [80, 20])
([30, 10], [80, 20], [50, 40])
([30, 10], [50, 40], [80, 20]))

1. 문제 설명

셀 수 있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플 (tuple)이라고 한다. n개의 요소를 가진 튜플을 n-tuple이라고 한다.

튜플은 다음과 같은 성질을 가지고 있다.

- 중복된 원소가 있을 수 있다. (예. (2, 3, 1, 2))

- 원소에 정해진 순서가 있으며, 원소의 순서가 다르면 서로 다른 튜플이다. (예. (1, 2, 3) ≠ (1, 3, 2))

- 튜플의 원소 개수는 유한하다.

(a1, a2, a3, ..., an)이 주어질 때, 집합 기호를 통해 다음과 같이 나타낼 수 있다.

- {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ... , an}

예를 들어 튜플이 (2, 1, 3, 4)인 경우 이는

- {{2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4}}

- {{2, 1, 3, 4}, {2}, {2, 1, 3}, {2, 1}}

- {{1, 2, 3}, {2, 1}, {1, 2, 4, 3}, {2}}

이렇게 다양하게 표현이 가능하다.

특정 튜플을 표현하는 집합이 담긴 문자열 s가 매개변수로 주어질 때, s가 표현하는 튜플을 배열에 담아 반환하도록 하라.

2. 제한 사항

- s의 길이는 5 이상 1,000,000 이하이다.

- s는 숫자와 '{', '}', ','로만 이루어져 있다.

- 숫자가 0으로 시작하는 경우는 없다.

3. 코드

def solution(s):
    s1 = s.lstrip('}').rstrip('{').split('},{')
    s2 = []
    
    # 각 원소로 이루어진 배열을 삽입
    for i in s1:
        if '{{' in i:
            i = i.lstrip('{{')
        if '}}' in i:
            i = i.rstrip('}}')
            
        s2.append(i.split(','))
    
    # 원소의 길이를 기준으로 배열 정렬
    s3 = []
    for tuple in sorted(s2, key=len):
        for t in tuple:
        	
            # 배열에 존재하지 않는 경우 순서대로 추가
            if t not in s3:
                s3.append(t)
    
    return list(map(int, s3))

4. 해설

집합 형태의 s가 문자열로 들어왔고, 이를 원소 하나하나씩 떼어주는 작업이 필요하다.

- 문자열 맨 앞의 { 와 맨 뒤의 }를 제거해준다.

(예시 결과 : {2}, {2, 1}, {2, 1, 3}, {2, 1, 3, 4})

- '},{'를 기준으로 split 해준다.

(예시 결과 : ['{{2', '2, 1', '2, 1, 3', '2, 1, 3, 4}}'])

떼어낸 문자열을 원소 하나씩으로 분리해준다.

- 원소에 {{ 가 있거나 }} 가 있는 경우, 제거해준다.

(예시 결과 : ['2', '2, 1', '2, 1, 3', '2, 1, 3, 4']

- ','를 기준으로 split 해준다.

(예시 결과 : [['2'], ['2', '1'], ['2', '1', '3'], ['2', '1', '3', '4']]

각 배열 요소들을 짧은 길이 순서대로 sorting 해주고, 정답 배열에 존재하지 않는 경우에 원소를 추가한다.

- sorted(s2, key=len) : key에 정렬 기준 함수를 적어주면 되는데, python 내장 함수인 len을 적어주었다.

1. 문제 설명

지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.

이때, 데이터베이스에 캐시를 적용하여 성능 개선을 시도하고 있지만, 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하라.

2. 입력 형식

- 캐시 크기 (cacheSize)와 도시이름 배열 (cities)을 입력받는다.

- cacheSize는 수이며, 범위는 0  ≦ cacheSize ≦ 30 이다.

- 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다.

3. 출력 형식

- 입력된 도시 이름 배열을 순서대로 처리할 때, '총 실행시간'을 출력한다.

4. 조건

- 캐시 교체 알고리즘은 LRU (Least Recently Used)를 사용한다.

- Cache hit일 경우 실행시간은 1이다.

- Cache miss일 경우 실행시간은 5이다.

5. 코드

def solution(cacheSize, cities):
	# 대소문자 구별하지 않도록 소문자로 만들어주기
    cities = [c.lower() for c in cities]
    
    # 캐시 사이즈가 0인 경우 전부 Cache miss로 간주
    if cacheSize == 0:
        return len(cities) * 5
    
    # { 도시 이름 : 참조 시간 } 저장할 딕셔너리 선언
    cache = dict()
    total = 0
	
    
    for c in cities:
        if len(cache) < cacheSize:
            if c not in cache.keys():
                total += 5
            else:
                total += 1
        else:
            if c not in cache.keys():
                total += 5
                
                # 가장 value가 큰 요소를 제거
                max_time = -1
                max_key = c
                for city, time in cache.items():
                    if max_time < time:
                        max_key = city
                        max_time = time

                del cache[max_key]

            else:
                total += 1
        
        # 공통적으로 c 아닌 도시들에 +1, c 도시에 0 부여
        cache = { city : time+1 for city, time in cache.items()}
        cache[c] = 0
        
    return total

6. 해설

https://tech.kakao.com/posts/344

카카오 기술 블로그에 나와있는 예시 설명이다.

놓칠 수 있는 포인트가

1. 대소문자 구별하지 않는다는 점 : lower case로 다 변환해주기

2. cacheSize로 0이 들어올 수 있다는 점 : 전부 cache miss로 간주하여 도시 개수 * 5 해주기

3. 단순히 가장 예전에 cache에 들어왔다고 해서 cache에서 제거해야 할 대상은 아니라는 점 : '참조 시간'의 문제임

캐시에 cacheSize만큼 저장되지 않은 경우,

중복 체크만 해주고 이미 있는 도시에 대해 value + 1, 새로 들어온 도시에 대해 0으로 만들어 준다.

캐시에 cacheSize만큼 저장되어 있는 경우에는,

가장 참조 시간이 긴 도시를 제거하고 새로 들어온 도시를 참조시간 0으로 하여 추가해준다. 역시 이미 있는 도시에 대해서는 value + 1을 해준다.

1. 문제 설명

코니는 매일 다른 옷을 조합하여 입는데, 각 종류별로 최대 1가지 의상만 착용할 수 있다.

예를 들어, 위의 경우 동그란 안경과 검정 선글라스 중 하나를 착용할 수 있지만 둘 다 착용할 수는 없다.

코니는 하루에 최소 한 개의 의상은 입는다.

코니가 가진 의상들이 담긴 2차원 배열이 주어질 때 서로 다른 옷의 조합의 수를 반환한다.

2. 제한 조건

- 2차원 배열은 [의상의 이름, 의상의 종류]로 이루어져 있다.

- 같은 이름을 가진 의상은 존재하지 않는다.

3. 코드

from collections import Counter

def solution(clothes):
    closet = Counter([sort for name, sort in clothes])
    
    answer = 1
    for sort, num in closet.items():
        answer *= (num + 1)
    
    return answer - 1

4. 해설

from collections import Counter는 매우 유용한 함수이다. 리스트에서 종류와 개수에 대해 dictionary를 만들 때 사용하면 좋다.

이 문제에서 특별하게 사용된 것은 [ sort for name, sort in clothes ] 이다.

sort를 기준으로 개수를 구해주도록 하여, sort에 대한 중복 확인, 개수 체크를 할 필요가 없어서 유용하다.

각 sort 별로 하나씩 입거나 입지 않은 경우를 고려하여 num + 1을 해주었다.

그리고 그 경우의 수를 다 곱하여 모든 경우의 수를 구하는데, 이때 정답은 -1을 해주어야 한다.

아무것도 입지 않은 경우는 제외해주어야 하기 때문이다.

1. 문제 설명

행렬 arr1, arr2가 주어지면, 두 행렬의 곱셈을 반환한다.

2. 제한 조건

- 행렬의 행과 열의 길이는 2 이상 100 이하이다.

- 행렬의 원소는 -10 이상 20 이하인 자연수이다.

- 곱할 수 있는 배열만 주어진다.

3. 코드

def solution(arr1, arr2):
    answer = []
    
    row1 = len(arr1)
    row2 = len(arr2)
    col2 = len(arr2[0])
    
    for i in range(row1):
        element = []
        
        for j in range(col2):
            res = 0
            
            for k in range(row2):
                res += arr1[i][k] * arr2[k][j]
                
            element.append(res)
        answer.append(element)
    
    return answer

4. 해설

우선 행렬의 곱셈은 시간 복잡도가 O(n^3)인 것은 알려져있는 사실이기 때문에, for문 3개를 사용해야겠다는 생각을 하게 되었다.

이렇게 for문이 여러 개 있을 때 많이 헷갈리는데, 나는 가장 바쁘게 변하는 것과 그렇지 않은 것으로 나눠서 생각한다.

행렬의 곱에서 가장 느리게 변화하는 것은 arr1의 행 인덱스이다.

그 다음으로 느리게 변화하는 것은 arr2의 열 인덱스이다.

가장 빠르게 변화하는 것은 arr1의 열 인덱스이자, arr2의 행 인덱스이다.

따라서 가장 바깥쪽 for문은 arr1의 행 길이 (len(arr1)),

그 다음 for문은 arr1의 열 길이 또는 arr2의 행 길이 (len(arr1[0]) 또는 len(arr2))

가장 안쪽 for문은 arr2의 열 길이이다.