새싹프로그래머의 이야기

[풀이 방법]

• 그래프 탐색을 통해 무인도를 탐색해준다.
• 리스트 내의 값들이 string 형태이므로 list로 변환하여 사용하면 더 편하다.
• 탐색 함수 안에서 조건문을 통해 list의 Index를 벗어나지 않도록 설정해준다.
• 파이썬은 재귀함수의 깊이를 제한하므로 반복문을 통해 문제를 해결하거나, sys함수를 통해 깊이를 늘려줘야한다.

*이러한 문제 종류들을 만날 때, 항상 많이 헤메었었다. 리스트 내의 값을 확인 해야할 때는 '그래프 탐색'을 먼저 떠올릴 수 있으면 좋을 것 같다.

[풀이 코드]

import sys

sys.setrecursionlimit(1000000)


def search(maps, row, column, visited, value):
    if (row, column) in visited or 0 > row or row > len(maps) - 1 or column < 0 or column > len(maps[0]) - 1 or \
            maps[row][column] == 'X':
        return value
    value += int(maps[row][column])
    visited.append((row, column))
    value = search(maps, row - 1, column, visited, value)
    value = search(maps, row + 1, column, visited, value)
    value = search(maps, row, column - 1, visited, value)
    value = search(maps, row, column + 1, visited, value)

    return value


def solution(maps):
    answer = []
    visited = []
    maps = [list(Amap) for Amap in maps]
    value = 0

    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == 'X' or (i, j) in visited:
                continue
            answer.append(search(maps, i, j, visited, value))

    return sorted(answer) if answer else [-1]

[풀이 방법]

• List로 귤의 크기가 주어졌을 때, 최소한의 귤의 종류로 판매하고 싶은 갯 수를 채워야 하므로 Counter 함수를 통해 귤 크기 별로 갯 수를 구해준다.
• 최소한의 종류로 판매하고자 하는 갯 수를 채우기 위해서는 갯 수가 많이 들어있는 크기의 귤을 활용하여 채워줘야 한다. 따라서, Counter의 most_common() 함수를 통해 정렬하여 문제 조건을 만족하는 귤 종류의 갯 수를 구한다.

[풀이 코드]

from collections import Counter


def solution(k, tangerine):
    answer = 0
    dic = Counter(tangerine)

    for i in dic.most_common():
        answer += 1
        k -= i[1]
        if k <= 0:
            break

    return answer

[풀이 방법]

• 시간을 다루는 문제이므로, 'HH:MM' 형태로 주어진 시간을 분 단위로 통일하여 활용한다.
• 이전 사람의 종료 시간과 현재 사람의 시작시간을 비교하여, 종료시간 + 10분(청소 시간) 보다 시작시간이 뒤에 있을 경우 기존의 방을 배정하고 아닐 경우 새로운 방을 배정한다.

[풀이 코드]

import heapq


def solution(book_time):
    answer = 0
    heap = []
    bt = [(int(s[:2]) * 60 + int(s[3:]), int(e[:2]) * 60 + int(e[3:])) for s, e in book_time]
    bt.sort()

    for s, e in bt:
        if not heap:
            heapq.heappush(heap, e + 10)
            continue

        if heap[0] <= s:
            heapq.heappop(heap)
        else:
            answer += 1

        heapq.heappush(heap, e + 10)

    return answer + 1

문제: cache 사이즈와 문자열 리스트가 주어졌을 때, 캐시 교체에 드는 총 실행시간을 구하는 문제입니다.

풀이 코드:

from collections import deque


def solution(cacheSize, cities):
    answer = 0
    q = deque(maxlen=cacheSize)

    for i in cities:
        i = i.lower()
        if i in q:
            q.remove(i)
            q.append(i)
            answer += 1
        else:
            q.append(i)
            answer += 5
    return answer

문제 풀이:

문제 풀이의 핵심은 maxlen 옵션을 활용한 deque 사용입니다.

문제에서 캐시 교체 알고리즘은 LRU 알고리즘을 활용한다고 명시해주었습니다.

예를 들면, 길이가 3인 ['a', 'b', 'c'] 라는 리스트에 'd' 라는 원소가 추가된다면 'a'라는 원소가 없어지고 'd'가 추가되는 것입니다.

deque의 maxlen 옵션을 활용한다면 위와 같이 동일하게 동작하는 deque를 구현할 수 있습니다.

from collections import deque

q = deque(maxlen=3)

for i in range(6):
    q.append(i)
    print(q)

위와 같은 코드가 있을 때, 데크에 담기는 원소를 확인해보면 다음과 같습니다.

따라서, 문제 풀이는 maxlen이 정의된 deque를 통해 풀어주었습니다. 

def solution(cacheSize, cities):
    answer = 0
    q = deque(maxlen=cacheSize)

    for i in cities:
        i = i.lower()
        if i in q:
            q.remove(i)
            q.append(i)
            answer += 1
        else:
            q.append(i)
            answer += 5
    return answer

maxlen이 설정된 deque에 append 할 경우, LRU 알고리즘과 맞게 동작하므로 원소가 있는지 여부만 판단하여 실행시간을 구해주었습니다.(원소가 있을 경우, 'cache hit'. 없을 경우, 'cache miss'.)

* 해당 문제는 https://www.youtube.com/watch?v=orf9ailzXvI 을 듣고 작성하였습니다.

문제: 문자열이 주어졌을 때, 문제에서 주어진 방식으로 압축 시킬 수 있는 모든 방법중에서 가장 짧은 문자열의 길이를 구하는 문제입니다.

풀이 코드:

def solution(s):
    answer = 0
    length = len(s)
    lst = [[] for _ in range((length - 1) // 2 + 2)]
    string = ''
    l = 1

    while l <= (length - 1) // 2 + 1:
        strlst = [s[i:i + l] for i in range(0, len(s), l)]  # 1부터 (length - 1) // 2 + 1까지 길이에 맞춰 문자열 쪼개기
        pos = strlst[0]
        cnt = 0
        for i in range(len(strlst)):
            if strlst[i] == pos:    # 앞선 문자열과 동일한 문자열이 들어온다면 갯수를 count하며 추가
                cnt += 1
                string += strlst[i]
            else:
                if cnt > 1:     # 앞선 문자열과 다른 문자열이 들어온다면 문자열 압축 및 새로운 문자열 추가
                    string = string.replace(pos * cnt, '{}{}'.format(cnt, pos))
                cnt = 1
                string += strlst[i]
                pos = strlst[i]

            if i == len(strlst) - 1:    # 동일한 문자가 반복되며 종료될 경우에 대한 처리 진행
                if cnt > 1:
                    string = string.replace(pos * cnt, '{}{}'.format(cnt, pos))

        lst[l] = list(string)
        string = ''
        cnt = 1
        l += 1
    answer = 1001

    for i in lst[1:]:
        if len(i) < answer:
            answer = len(i)

    return answer

풀이 방법:

• 첫번째는 문자열이 있을 때, 앞에서 부터 문자열 길이의 반 이상으로 쪼갠다면 중복되는 것이 생길 수 없으므로 범위를 (문자열 길이 -1)//2 +1 로 정의했습니다.

-> 'abcdefg' 를 'abcde' 'fg'로 쪼갠다면 앞의 문자열에 중복되는 문자열이 뒤에 나올 수 없습니다.

• 두번째로는, 쪼개진 문자열을 앞에서 부터 탐색하면서 다른 문자열이 나올 경우 앞선 문자열에 대한 압축과 동시에 새로 들어온 문자열을 추가해주었습니다.
• 마지막으로,동일한 문자('ababccc'에서 'c') 가 반복되며 종료될 경우를 위해 마지막 index에 대하여 처리하는 코드를 추가해주었습니다.

문제: 주어진 점수를 계산하여 성격유형 검사 결과 출력하기.

풀이 코드:

def solution(survey, choices):
    answer = ''
    dic1 = {'R': 0, 'T': 0, 'C': 0, 'F': 0, 'J': 0, 'M': 0, 'A': 0, 'N': 0}
    lst = 'RTCFJMAN'

    for string, score in list(zip(survey, choices)):
        if score == 4:
            continue
        elif score > 4:
            dic1[string[1]] += abs(score - 4)
        else:
            dic1[string[0]] += abs(score - 4)
    for i in range(0, len(lst), 2):
        if dic1[lst[i]] >= dic1[lst[i + 1]]:
            answer += lst[i]
        else:
            answer += lst[i + 1]

    return answer

풀이 설명:

성격 유형에 대한 점수를 확인하기 위해 다음과 같이 탐색을 해주었습니다.

또한, 탐색 결과를 바탕으로 문제 조건에 맞게 점수를 배분하였습니다.

• 4점 이상일 경우, 'RT'(예시)에서 T에 점수를 배정
• 4점 이하일 경우, 'RT'에서 R에 점수를 배정

for string, score in list(zip(survey, choices)):
    if score == 4:
        continue
    elif score > 4:
        dic1[string[1]] += abs(score - 4)
    else:
        dic1[string[0]] += abs(score - 4)

이후, 각 성격 유형에 대해 점수가 다 반영되면 각 카테고리 별로 강한 성향을 보이는 성격 유형을 answer에 담아주었습니다.

for i in range(0, len(lst), 2):
    if dic1[lst[i]] >= dic1[lst[i + 1]]:
        answer += lst[i]
    else:
        answer += lst[i + 1]

문제: LZW 압축

풀이 코드:

import string


def solution(msg):
    answer = []
    alphabet = list(string.ascii_uppercase)
    dic = {c: i + 1 for i, c in enumerate(alphabet)}
    pos = 27

    while msg:
        length = 1

        while msg[:length] in dic.keys() and length <= len(msg):
            length += 1
        if msg[:length] not in dic.keys():
            dic[msg[:length]] = pos
            pos += 1

        answer.append(dic[msg[:length - 1]])
        msg = msg[length - 1:]

    return answer

문제풀이:

alphabet = list(string.ascii_uppercase)
dic = {c: i + 1 for i, c in enumerate(alphabet)}

먼저, 알파벳에 대한 index가 필요하기 때문에 다음과 같이 enumerate 함수를 통해 딕셔너리 형태로 알파벳:index 형태로 저장해주었습니다.

while msg:
    length = 1

    while msg[:length] in dic.keys() and length <= len(msg):
        length += 1
    if msg[:length] not in dic.keys():
        dic[msg[:length]] = pos
        pos += 1

    answer.append(dic[msg[:length - 1]])
    msg = msg[length - 1:]

가장 핵심이 되는 코드는 문제 조건에 따라 다음과 같이 구현하였습니다.

• 문자열의 시작점으로부터 문자를 탐색하여 딕셔너리에 담긴 최대 길이의 문자열을 구합니다. 즉, 해당 문자열에 한 글자가 추가된다면 해당 문자열은 딕셔너리에 담기지 않은 문자열이 됩니다.
• 딕셔너리에 담기지 않는 문자열에 대해서는 새로운 index와 함께 딕셔너리에 추가해줍니다.
• 딕셔너리에 담긴 최대 길이 문자열에 대한 index를 answer 배열에 담습니다.

위 과정을 반복하여, 문자열을 압축합니다.

문제: 두 개의 문자열이 있을 때, 자카드 유사도를 구하는 문제입니다.

조건:

• 입력된 문자열을 두 글자씩 끊어서 다중집합의 원소로 만듭니다.
• 이때, 토큰화 된 문자열에 특수문자가 들어갈 경우 제외합니다.
• 대문자와 소문자의 차이는 무시합니다.

풀이 코드:

num = 65536


def solution(str1, str2):
    answer = 0

    dic1 = dict()
    dic2 = dict()

    ls1 = len(str1)
    ls2 = len(str2)
    
    for i in range(ls1 - 1):
        key = str1.lower()[i:i + 2]
        if key.isalpha():  # 특수문자 있을 경우 제외.
            if dic1.get(key):
                dic1[key] += 1
            else:
                dic1[key] = 1

    for i in range(ls2 - 1):
        key = str2.lower()[i:i + 2]
        if key.isalpha():  # 특수문자 있을 경우 제외.
            if dic2.get(key):
                dic2[key] += 1
            else:
                dic2[key] = 1

    # intersection
    int_val = 0
    for i in dic1.keys():
        if i in dic2.keys():
            int_val += min(dic1[i], dic2[i])
    # Union 구하기
    uni_val = 0
    for i in dic1.keys():
        if i in dic2.keys():
            uni_val += max(dic1[i], dic2[i])
            dic2.pop(i)
        else:
            uni_val += dic1[i]

    for i in dic2.keys():
        uni_val += dic2[i]

    if uni_val == 0:
        answer = num
    else:
        answer = int(int_val / uni_val * num)

    return answer

풀이 설명:

for i in range(ls1 - 1):
    key = str1.lower()[i:i + 2]
    if key.isalpha():  # 특수문자 있을 경우 제외.
        if dic1.get(key):
            dic1[key] += 1
        else:
            dic1[key] = 1

자카드 유사도의 경우, 다중집합의 경우 같은 문자열도 다른 원소로 취급하므로 개 수를 세기 위해 딕셔너리를 활용하였습니다.

또한, 특수문자가 포함된 문자열을 제거하기 위해 .isalpha() 함수를 활용하였습니다.

str1 = '112' str2 = '1212' 일 경우,

dic1 = { '11' : 1 , '12': 1}

dic2 = {'12': 2 , '21:': 1} 가 됩니다.

# intersection
int_val = 0
for i in dic1.keys():
    if i in dic2.keys():
        int_val += min(dic1[i], dic2[i])

교집합을 구하는 부분은 다음과 같습니다. 토큰화된 문자열에 대한 개 수를 담은 딕셔너리의 key 값을 통해 같은 key가 존재할 경우, 

교집합이기 때문에 최소값을 더해주었습니다.

위의 예시에서 str1에는 '12'가 1개 , str2에는 '12'가 2개 있을 때 교집합은 1개 인 것을 보면 이해에 도움이 되실 것 입니다.

# Union 구하기
uni_val = 0
for i in dic1.keys():
    if i in dic2.keys():
        uni_val += max(dic1[i], dic2[i])
        dic2.pop(i)
    else:
        uni_val += dic1[i]

for i in dic2.keys():
    uni_val += dic2[i]

합집합의 경우, 두 문자열에 모두 존재하는 원소일 경우 개 수의 최대 값을, dic1에만 존재할 경우 그 원소의 개 수를 더하도록 하였으며, 

교집합에 해당되는 원소에 대한 값을 반영하였을 경우, pop() 함수를 통해 dic2에서 제거를 해주었습니다.

그리고 아직 dic2에만 있는 원소에 대한 값을 반영하지 않았으므로, 반복문을 별도로 구성해 값을 반영하여 주었습니다.

문제를 풀고 나서 다른 코드들을 보니 엄청 깔끔하고 파이써닉하게 풀어낸 코드가 있어서 소개드리고 마무리 하도록 하겠습니다.

num = 65536

def solution(str1, str2):
    answer = 0

    token1 = [str1[i:i + 2].lower() for i in range(len(str1) - 1) if str1[i:i + 2].isalpha()]
    token2 = [str2[i:i + 2].lower() for i in range(len(str2) - 1) if str2[i:i + 2].isalpha()]

    intersect = set(token1) & set(token2)
    uni = set(token1) | set(token2)


    uni_val = sum(max(token1.count(i), token2.count(i)) for i in uni)
    intersect_val = sum(min(token1.count(i), token2.count(i)) for i in intersect)


    if uni_val == 0:
        answer = num
    else:
        answer = int(intersect_val/uni_val*num)
    return answer

다중집합의 원소의 개 수로 답을 구하는 문제이므로, set()과 count() 함수를 통해 깔끔하게 풀어낸 풀이가 있더라구요. 보면서 감탄만 나왔던 코드였습니다. 제가 앞으로 파이썬으로 알고리즘을 공부해가면서 나아가야할 방향을 보여주는 듯 했습니다.