1. 문제 - 카카오 18년 기출 3번

• 지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.
  • 이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.
  • 어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.
  • 어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.
• 입력 형식
  • 캐시 크기(cacheSize)와 도시 이름 배열(cities)을 입력받는다.
  • cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30이다.
  • cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
  • 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.
• 출력 형식
  • 입력된 도시 이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.
• 조건
  • 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
  • cache hit일 경우 실행시간은 1이다.
  • cache miss일 경우 실행시간은 5이다.

2. 풀이 - 데크(Deque) 이용

1) 데크 자료형 구현

일반적으로 이중 연결 리스트로 구현된 데크(Deque) 자료형은 동적 배열로 이뤄진 파이썬 리스트보다 시간 효율성이 우수하다.

또한, deque 자료형은 매개변수 ‘maxlen’을 설정할 수 있어서 본 문제를 구현하는 데 적합하다.

예를 들어 캐시 사이즈(=maxlen)는 3이며 ‘a’, ‘b’, ‘c’, ‘d’가 차례대로 입력될 때,

데크에는 ‘a’, ‘b’, ‘c’가 우선 삽입되며, 최종적으로 ‘a’가 빠짐과 동시에 ‘d’가 삽입된다.

import collections

def solution(cacheSize, cities):

    cache = collections.deque(maxlen=cacheSize)

2) 캐시 히트

입력값으로 주어진 도시가 캐시에 이미 존재할 경우(캐시 히트), 실행시간(answer)에 1을 추가한다.

다만 캐시가 LRU로 구현되었기 때문에, 가장 오래전에서 사용된 캐시 값이 우선적으로 제거된다는 점을 주의해야 한다.

즉, 캐시 히트가 발생할 경우 해당 값은 데크의 가장 우측으로 위치 변경을 해야 한다.

아래 코드에서 remove() 함수를 이용하여 해당 값을 데크에서 제거한 후, append() 함수로 다시 추가하는 방식으로 구현했다.

import collections

def solution(cacheSize, cities):

    answer = 0
    cache collecdtions.deque(maxlen=cacheSize)

    for c in cities:

        # 소문자 처리
        c = c.lower()

        # 캐시 히트
        if c in cache:
            cache.remove(c)
            cache.append(c)

            answer += 1

3) 캐시 미스

입력값으로 주어진 도시가 캐시에 존재하지 않을 경우(캐시 미스), 실행 시간(answer)은 5만큼 증가한다.

캐시 미스가 일어난 도시는 새로이 캐시에 추가한다.

앞서 설명한 대로 데크가 가득 찬 상황에서 새로운 값이 추가되면, 가장 오래전에 삽입된 값이 데크에서 우선적으로 제거된다.

전체 코드는 아래와 같다.

import collections

def solution(cacheSize, cities):
    answer = 0

    cache = collections.deque(maxlen=cacheSize)

    for c in cities:

        # 소문자 처리
        c = c.lower()

        # 1. 캐시 히트
        if c in cache:

            # 캐시 추출 후 재삽입
            cache.remove(c)
            cache.append(c)

            answer += 1

        # 2. 캐시 미스
        else:
            cache.append(c)
            answer += 5


    return answer

‘파이썬 알고리즘 인터뷰(박상길, 책만)’ 참조

1. 문제 - (카카오 18년 기출) - 다트 게임

• 카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다. 갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다.
  • 다트 게임은 총 3번의 기회로 구성된다.
  • 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
  • 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수1 , 점수2 , 점수3 )으로 계산된다.
  • 옵션으로 스타상() , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
  • 스타상()은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다. (예제 4번 참고)
  • 스타상()의 효과는 다른 스타상()의 효과와 중첩될 수 있다. 이 경우 중첩된 스타상() 점수는 4배가 된다. (예제 4번 참고)
  • 스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다. (예제 5번 참고)
  • Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.
  • 스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.
  • 0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.
  

2. 풀이 - 문자열 처리

1) 정수 처리

문자열을 처리하는 문제다.

다트를 던지는 횟수(3번)만큼 덧셈이 이뤄지므로, 총 세개의 점수가 더해지는 셈이다.

리스트를 생성하여 세개의 점수를 삽입하고 sum()함수로 그 답을 구하는 구조로 전체를 구성한다.

문자열(dartResult)을 대상으로 for 반복문을 실행하여 개별 문자열 하나하나를 추출한다.

추출한 문자열(s)가 정수일 경우, 미리 만든 리스트(nums)에 해당 문자열의 정수값(int(s))을 입력하는 방식이다.

정수값 앞에 ‘ nums[-1] * 10 ’이 더해진 이유는 10점이 입력값으로 들어오는 경우 때문이다.

다트 점수가 10점일 경우, for문의 문자열 처리 과정에서 각 자리 숫자가 개별적으로(‘1’ → ‘0’) 처리된다.

따라서 일의 자리 수 ‘0’을 처리할 때, 십의 자리수 ‘1’에 대한 자릿수 올림을 계산해야 한다.

nums = [0]

for s in dartResult:
  if s.isdigit():  # s가 정수일 때
    nums[-1] = nums[-1] * 10 + int(s)

2) 연산식 처리

거듭제곱 연산(Single, Double, Triple)과 곱셉(스타상 및 아차상)을 처리한다.

거듭제곱 연산은 1제곱, 2제곱, 3제곱을 처리한다.

스타상은 방금 던진 다트의 점수와 이전에 던진 다트의 점수에 ‘2’를 곱하고,

아차상은 방금 던진 다트 점수에 ‘-1’을 곱한다.

리스트에 들어있는 정수 값에 각각의 연산을 적용시키면 된다.

주의할 점으로 스타상의 경우 2차례 시행을 대상으로 ‘x2’처리를 해야하며,(#1)

스타상이 맨 첫 시행에서 발생할 경우에 대한 예외 조건을 설정해야 한다. (#2)

전체 코드는 아래와 같다.

def solution(dartResult):
    answer = 0

    nums = [0]

    for s in dartResult:
        if s == 'S':
            nums[-1] **= 1
            nums.append(0)

        elif s == 'D':
            nums[-1] **= 2
            nums.append(0)

        elif s == 'T':
            nums[-1] **= 3
            nums.append(0)

        # 1. 이전 값과 그 이전 값 모두 2배 처리    
        elif s == '*':
            nums[-2] *= 2

            #2. 아차상이 맨 처음 시행에서 발생할 경우 
            if len(nums) > 2:
                nums[-3] *= 2

        elif s == '#':
            nums[-2] *= (-1)

        # 자릿수 올림: 입력값으로 10이 들어온 경우, 문자열 '1'과 '0'을 나누어 처리    
        else:
            nums[-1] = nums[-1] * 10 + int(s)


    return sum(nums)

'파이썬 알고리즘 인터뷰(박상길, 책만)' 참조

1. 문제 - 비밀 지도

• 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.
  • 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다.
  • 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
  • "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다.
  • 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.
  

- 입력: 
  - n = 5
  - arr1    [9, 20, 28, 18, 11]
  - arr2    [30, 1, 21, 17, 28]
- 출력    ["#####","# # #", "### #", "# ##", "#####"]

2. 풀이 - 이진수 OR 연산

1) OR 연산

비트 연산자 OR를 이용하여 이진수를 계산하는 문제다.

두 개의 지도를 합칠 때, 둘 중 하나라도 벽(’#)이면 벽(’#)이 나오고,

둘 중 모두가 공백(” “) 일 경우에 공백(” “)이 나온다.

‘이진수 1’을 벽(’#’)으로, ‘이진수 0’을 공백(” “)으로 치환하면 된다.

하나의 지도가 10100(2), 다른 지도가 00001(2)라고 할 때,

두 이진수를 OR(|) 연산하면 10101(2)이 된다. 각 자릿수를 계산해보면 쉽게 이해가 될 것이다.

for i in range(len(arr1):
    bin_or = bin(arr1[i] | arr2[i])[2:].zfill(len(arr1))

bin() 매서드를 사용해서 십진수를 이진수로 바꾸면 문자열 타입이 출력된다.

또한 앞부분에 이진수임을 표시한 ‘0b’라는 문자가 같이 붙어서 출력된다.

예를 들어 ‘ bin(arr1[i] | arr2[i]) ‘를 입력하면,

'0b1111'이 출력되는 식이다.

앞에 ‘0b’를 제거하기 위해 슬라이싱( [2:])을 사용했다.

그리고 작은 숫자의 경우 OR연산 결과 5자리가 모두 채워지지 않을 수 있다.(ex. 1001(2))

따라서 지정된 자리수를 채우지 못할 경우 앞에 0을 넣어주는 zfill() 함수를 사용하여 자릿수를 맞춰준다.

2) 문자열 변환 및 정답 출력

answer = []

for i in range(len(arr1):
    bin_or = bin(arr[i] | arr[i])[2:].zfill(len(arr1))

    answer.append(bin_or.replace('0', ' ').replace('1', '#')

replace(’바꾸기 전’, ‘바꾼 후’) 함수를 활용하여 ‘0’을 공백(’ ‘)으로 ‘1’을 ‘#’으로 바꿔준다.

그런 다음 정답 리스트에 추가를 해주면 최종 답이 완성된다.

전체 코드는 아래와 같다.

3) 전체 코드

def solution(n, arr1, arr2):
    answer = []

    for i in range(len(arr1)):
        or_bin = bin(arr1[i] | arr2[i])[2:].zfill(len(arr1))
        answer.append(or_bin.replace('0', ' ').replace('1', '#'))

    return answer

| '파이썬 알고리즘 인터뷰(박상길, 책만)' 참조

1. 문제 - 코스 스케줄(리트코드 207)

- 문제: 0을 완료하기 위해서는 1을 끝내야 한다는 것을 [0,1], 쌍으로 표현하는 n개의 코스가 있다. 코스 개수 n과 이 쌍들을 입력으로 받았을 때 모든 코스가 완료 가능한지 판별하라
    - Input: numCourses = 2, prerequisites = [[1,0]]
    - Output: true

선행 수강해야하는 과목(prerequisites)을 고려했을 때, 특정 개수(numCourse)의 수업을 모두 들을 수 있는지 여부를 판단하는 문제다.

위 예시에서 ‘numCourses = 2’이므로 2개의 수업을 들어야 된다.

‘prerequisites = [[1,0]]’ 조건에서 1번 수업을 듣기 위해서는 0번 수업을 먼저 수강해야 한다.

즉 위의 경우는 수업을 들을 수 있으므로 ‘참’이다.

하지만 만약 조건이 numCourses = 2, prerequisites = [[1,0], [0,1]]이라고 한다면,

1번 수업을 듣기 위해 0번 수업을 먼저 들어야 하고, 동시에 0번 수업을 듣기 위해 1번 수업을 사전에 들어야 하므로, ‘거짓'이 된다.

2. 풀이 - DFS로 순환구조 판별

이 문제는 순환 구조 여부를 판단해야 한다.

a강의를 듣기 위해 b강의를 먼저 수강해야 하고,

b강의를 듣기 위해 a강의를 먼저 수강해야 한다면,

a와 b가 서로 연결되는 구조가 만들어지며,

순환구조로 구성될 경우 ‘False’를 리턴한다.

1) 그래프 생성

graph = collections.defaultdict(list)

for a, b in prerequisites:
    graph[a].append(b)

우선 입력값으로 주어진 수강 순서(변수 prerequisites)를 그래프 형태로 바꿔준다.

defaultdict 자료형을 이용하며, 도식화하면 아래와 같다.

2) 순환구조 판단

이미 방문했던 경로는 ‘traced’ 변수에 저장하고,

재귀 호출을 진행하면서 해당 경로가 ‘traced 변수'에 존재할 경우(중복일 경우) False를 리턴하는 구조다.(#3)

우선 그래프에 키값(a)을 대상으로 for 반복문을 실행하고, dfs 함수를 호출한다.(#1)

키에 속한 경로들을 나타내는 value(b) 대상으로 for 반복문을 실행하고, 재귀 함수를 호출한다.(#2)

경로 탐색을 마친 후 해당 경로는 ‘traced’에서 삭제한다.(# 4)

만약 삭제를 하지 않으면 for 문이 실행되는 과정에서 부모가 아닌 형제 노드가 방문한 경로를 중복 경로로 판단할 수 있기 때문이다.

이 과정을 통해 순환 경로의 존재 여부를 판단한다.

traced = set()  # 3-1

def dfs(i):
    if i in traced:  #3-2
        return False

    set.add(i)

    # 2 
    for b in graph[i]: 
        if not dfs(b):
            return False
    # 4
    set.remove(i)

    return True

# 1
for a in list(graph):
    if not dfs(a):
        return False

3) 전체 코드

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        graph = collections.defaultdict(list)
        # 그래프 구성
        for x, y in prerequisites:
            graph[x].append(y)

        traced = set()

        def dfs(i):
            # 순환 구조이면 False
            if i in traced:
                return False

            traced.add(i)
            for y in graph[i]:
                if not dfs(y):
                    return False
            # 탐색 종료 후 순환 노드 삭제
            traced.remove(i)

            return True

        # 순환 구조 판별
        for x in list(graph):
            if not dfs(x):
                return False

        return True

| '파이썬 알고리즘 인터뷰(박상길, 책만)' 참조

1. 문제 - 일정 재구성(리트코드 332)

- 문제: [from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전 어휘 순(Lexical Order)로 방문한다.
  - Input: tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
  - Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]

티켓의 출발지와 도착지가 주어질 때, 가능한 여행 경로를 구하는 문제다.

만약 출발지에 도착지가 두개 이상이라면, 알파벳 순서가 빠른 곳으로 간다.

JFK에서 갈 수 있는 곳은 ‘SFO’와 ‘ATL’ 두 곳인데,

‘ATL’이 알파벳 순서가 빠르기 때문에 이곳을 먼저 방문한다.

따라서 JFK → ATL → JFK → SFO → ATL → SFO 순서대로 방문한다.

2. 풀이 - 재귀함수를 활용한 DFS 탐색

1) 그래프 만들기

이동 가능한 경로를 그래프로 나타내야 한다

출발점을 key로 도착 가능한 지역들을 value로 입력한 딕셔너리 형태로 구성한다.

# 그래프 사전식 순서대로 구성
        dict = collections.defaultdict(list)

        for a,b in sorted(tickets):
            dict[a].append(b)

코드를 살펴보면,

우선 ‘defaultdict’ 매서드로 빈 그래프(dict)를 만든다.

중요한 것은 도착 지점들이 알파벳 순으로 정렬돼야 한다는 점이다.

따라서 입력값(tickets)을 먼저 정렬하면 key의 문자열이 빠른 순으로 정렬되고, key가 같을 경우 value가 빠른 순으로 정렬된다.

그 후, 딕셔너리에 출발점을 key로, 도착지를 value로 입력한다면,

도착지는 알파벳 순으로 정렬되어 있을 것이다.

2) 재귀호출 및 dfs 탐색

‘JFK’에서 출발하여 도착 가능한 경로 중 알파벳이 빠른 곳에 먼저 방문한다.

앞서 도착지를 미리 정렬했기 때문에 도착지 리스트 중 맨 앞의 것을 추출(pop())하면 된다.

위 그림에서는 ‘ATL’이 첫 번째 도착지에 해당할 것이다.

추출한 값 ‘ATL’을 다시 입력값으로 넣어 재귀 함수를 호출하면,

이번에는 알파벳이 가장 앞선 도착지 ‘JFK’가 되고 해당 값을 추출하여 재귀 호출하는 과정을 반복한다.

마지막 지점까지 도착했다면, 마지막 지점부터 경로 리스트(route)에 차례대로 담는다.

route = []

      # value의 첫 번째 값을 읽어 어휘순 방문
      def dfs(a):
          while dict[a]:
              dfs(dict[a].pop(0))

          route.append(a)

      dfs('JFK')

3) 결과 출력 및 전체 코드

위와 같이 마지막 지점부터 경로 리스트에 담기면, 결국 경로가 거꾸로 저장된다.

따라서 최종 결과 값을 뒤집어서 알파벳 순서대로 다시 정렬한다. 전체 코드는 아래와 같다.

class Solution(object):
    def findItinerary(self, tickets):
        """
        :type tickets: List[List[str]]
        :rtype: List[str]
        """ 

        # 그래프 사전식 순서대로 구성
        dict = collections.defaultdict(list)

        for a,b in sorted(tickets):
            dict[a].append(b)

        route = []

        # value의 첫 번째 값을 읽어 어휘순 방문
        def dfs(a):
            while dict[a]:
                dfs(dict[a].pop(0))

            route.append(a)

        dfs('JFK')

        # 다시 뒤집어서 어휘순 결과대로 리턴
        return route[::-1]

'파이썬 알고리즘 인터뷰(박상길, 책만)' 참조

1. 문제 - 조합의 합(리트코드 39)

- 문제: 숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라. 각 원소는 중복으로 나열 가능하다. 
  - Input: candidates = [2,3,6,7], target = 7
  - Output: [[2,2,3],[7]]

배열(candidates)의 요소를 더해서 특정 수(target)를 만드는 문제다.

중복해서 수를 뽑을 수 있다는 점이 중요한 조건이다.

위 예를 보면 2, 3, 6, 7 중에서 임의로 숫자를 뽑아 더한 다음 7을 만든다.

‘2+2+3 = 7 ‘과 ‘7 = 7’ 두 가지 경우의 수가 발생하므로,

정답은 [ [2, 2, 3] , [7] ] 이 된다.

2. 풀이 - DFS로 그래프 탐색

1)

풀이 과정의 일부를 도식화 하면 위 그림과 같다.

숫자 2부터 경로를 찾아나간다.

다음 경로의 후보로 ‘자기 자신 + 뒤에 나열된 수’가 된다.

2의 경우 [2, 3, 4, 5]이고,

3의 경우 [3, 4, 5]가 될 것이다.

2)

위 과정을 재귀함수로 구현한다.

csum은 구하고자 하는 값(target)에서 탐색한 경로의 값의 차이다.

예를 들어, 맨 처름 숫자 2를 선택했으면, 앞으로 ‘7-2 = 5’만큼을 더 찾아야 한다.

‘index’는 ‘자기자신 + 뒤에 나열된 수’의 순서를 나타낸다.

마지막으로 ‘path’는 지나온 경로를 담고 있으며, 정답을 충족할 경우 ‘result’ 변수에 담기게 된다.

3)

위의 예에서, 2를 총 네번 선택하는 경로를 선택(7-2-2-2-2 = -1)한다면,

값이 1만큼 초과하여 오답이 되어 해당 경로는 탐색이 종료된다.

이번에 2를 세 번 선택할 경우를 살펴보면,

‘7-2-2-2 =1 ‘로 값이 1만큼 부족하기 때문에 오답이 된다.

인덱스를 1만큼 증가시켜서 ‘2’ 세 번, ‘3’ 한 번을 탐색할 경우

‘7-2-2-3 = 0’으로 정답에 해당하며, ‘result’ 변수에 담긴다.

이처럼 경로의 값들을 더했을 때 원하는 값(target)을 초과할 경우, 탐색을 종료한다.

경로의 합이 원하는 값과 일치할 경우, 해당 경로를 정답 리스트에 추가한다.

3. 전체 코드

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """

        result = []

        def dfs(csum, index, path):

            # 종료 조건
            if csum < 0:
                return

            elif csum == 0:
                result.append(path)
                return 

            # 자신부터 하위 원소까지의 나열 재귀 호출
            for i in range(index, len(candidates)):
                dfs(csum-candidates[i], i, path + [candidates[i]])


        dfs(target, 0, [])

        return result

'파이썬 알고리즘 인터뷰(박상길, 책만)' 참조

1. 문제 - 이진트리 직렬화 & 역직렬화(리트코드 297)

- 문제: 이진 트리를 배열로 직렬화하고, 반대로 역직렬화하는 기능을 구현하라.
    - Input: root = [1,2,3,null,null,4,5]
    - Output: [1,2,3,null,null,4,5]

직렬화(Serialize)는 논리적 구조인 이진트리를 파일이나 메모리에 저장하기 위해 배열구조로 바꾸는 것을 말하며 반대는 과정은 역직렬화(Deserialize)라고 한다.

본 문제는 이진트리를 배열로 바꾸는 직렬화 함수와 배열을 이진트리로 바꾸는 역직렬화 함수 모두를 구현하는 것이다.

2. 풀이

1) 직렬화

1-1

우선, 이진 트리를 배열화 한 모습을 도식화하면 위와 같다.

노드 레벨 구분의 편의를 위해 인덱스를 1부터 시작했다. 인덱스 1, 2, 4, 8, … 순서로 앞 수에 곱하기 2를 하면 노드 레벨의 시작 위치를 구분할 수 있기 때문이다.

이진트리를 배열로 바꾸기 위해 너비 우선 탐색 방식(BFS)을 사용한다.

우선, 리스트 보다 시간 효율적인 데크 자료형으로 ‘큐'를 생성한다.

그리고 배열을 담을 리스트(result)를 만들어 주는데, 앞 서 말했듯이 인덱스가 1부터 시작하기 때문에 ‘#’ 하나를 미리 채워놓았다.

파이썬의 경우 None값을 string 형태로 출력할 수 없기 때문에 ‘#’를 이용하여 None을 표현했다.

def serialize(self, root):
    queue = collections.deque([root])
    result = ['#']

1-2

while 반복문을 통해 큐(queue)에서 노드를 하나씩 추출한 다음, 해당 노드의 자식 노드를 다시 큐에 삽입하는 과정을 반복한다.

추출된 부모 노드의 값을 결과를 담을 리스트(result)에 추가하되, 빈 노드의 경우 ‘#’를 추가한다.

최종 값을 하나의 문자열로 출력해야 하기 때문에 리스트(result)의 요소들을 join() 함수를 이용하여 통합한다.

def serialize(self, root):
    queue = collections.deque([root])
    result = ['#']

    # 트리 BFS 직렬화
    while queue:
        node = queue.popleft()

        if node:
            queue.append(node.left)
            queue.append(node.right)

            result.append(str(node.val))

        else:
            result.append('#')

    return ' '.join(result)

2) 역직렬화

2 - 1

직렬화 과정에서 join() 함수로 통합했던 배열을 split() 함수로 분할한 후 ‘nodes’ 변수에 담아준다.

루트 노드(root)를 생성하고, 해당 노드를 큐에 삽입한다.

인덱스 변수에 정수 2를 할당하는데, 루트 노드의 왼쪽 자식 노드가 인덱스 2에 위치하기 때문이다.

# 역직렬화
    def deserialize(self, data):

        # 예외 처리 
        if data == '# #':
            return None

        nodes = data.split()
        root = TreeNode(nodes[1])
        queue = collections.deque([root])

        index = 2

2 - 2

while 반복문을 통해 부모 노드를 큐에서 출력한 후, 자식 노드를 큐에 다시 삽입하는 과정을 반복한다.

이때 인덱스를 ‘+1’씩 증가시키며 부모 노드와 자식 노드를 연결한다.

자식 노드가 존재하지 않을 경우, queue에 추가하지 않음으로써 빈 노드를 처리한다.

while queue:

        node = queue.popleft()

    # 자식 노드 존재 시, 큐에 삽입
    if nodes[index] != '#':
        node.left = TreeNode(int(nodes[index]))
        queue.append(node.left)
    index += 1

    if nodes[index] != '#':
        node.right = TreeNode(int(nodes[index]))
        queue.append(node.right)
    index += 1

3) 전체 코드

class Codec:
    # 직렬화
    def serialize(self, root):

        queue = collections.deque([root])
        result = ['#']

        # 트리 BFS 직렬화
        while queue:
            node = queue.popleft()

            if node:
                queue.append(node.left)
                queue.append(node.right)

                result.append(str(node.val))

            else:
                result.append('#')

        return ' '.join(result)



    # 역직렬화
    def deserialize(self, data):

        # 예외 처리 
        if data == '# #':
            return None

        nodes = data.split()
        root = TreeNode(nodes[1])
        queue = collections.deque([root])

        index = 2

        while queue:

            node = queue.popleft()

            # 자식 노드 존재 시, 큐에 삽입
            if nodes[index] != '#':
                node.left = TreeNode(int(nodes[index]))
                queue.append(node.left)
            index += 1

            if nodes[index] != '#':
                node.right = TreeNode(int(nodes[index]))
                queue.append(node.right)
            index += 1

        return root

‘파이썬 알고리즘 인터뷰(박상길, 책만)’ 참조

1. 문제 - 상위 K 빈도 요소(리트코드 347)

- 문제: 상위 k번 이상 등장하는 요소를 출력하라

  - Input: nums = [1,1,1,2,2,3], k = 2
  - Output: [1,2]

입력값으로 주어진 리스트에서 동일한 요소가 가장 많은 값 순서대로 k개를 출력하는 문제다.

예시로 주어진 리스트에서 엘리먼트 ‘1’, ‘2’, ‘3’은 각각 3개, 2개, 1개가 있다.

개수가 많은 순서대로 2개(k=2)를 출력하면 ‘1’과 ‘2’가 출력된다.

2. 풀이 - 파이썬 모듈 활용

‘우선순위 큐’를 이용하여 엘리먼트의 빈도수 순서대로 정렬하는 방식이 일반적인 풀이일 것이다.

하지만 파이썬 모듈을 활용한 간결한 풀이 방법을 사용하려 한다.

우선 전체 코드는 아래와 같다.

짧은 코드이지만 다양한 기능을 함축하고 있다.

def topKFrequent(self, nums, k):

    return list(zip(*collections.Counter(nums).most_common(k)))[0]

1) collections.Counter()

코드를 세분화 하여 살펴보자.

우선 collections.Counter()모듈은 엘리먼트(key)와 그 개수(value)를 튜플 형태로 반환한다.

2) most_common(k)

most_common(k) 매서드르 활용하면 value값이 큰 순서대로 k개를 반환한다.

3) zip()

zip() 함수는 서로 다른 튜플 내 요소들을 인덱스에 맞게 짝지어 튜플로 반환한다.

>>> a = (1, 2)
>>> b = (3, 4)
>>> list(zip(a,b))

[**(1,3), (2, 4)]**

하지만 ‘zip(collections.Counter(nums).most_common(k))’를 실행해보면 위의 예시와 다른 방식으로 출력된다. 엘리먼트끼리 짝지어지는 것이 아니라, 하나로 묶인 엘리먼트와 빈 값이 짝지어진다.

4) 아스테리스크(*)

아스테리스크(*)는 시퀀스를 언팩(Unpack)하는 연산자다. 위 예시에서 튜플로 묶인 엘리먼트를 언팩한 후 zip() 함수를 적용하면 우리가 원하는 형태의 값을 얻을 수 있다.

5) 인덱싱

우리는 개수가 가장 많은 엘리먼트 k개(1과 2)를 리스트에 담아서 출력하고자 한다. 따라서 인덱싱으로 리스트의 첫 번째 요소를 출력하면 최종 답을 구할 수 있다.