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

👉 사용 언어 : PYTHON3

가장 많이 받은 선물

✅ Solution

from collections import defaultdict

def solution(friends, gifts):
    score = defaultdict(int)
    combi = defaultdict(int)

    for friend in friends:
        score[friend] = 0

    for record in gifts:
        giver, taker = record.split()
        combi[(giver, taker)] += 1
        score[giver] += 1
        score[taker] -= 1

    ans = -1
    for i in friends:
        temp = 0
        for j in friends:
            if i == j:
                continue
            if combi[(i, j)] > combi[(j, i)]:
                temp += 1
            if combi[(i, j)] == combi[(j, i)] and score[i] > score[j]:
                temp += 1
        ans = max(ans, temp)

    return ans

 

👉 아이디어

• score 딕셔너리를 사용하여 각 이름(key)에 0(value)을 맵핑한다.
• combi 딕셔너리를 사용하여 giver, taker 튜플(key)의 value에 +1씩 카운트한다.
• score 딕셔너리에서 giver에 해당하는 value에 +1, taker에 해당하는 value에 -1을 해준다.
• 중첩 for문 을 사용하여 한쌍씩 묶어서 비교한다.
  • 주고 받은 선물의 개수를 비교하여 i가 받을 선물 개수를 카운트한다.
  • 주고 받은 선물의 개수가 같을 경우, 선물 지수를 비교하여 i가 받을 선물 개수를 카운트한다.
• 이전 ans 값과 현재 카운팅 값을 비교하여 max 값으로 ans를 업데이트한다.
  • 다음달에 가장 선물을 많이 받는 사람의 선물 개수를 리턴해야 하므로!

 

✅ 딕셔너리 기본값 처리

 

- for 루프 안에 if  조건절을 통해서 counter 사전에 어떤 글자가 키(key)로 존재하지 않는 경우, 해당 키에 대한 기본값을 0으로 주기

def count_letters(word):
    counter = {}
    for letter in word:
        if letter not in counter:
            counter[letter] = 0
        counter[letter] += 1
    return counter

 

- dict.setdefault

 : 첫번째 인자로 키(key)값, 두번째 인자로 기본값(default value) 

def count_letters(word):
    counter = {}
    for letter in word:
        counter.setdefault(letter, 0)
        counter[letter] += 1
    return counter

 👉 for 루프 내에서 setdefault() 함수가 무조건적으로 항상 호출됨

 

- dict.get

 : 사전에 저장된 값을 접근할 때, 대괄호 대신에 get() 함수를 사용하면 두 번째 인자로 기본값을 명시 가능

 : if 조건절 없이도 사전의 기본값을 지정할 수 있다.

def count_letters(word):
    counter = {}
    for letter in word:
        counter[letter] = counter.get(letter, 0) + 1
    return counter

 

- collections.defaultdict

 : defaultdict 클래스의 생성자 로 기본값을 생성해주는 함수를 넘기면, 모든 키에 대해서 값이 없는 경우 자동으로 생성자의 인자로 넘어온 함수 를 호출하여 그 결과값으로 설정한다.

( KeyError를 출력하는 대신 정해져있는 기본 값을 기준으로 key값에 대한 딕셔너리의 요소를 생성해주는 기능)

from collections import defaultdict

def count_letters(word):
    counter = defaultdict(int) # defaultdict(lamda: 0)
    for letter in word:
        counter[letter] += 1
    return counter
    
count_letters("banana") # defaultdict(int, {'b': 1, 'a': 3, 'n': 2})

👉 생성자로 int 함수를 넘긴 이유는❓ int()는 0을 리턴하기 때문에❗

👉 int  함수 대신에 lambda: 0 를 넘겨도 동일하게 작동한다.

 

👉 깨달은 것 / 알게된 것

• 딕셔너리의 key 에 튜플 을 사용할 수 있다.
• 변경이 불가한지의 여부 > key로 사용 가능

두 큐 합 같게 만들기

✅ Solution

from collections import deque

def solution(queue1, queue2):
    ans = 0
    sum1 = sum(queue1)
    sum2 = sum(queue2)
    _sum = (sum(queue1) + sum(queue2)) / 2

    queue1 = deque(queue1)
    queue2 = deque(queue2)

    while sum1 != sum2:
        if not queue1 or not queue2 or _sum % 1 != 0 or ans == len(queue1)*2:
            ans = -1
            break
        if sum1 < _sum:
            num = queue2.popleft()
            sum2 -= num
            sum1 += num
            queue1.append(num)
        elif sum2 < _sum:
            num = queue1.popleft()
            sum1 -= num
            sum2 += num
            queue2.append(num)
        ans += 1
    return ans

 

👉 아이디어

• 큐의 양 끝에서의 삽입과 삭제가 O(1) 에 가능한 deque를 사용하여 성능을 향상시키기 위해 queue1과 queue2를 deque로 변환한다.
  • 기존 리스트(list) : 리스트의 맨 앞에서 요소를 추가하거나 제거할 때 리스트의 모든 요소를 한 칸씩 이동시켜야 하기 때문에 시간 복잡도가 O(n)이 된다.
  • deque 연산 메서드 : 기존 리스트의 메서드 기본 방향과 다르다.
    • append() / pop(): 기본적으로 큐의 맨 끝(오른쪽)에서 실행
    • popleft() 또는 appendleft() 등을 사용하여 큐의 맨 앞(왼쪽)에서 실행되도록 할 수 있다.
• while문 중단할 조건
  • 각각의 큐 합이 서로 같아졌거나
  • 2개의 큐 중 하나라도 비었거나
  • 2개의 큐 합이 홀수이거나
  • 최대 순회 가능 수 도달했을 경우 (= 한 바퀴 돌았을 경우)
• 테스트케이스 시간초과 발생 
  • [1, 4], [4, 8] > -1 케이스 추가해서 해결하기
  • sum()의 시간 복잡도는 O(n)이므로 반복문 내에서 사용하지 않는다.
  • 두 큐가 모든 원소를 바꿨을 때까지도 답이 안나오면 반복문을 중단해야한다. (무한루프 방지)
    • 현재 풀이에서는 ans == len(queue1) *2 일 경우!

 

✅ 다른 사람 풀이 참고

 

👉 비슷한 풀이

다만, 최대 순회 가능 수 제한 조건을 다르게 작성한 코드들이 많았다.

answer > 2*(len1+len2)

4 * len(queue1) + 1

answer <= 600000

4* len(q1)

...... 등등

 

👉 깨달은 것 / 알게된 것

• sum()을 여러 번 사용하는 것은 시간 복잡도 상 좋지 않다. 변수에 담아놓고 사용하는 방법을 권장한다.
• 리스트를 순회하는 것 또한 O(n)이므로 해당 문제와 유사한 알고리즘을 풀이하는 경우 deque를 사용하는 것이 좋다.