새싹프로그래머의 이야기

[문제 풀이]

• 연산의 최소 횟수를 구해야하므로 bfs를 활용하였습니다.
• 이때 연산된 값은 y보다 같거나 작아야하며, 거리가 구해진 적이 없어야만 갱신해주었습니다.(거리가 구해졌는지 여부와 상관 없이 값을 구하면 최소 연산 횟수를 구할 수 없습니다.)

[풀이 코드]

from collections import deque


def solution(x, y, n):
    answer = 0
    dq = deque([x])
    distance = [0 for _ in range(1000001)]

    if x == y:
        return 0
    while dq:
        val = dq.popleft()

        if 1 <= val * 2 <= y and distance[val * 2] == 0:
            distance[val * 2] = distance[val] + 1
            dq.append(val * 2)
        if 1 <= val * 3 <= y and distance[val * 3] == 0:
            distance[val * 3] = distance[val] + 1
            dq.append(val * 3)
        if 1 <= val + n <= y and distance[val + n] == 0:
            distance[val + n] = distance[val] + 1
            dq.append(val + n)

    return distance[y] if distance[y] != 0 else -1

[풀이 방법]

• 틱택토에서 성립되지 않은 case를 찾았습니다.
  
  • 1. O가 완성 되었는데 X의 개수가 O의 개수와 같거나 더 많은 경우
  • 2. X가 완성 되었는데 O와 X의 개수가 다른 경우
  • 3. O와 X가 둘다 완성된 경우
  • 4. O의 갯수가 X의 개수보다 작거나 O의 개수가 X의 개수 + 1 보다 많은 경우
  • 이 문제에서 제일 시간을 많이 잡아먹은 경우는 4번 조건 이었습니다.  완성된 case가 없어도, O의 갯수는 항상 x의 개수와 같거나 더 많아야 하며, O의 개수가 X의 개수 + 1 보다 클 수 없습니다.
• 그런 다음, 주어진 배열을 탐색하면서 수직 / 수평 / 대각선으로 만들어질 수 있는 case를 모두 찾았습니다.

[풀이 코드]

def get_count(board):
    o = 0
    x = 0

    for i in board:
        o += i.count('O')
        x += i.count('X')

    return (o, x)


def get_game_set(board, o, x):
    horizontal = []
    vertical = [''] * 3
    diagonal = [''] * 2

    for i in range(len(board)):
        diagonal[0] += board[i][i]
        diagonal[1] += board[2 - i][i]

    for i in range(len(board)):
        for j in range(len(board)):
            vertical[j] += board[i][j]

    for line in board:
        if line[0] == line[1] and line[1] == line[2]:
            horizontal.append(line[0] * 3)

    fin = horizontal + vertical + diagonal

    if 'OOO' in fin and 'XXX' in fin:
        return 0
    elif ('XXX' in fin and o != x):  # "XXX"만 완성되면 O와 X의 갯수는 동일해야한다
        return 0
    elif ('OOO' in fin and x >= o):  # "OOO"만 완성되면 O의 갯수는 무조건 X의 갯수보다 많아야한다.
        return 0

    return 1


def solution(board):
    o, x = get_count(board)
    if o < x or o > x + 1:
        return 0

    return get_game_set(board, o, x)

[풀이 방법]

• 그래프 탐색 문제로 bfs 활용
• 경유지가 있으므로, (시작점에서 경유지까지의 최단거리 + 경유지에서 끝점까지의 최단거리)를 계산
• 미로를 탈출 할 수 없는 경우는 시작점에서부터 레버까지 도달하지 못하는 경우와 레버에서 끝점 까지 도달하지 못하는 경우가 있음

[풀이 코드]

from collections import deque


def search(r, c, maps, distance):
    visited = []
    direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    q = deque([(r, c)])

    while q:
        x, y = q.popleft()

        if (x, y) in visited:
            continue
        visited.append((x, y))
        for dx, dy in direction:
            nx, ny = x + dx, y + dy

            if nx < 0 or nx >= len(maps) or ny < 0 or ny >= len(maps[0]) or maps[nx][ny] == 'X' or (nx, ny) in visited:
                continue
            distance[nx][ny] = distance[x][y] + 1
            q.append((nx, ny))


def solution(maps):
    answer = 0
    maps = [list(line) for line in maps]
    distance = [[0] * len(maps[0]) for _ in range(len(maps))]
    sr, sc, lr, lc, er, ec = 0, 0, 0, 0, 0, 0

    for i in range(len(maps)):
        if 'S' in maps[i]:
            sr, sc = i, maps[i].index('S')
        if 'L' in maps[i]:
            lr, lc = i, maps[i].index('L')
        if 'E' in maps[i]:
            er, ec = i, maps[i].index('E')

    search(sr, sc, maps, distance)
    if distance[lr][lc] == 0:
        return -1

    answer += distance[lr][lc]
    distance = [[0] * len(maps[0]) for _ in range(len(maps))]
    search(lr, lc, maps, distance)
    if distance[er][ec] == 0:
        return -1
    return answer + distance[er][ec] 

[풀이 방법]

• 그래프 탐색을 통해 무인도를 탐색해준다.
• 리스트 내의 값들이 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 배열에 담습니다.

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