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

👉 사용 언어 : PYTHON3

크레인 인형뽑기 게임

✅ Solution

def solution(board, moves):
    answer = 0
    m = 0
    basket = []
    for i in moves:
        for j in range(0, len(board)):
            if board[j][i-1] != 0:
                basket.append(board[j][i-1])
                board[j][i-1] = 0
                break
    while m < len(basket) -1 and len(basket) > 1:
        if basket[m] == basket[m+1]:
            del basket[m:m+2]
            answer += 2
            m -= 1
        else:
            m += 1
    return answer

 

👉 아이디어

• 0 ~ n-1 중 board[n-1][?]가 맨 아래줄, board[0][?]가 맨 윗줄
• 중첩 for문을 돌려서 해당 moves 위치에서 맨 윗줄에 있는 인형을 뽑아 바구니에 넣는다.
  • moves 원소 는 1 ~ n 이므로 board의 index로 사용할 경우 -1을 해줘야한다는 점을 고려해야 한다.
  • 배열에서는 0이 인형이 없다는 의미이므로 0이 아닐 경우에만 바구니에 추가 후, 내부 for문을 중단한다. (시간 복잡도 ↓)
  • 0일 경우에는 인형이 있을때까지 계속 for문을 진행한다.
• 연속되는 원소를 확인하기 위해 while문을 돌린다.
  • 인덱스 범위를 고려하여 len(basket) -1 까지만!
  • 연속된 숫자(인형)가 존재하면 바구니에서 지운 후, +2 카운트한다.
  • 연속 숫자 2개 를 지운 후, 중복 체크에 영향을 받는 범위는 지운 첫 번째 숫자 앞자리까지이므로 m = m-1 로 재할당한다.
  • 연속 숫자가 없으면 계속 m = m+1 하면서 쭉쭉 체크!
• [12/5] Lv1. 풀이에서 햄버거 만들기 문제 풀이와 비슷

👉 주의해야할 점 _ 런타임에러 CASE

• 바구니에 인형이 안 들어있는 경우 또는 1개만 들어간 경우를 고려해야 한다.
• 즉, board에 인형이 1개만 존재하고 move 배열의 길이가 2 이상인 경우!
• 위의 코드에서는 while문 조건에 len(basket) > 1을 추가하여 해결하였다.

 

✅ 다른 사람 풀이 참고

def solution(board, moves):
    stacklist = []
    answer = 0

    for i in moves:
        for j in range(len(board)):
            if board[j][i-1] != 0:
                stacklist.append(board[j][i-1])
                board[j][i-1] = 0

                if len(stacklist) > 1:
                    if stacklist[-1] == stacklist[-2]:
                        stacklist.pop(-1)
                        stacklist.pop(-1)
                        answer += 2     
                break

    return answer

 

👉 깨달은 것 / 알게된 것

• 첫번째 중첩 반복문에서 모든 과정을 다 끝냄으로써, 밖에서 또 다른 반복문을 실행하지 않아도 된다.
  • 내가 풀이한 코드 : 바구니에 모두 담고 나서 다시 반복문을 돌려 중복되는 원소(인형) 삭제
  • 위의 코드 : 바구니에 담으면서 중복되는 원소(인형)을 만나면 바로 삭제
• [-1] : 스택리스트의 맨 위(끝) 원소 ,  [-2] : 스택리스트의 맨 위(끝)에서 2번째 원소

신고 결과 받기

✅ Solution

def solution(id_list, report, k):
    answer = {}
    user = []
    block_user = []
    report = list(set(report))
    for i in report:
        user.append(i.split(' ')[1])
    for j in id_list:
        answer[j] = 0
        if user.count(j) >= k:
            block_user.append(j)
    for k in report:
        if k.split(' ')[1] in block_user:
            answer[k.split(' ')[0]] += 1
    return list(answer.values())

 

👉 아이디어

• 위의 "가장 많이 받은 선물" 문제와 비슷한 유형인 것 같다.
• 한 사용자가 동일한 사용자를 여러 번 신고했을 경우, 1번의 신고만 count한다. (=중복체크)
  • "set( )" 사용 _ report = set(report)
• 경고 횟수가 k회 이상인 사용자를 block_user 리스트에 추가한다.
• report에서 반복문을 돌리며 신고받은 사용자가 block_user에 있는 사용자일 경우, 해당 사용자를 신고한 사용자 이름에 맵핑된 값에 +1을 한다.
• 정답 딕셔너리의 value을 리스트로 변환하여 반환한다.

👉 고민해봐야할 부분

• report의 중복 원소를 제거함으로써 순회할 경우의 시간 복잡도를 줄여주었지만
  • report 리스트 순회 2회
  • id_list 리스트 순회 1회
• 총 3번 순회함으로써 시간 복잡도상 효율적인 코드라고 보기는 어렵다.

 

✅ 다른 사람 풀이 참고

def solution(id_list, report, k):
    answer = [0] * len(id_list)    
    reports = {x : 0 for x in id_list}

    for r in set(report):
        reports[r.split()[1]] += 1

    for r in set(report):
        if reports[r.split()[1]] >= k:
            answer[id_list.index(r.split()[0])] += 1

    return answer

 

👉 깨달은 것 / 알게된 것

• {x : 0 for x in id_list} : 또 다른 배열의 원소를 key로, 0을 value로 가지는 딕셔너리 생성하는 방법
• 배열 1개 와 딕셔너리 1개 만으로 문제 풀이가 가능하다.
• 순회 횟수가 동일하게 3개이지만, 딕셔너리를 사용함으로써 신고받은 사용자를 배열에 넣고, 그 중 k번 이상 신고받은 사용자를 또 골라내어 배열에 넣는 과정이 빠짐으로써 더 효율적인 코드가 완성되었다.