https://school.programmers.co.kr/learn/courses/30/lessons/131127

문제

입출력( + 추가적인 Test Case)

제한사항

풀이방법

유저의 쇼핑목록과 개수를 Counter class 로 구성합니다.

1일차부터 n, len(discount)-9 일까지의 각각의 카운터를 구성합니다.

만약 user_counter 와 mart_counter가 동일하다면 answer 을 1씩 더합니다.

마지막 answer을 반환합니다.

코드

from collections import Counter

def solution(want, number, discount):
    answer = 0
    user = dict()
    for i in zip(want,number):
        user[i[0]] = i[1]
    user_counter = Counter(user)
    for i in range(0,len(discount)-sum(number)+1):
        mart = Counter(discount[i:i+10])
        if user_counter == mart:
            answer += 1
    return answer

Collections 모듈에서의 Counter 객체

Counter은 객체를 계산하기 위한 dict의 하위 클래스 입니다. 요소는 dictionary의 키로 저장되며 그들의 갯수는 dictionary의 value 값으로 저장되는 collection입니다. value 값은 0 또는 음수를 포함해 모둔 '정수' 값이 될 수 있습니다.

참고링크

Counter 선언방법

선언하는 방법은 2가지가 있습니다.

collections 모듈에서 Counter을 불러오는 방식입니다.

from collections import Counter # 방법 1

counter1 = Counter()

collections 모듈을 모두 불러와 collections를 접두사로 사용하는 방식입니다.

import collections # 방법 2

counter2 = collections.Counter()

밑에 설명하는 코드들은 방법 1을 사용해서 선언하도록 하겠습니다.

리스트(List) 와 카운터(Counter)

a = ['aaa','ddd','aaa','ccc','aaa','ccc','bbb','aaa']

counter = Counter(a)
print(counter)
>>> Counter({'aaa': 4, 'ccc': 2, 'ddd': 1, 'bbb': 1})

Counter의 type은 dict입니다.

list를 Counter를 통해 선언한다면, 반환하는 type은 Counter객체이지만 Counter 안에 있는 type은 dict입니다.

출력은 value값의 순서대로 출력합니다.(내림차순) 하지만 value가 같은 경우 key는 내림차순이 아닙니다.

딕셔너리(dictionary)와 카운터(Counter)

a = {'k': 5, 's': 1, 'c': 4}

counter = Counter(a)
print(counter)
>>> Counter({'k': 5, 'c': 4, 's': 1})

dict를 Counter을 통해 선언한다면 value값의 내림차순으로 출력합니다.하지만 value가 같은 경우 key는 내림차순이 아닙니다.

문자열(String)과 카운터(Counter)

a = 'aasdfasdf'

counter = Counter(a)
print(counter)
>>> Counter({'a': 3, 's': 2, 'd': 2, 'f': 2})

위와 다르게 이번엔 문자열(String)을 카운터(Counter)에 넣어서 반환하는 방식을 구현했습니다.

문자열별로 얼마나 count되었는지 확인할 수 있습니다.

숫자(integer)와 카운터(Counter)

a = 323124

counter = Counter(a)
print(counter)

Traceback (most recent call last):
  File "/Users/hwangiljeong/PycharmProjects/pythonProject/main.py", line 6, in <module>
    counter = Counter(a)
              ^^^^^^^^^^
  File "/Library/Frameworks/Python.framework/Versions/3.11/lib/python3.11/collections/__init__.py", line 597, in __init__
    self.update(iterable, **kwds)
  File "/Library/Frameworks/Python.framework/Versions/3.11/lib/python3.11/collections/__init__.py", line 688, in update
    _count_elements(self, iterable)
TypeError: 'int' object is not iterable

정수는 오류가 not iterable 하기 때문에 오류가 발생합니다.

Counter의 함수들을 소개해보겠습니다.

element() 

c = Counter(a=4, b=2, c=0, d=-2)
print(sorted(c.elements())

>>> ['a', 'a', 'a', 'a', 'b', 'b']

개수만큼 반복되는 요소에 대한 이터레이터를 반환합니다. 요소는 처음 발견되는 순서대로 반환됩니다. 요소의 개수가 1보다 작으면 elements()는 이를 무시합니다.

most_common(n)

a = 'blogblogblogg'

counter = Counter(a)
print(counter.most_common())
>>> [('g', 4), ('b', 3), ('l', 3), ('o', 3)]

print(counter.most_common(2))
>>> [('g', 4), ('b', 3)]

n 개의 가장 흔한 요소와 그 개수를 가장 흔한 것부터 가장 적은 것 순으로 나열한 리스트를 반환합니다. 

n이 생략되거나 None이면, most_common()은 계수기의 모든 요소를 반환합니다. 개수가 같은 요소는 처음 발견된 순서를 유지합니다.

subtract()

c = Counter(a=4, b=2, c=0, d=-2)
d = Counter(a=1, b=2, c=3, d=4)
c.subtract(d)
# c의 counter - d의 counter 

print(c)
>>> Counter({'a': 3, 'b': 0, 'c': -3, 'd': -6})
# 각각의 요소를 뺀 값들을 출력

이터러블이나 다른 매핑 (또는 계수기)으로부터 온 요소들을 뺍니다. 입력과 출력 모두 0이나 음수일 수 있습니다.

Counter 활용방법

c = Counter('blogblogblogg')
c.total()                       # count의 총 개수
>>> 13

c = Counter('blogblogblogg')
c.clear()                       # 요소를 모두 제거
>>> None

c = Counter('blogblogblogg')
list(c)                         # 요소들을 list로 출렫하되 중복을 제거합니다.
>>> ['b', 'l', 'o', 'g']

c = Counter('blogblogblogg')
set(c)                          # set 형으로 변환합니다.
>>> {'b', 'o', 'g', 'l'}

c = Counter('blogblogblogg')
dict(c)                         # dictionary로 변환합니다.
>>> {'b': 3, 'l': 3, 'o': 3, 'g': 4}

c = Counter('blogblogblogg')
c.items()                       # (elem, cnt) 이러한 형태로 변환합니다.
>>> dict_items([('b', 3), ('l', 3), ('o', 3), ('g', 4)])

Counter 연산

c = Counter(a=3, b=1)
d = Counter(a=1, b=2)
print(c + d)                       # add two counters together:  c[x] + d[x]
>>> Counter({'a': 4, 'b': 3})
print(c - d)                       # subtract (keeping only positive counts)
>>> Counter({'a': 2})
print(c & d)                       # intersection:  min(c[x], d[x])
>>> Counter({'a': 1, 'b': 1})
print(c | d)                       # union:  max(c[x], d[x])
>>> Counter({'a': 3, 'b': 2})
print(c == d)                      # equality:  c[x] == d[x]
>>> False
print(c <= d)                      # inclusion:  c[x] <= d[x]
>>> False

https://www.acmicpc.net/problem/17069

문제 및 입출력 

풀이방법

처음의 파이프는 이와 같이 가로로 되어 있습니다. 

입력받은 N x N 의 DP행렬을 생성합니다. 각각의 행렬안에는 크기가 3인 배열이 있으며 각각 대각선, 세로, 가로입니다.

* 입력받은 행렬을 matrix로 표현합니다.

이후 DP[i][j]의 칸의 값을 구하는 방법은 다음과 같습니다.

(대각선)

matrix[i-1][j-1], matrix[i-1][j], matrix[i][j-1]의 칸이 모두 0인 경우 (모두 벽이 아닌 빈칸)

DP[i][j][0] = sum(DP[i-1][j-1])

(세로)

matrix[i-1][j-1] 이 0인 경우(벽이 아닌 빈칸)

현재칸의 세로 파이프 = 위칸에서의 대각선으로 들어온 파이프 + 위칸에서의 세로로 들어온 파이프

dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j][1]

(가로)

matrix[i-1][j-1] 이 0인 경우(벽이 아닌 빈칸)

현재칸의 가로 파이프 = 왼쪽칸에서의 대각선으로 들어온 파이프 + 왼쪽칸에서의 가로로 들어온 파이프

dp[i][j][2] = dp[i][j-1][0] + dp[i][j-1][2]

코드

import sys

# 입력
N = int(input())
matrix = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)]
# 대각선, 세로, 가로
dp = [[[0] * 3 for _ in range(N+1)] for __ in range(N+1)]
dp[1][2][2] = 1
for i in range(1,N+1):
    for j in range(3, N+1):
        if matrix[i-1][j-1] == 0:
            # 대각선
            if matrix[i-1][j-2] == 0 and matrix[i-2][j-1] == 0:
                dp[i][j][0] = sum(dp[i-1][j-1])
            # 세로
            dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j][1]
            # 가로
            dp[i][j][2] = dp[i][j-1][0] + dp[i][j-1][2]

print(sum(dp[N][N]))

결론

처음의 초기값을 잘 주는 것을 성공적으로해서 생각보다 빨리 풀 수 있었습니다.

마지막 DP배열을 증가시키는 과정에서 다른 방법을 쓰면 DP배열을 확장하지 않아도 될 것 같지만 코드의 가독성을 위해 썼습니다.

https://www.acmicpc.net/problem/15992

문제

입출력 보기

풀이방법

m = 수의 합, n = 사용한 수의 개수

왼쪽의 표를 보게 되면 형광색으로 칠한 것의 합이 빨간색 화살표로 가리킨 숫자와 같습니다.

그 이유는 오른쪽의 한 예시를 보면 알 수 있습니다. 

예시) f(4,2)에서  1 + 3, 2 + 2, 3 + 1 이렇게 3개의 숫자입니다. 이 숫자들은 각각 1, 2, 3에 3, 2, 1를 더한 것입니다.

이 예시를 통해 정리한 식은 우하단의 식과 같습니다.

f(m, n) = f(m-1, n-1) + f(m-2, n-1) + f(m-3, n-1) -> 각각의 수들에서 1, 2, 3을 더한 수들의 합이라고 보시면 됩니다. 

코드

import sys

input=sys.stdin.readline
MAX = 1001
MOD = 1_000_000_009

# 초기값 설정
dp = [[0] * MAX for _ in range(MAX)]
dp[1][1] = 1
dp[2][1], dp[2][2] = 1,1
dp[3][1], dp[3][2], dp[3][3] = 1, 2, 1

for i in range(4, MAX):
    for j in range(1, i + 1):
        dp[i][j] = (dp[i-1][j-1] + dp[i-2][j-1] + dp[i-3][j-1]) % MOD

# 출력
N = int(input())
for i in range(N):
    n, m = map(int, input().split())
    print(dp[n][m])

문제

입출력( + 추가적인 Test Case)

제한사항

풀이방법

1. 완호의 점수를 저장해놓습니다.

2. 점수를 근무 태도 점수는 내림차순, 동료 평가 점수는 오름차순으로 정렬합니다.

3. 현재 점수가 완호의 점수보다 모두 크다면 -1을 반환합니다.

4. limit > score[1]인 경우, incentive를 받지 못하는 사람이므로 다음 차례로 넘어갑니다.

5. limit <= score[1]인 경우, incentive를 받는 사람이므로 완호의 점수의 총합과 비교해서 등수를 계산합니다.

6. limit을 갱신합니다.

7. 비교가 끝나면 등수를 반환합니다.

* limit > score[1]일 때, incentive를 받지 못하는 이유에 대해 설명해보겠습니다.

limit은 이전 수들 중에서 가장 큰 동료 평가 점수(score[1])입니다.

현재 동료 평가 점수(socre[1])가 limit 보다 작다면, 동료의 인사고과 점수보다 낮은 것을 알 수 있습니다.

현재 근무 태도 점수(socre[0])은 내림차순입니다. 다시 말한다면, 이전 동료의 근무 태도 점수가 더 높다는 것입니다.

다시말해서, score[0], score[1] 모두 동료의 점수보다 낮다는 것을 알 수 있습니다.

코드

def solution(scores):
    answer = 1
    wanho_score = scores[0]
    sum_wanho_score = sum(scores[0])
    scores.sort(key=lambda x: (-x[0], x[1]))
    limit = 0

    for score in scores:
        sum_score = sum(score)
        if wanho_score[0] < score[0] and wanho_score[1] < score[1]:
            return -1

        # limit > score[1] 은 incentive를 받지 못하는 사람이다.
        if limit <= score[1]:

            # 성립한다는 것은 인센티브를 받는 것이므로 숫자를 계산해서 등수를 계산한다.
            if sum_wanho_score < sum_score:
                answer += 1
            limit = score[1]
    return answer

결론

처음에 문제를 잘못 해석해 시간이 오래 걸렸다. 10번 줄에 max(wanho_score) < min(score)인 경우로 계산했는데 이 것은 틀린 풀이이다. 두 값 중 min과 max를 구하는 것이 아닌 각각의 요소의 대소관계를 계산했어야 했다. 그 이후 오름차순과 내림차순을 떠올리지 못해서 다른 분들의 코드를 참고해서 문제를 풀었다. Level 3으로 와서 그런지 문제가 상당히 어렵다.

https://school.programmers.co.kr/learn/courses/30/lessons/160585

문제

입출력( + 추가적인 Test Case)

제한사항

풀이방법

틱택토가 성립이 안되는 경우가 있습니다.

1. 순서가 어긋난 경우

2. X가 성립되고 O를 놓는 경우

3. O가 성립되고 X를 놓는 경우

총 3가지가 있습니다.

1번의 경우

O의 개수는 cnt_o, X의 개수는 cnt_X 입니다.

cnt_x > cnt_o 의 경우

cnt_o > cnt_x + 1 의 경우 2가지 중 하나라도 성립되는 경우 오류입니다.

tic_o는 O가 성립된 경우, tic_x는 X가 성립된 경우 입니다.

2번의 경우

tic_x == 1 이면서 cnt_o > cnt_x 이면, X가 성립되고 O를 놓은 경우이므로 오류입니다.

3번의 경우

tic_o == 1 이면서 cnt_o == cnt_x 이면, O가 성립되고, X를 놓는 경우이므로 오류입니다.

총 3가지의 경우를 거치고 오류가 없다면 틱택토는 성립합니다.

코드

def tic_tac_toe(player, board):
    tic = 0

    for i in range(3):
        if all(player == cell for cell in board[i]):
            tic += 1

    for j in range(3):
        if all(player == board[i][j] for i in range(3)):
            tic += 1

    if all(board[i][i] == player for i in range(3)):
        tic += 1
    if all(board[i][2 - i] == player for i in range(3)):
        tic += 1

    return tic


def solution(board):
    board_list = [list(i) for i in board]

    # x, o 개수 세기
    cnt_x, cnt_o = 0, 0
    for i in range(3):
        for j in range(3):
            if board_list[i][j] == 'X':
                cnt_x += 1
            elif board_list[i][j] == 'O':
                cnt_o += 1
            else:
                continue

    # 순서가 어긋난 경우
    if cnt_x > cnt_o or cnt_o > cnt_x + 1:
        return 0
        
	# x와 o의 틱택토 성립하는지 확인
    tic_o = tic_tac_toe('O', board)
    tic_x = tic_tac_toe('X', board)

    # o 가 완성된 이후 x를 놓은 경우
    if tic_o == 1 and (cnt_x == cnt_o):
        return 0

    # x 가 완성된 이후 o를 놓은 경우
    if tic_x == 1 and (cnt_o > cnt_x):
        return 0

    return 1

all functions을 사용하지 않은 경우

def tic_tac_toe(board_list):
    tic_o = 0
    if board_list[0] == ['O', 'O', 'O'] or board_list[1] == ['O', 'O', 'O'] or board_list[2] == ['O', 'O', 'O']:
        tic_o += 1

    if board_list[0][0] == 'O' and board_list[1][0] == 'O' and board_list[2][0] == 'O':
        tic_o += 1
    elif board_list[0][1] == 'O' and board_list[1][1] == 'O' and board_list[2][1] == 'O':
        tic_o += 1
    elif board_list[0][2] == 'O' and board_list[1][2] == 'O' and board_list[2][2] == 'O':
        tic_o += 1

    if board_list[0][0] == 'O' and board_list[1][1] == 'O' and board_list[2][2] == 'O':
        tic_o += 1
    elif board_list[0][2] == 'O' and board_list[1][1] == 'O' and board_list[2][0] == 'O':
        tic_o += 1

    tic_x = 0
    if board_list[0] == ['X', 'X', 'X'] or board_list[1] == ['X', 'X', 'X'] or board_list[2] == ['X', 'X', 'X']:
        tic_x += 1

    if board_list[0][0] == 'X' and board_list[1][0] == 'X' and board_list[2][0] == 'X':
        tic_x += 1
    elif board_list[0][1] == 'X' and board_list[1][1] == 'X' and board_list[2][1] == 'X':
        tic_x += 1
    elif board_list[0][2] == 'X' and board_list[1][2] == 'X' and board_list[2][2] == 'X':
        tic_x += 1

    if board_list[0][0] == 'X' and board_list[1][1] == 'X' and board_list[2][2] == 'X':
        tic_x += 1
    elif board_list[0][2] == 'X' and board_list[1][1] == 'X' and board_list[2][0] == 'X':
        tic_x += 1

    return tic_o, tic_x


def solution(board):
    board_list = [list(i) for i in board]

    # x, o 개수 세기
    cnt_x, cnt_o = 0, 0
    for i in range(3):
        for j in range(3):
            if board_list[i][j] == 'X':
                cnt_x += 1
            elif board_list[i][j] == 'O':
                cnt_o += 1
            else:
                continue

    # 순서가 어긋난 경우
    if cnt_x > cnt_o or cnt_o > cnt_x + 1:
        return 0

    tic_o, tic_x = tic_tac_toe(board_list)

    # o 가 완성되었는데 x를 놓은 경우
    if tic_o == 1 and (cnt_x == cnt_o):
        return 0

    # x 가 완성되었는데 o를 놓은 경우
    if tic_x == 1 and (cnt_o > cnt_x):
        return 0

    answer = 1
    return answer

결론

처음에 규칙을 찾느라 어려웠다. 틱택토를 해본적도 없었기 때문이다. 규칙을 빨리 찾고나서 구현은 생각보다 쉬웠다. 하지만 밑에 있는 코드는 너무 복잡해 보여서 Python의 all function을 사용해서 깔끔하게 바꾸었다. 덕분에 all function을 배워갔다.

https://school.programmers.co.kr/learn/courses/30/lessons/159993

문제

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

입출력( + 추가적인 Test Case)

제한사항에 대해 보고싶으면 눌러주세요

풀이방법

사용한 알고리즘 : BFS

크게 2개로 나누어서 구현했습니다.

1. S 에서 L까지의 최단거리를 구합니다.

2. L 에서 E까지의 최단거리를 구합니다.

-> 최단거리를 구하는 방식은 BFS를 사용해서 풀었습니다.

코드

from collections import deque

INF = float('inf')

def solution(maps):
    answer = 0
    n = len(maps)
    m = len(maps[0])
    matrix = [[INF] * m for _ in range(n)]
    deq = deque()
    
    # S 위치 찾기
    for i in range(n):
        for j in range(m):
            if maps[i][j] == 'S':
                matrix[i][j] = 0
                deq.append((i, j, 0))
                break
        if deq:
            break

    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

    # S => L
    while deq:
        x, y, cnt = deq.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] != 'X':
            
            	# L을 찾았을 경우
                if maps[nx][ny] == 'L':
                    answer += cnt + 1

                    # deq 초기화
                    deq = deque()
                    deq.append((nx, ny, 0))
                    break
                    
                if cnt + 1 < matrix[nx][ny]:
                    matrix[nx][ny] = cnt + 1
                    deq.append((nx, ny, cnt + 1))
        if answer != 0:
            break

    temp_answer = answer
    matrix = [[INF] * m for _ in range(n)]

    # L => E
    
    while deq:
        x, y, cnt = deq.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] != 'X':
                if maps[nx][ny] == 'E':
                    answer += cnt + 1
                    break
                if cnt + 1 < matrix[nx][ny]:
                    matrix[nx][ny] = cnt + 1
                    deq.append((nx, ny, cnt + 1))
        
        # answer 값이 변하면 break
        if answer != temp_answer:
            break

	# L -> E 경로가 없으면 -1
    if answer == temp_answer:
        return -1

    return answer

결론

1. S 에서 L까지의 최단거리를 구합니다.

2. L 에서 E까지의 최단거리를 구합니다.

1에서 최단거리가 없을 경우, 2에서 최단거리가 없는 경우와 둘 다 없는 경우를 생각해서 풀면 바로 풀리는 문제이다. 단, 범위오류가 발생할 수 있으니 변수 설정을 잘 해주면 된다.

처음 겪어보는 런타임 에러여서 당황했지만 백준에서 해왔던 것처럼 범위 오류라 가정하고 변수를 재설정하여 해결하였다.

https://school.programmers.co.kr/learn/courses/30/lessons/176962

문제

과제를 받은 루는 다음과 같은 순서대로 과제를 하려고 계획을 세웠습니다. 
  과제는 시작하기로 한 시각이 되면 시작합니다.
  새로운 과제를 시작할 시각이 되었을 때, 기존에 진행 중이던 과제가 있다면 진행 중이던 과제를 멈추고 새로운 과제를 시작합니다.

  진행중이던 과제를 끝냈을 때, 잠시 멈춘 과제가 있다면, 멈춰둔 과제를 이어서 진행합니다.

    만약, 과제를 끝낸 시각에 새로 시작해야 되는 과제와 잠시 멈춰둔 과제가 모두 있다면, 새로 시작해야 하는 과제부터 진행합니다.

  멈춰둔 과제가 여러 개일 경우, 가장 최근에 멈춘 과제부터 시작합니다.

과제 계획을 담은 이차원 문자열 배열 plans가 매개변수로 주어질 때, 과제를 끝낸 순서대로 이름을 배열에 담아 return 하는 solution 함수를 완성해주세요.

입출력 ( + 추가적인 Test Case)

풀이방법

시간 순서대로 풀어 내기 위해서 hh:mm 형식을 -> 분 형식으로 바꾸는 함수를 만들었습니다.  ex) 12:30 -> 750

1. plans의 내부 요소 중에 time을 함수를 이용해 hh:mm 형식을 total_time인 정수형태로 바꾸어서 다시 저장했습니다.

2. plans에서의 total_time을 작은 순부터 정렬했습니다.

3. plans의 가장 앞에 있는 total_time을 now_time으로 설정하고 과제 풀이를 시작했습니다.

* first와 second의 설명 : second는 현재 처리 해야할 과제를 가리킵니다. first는 현재 처리할 과제보다 앞에 있는 과제들을 가리킵니다.

* stack을 통해서 stack은 현재 처리해야할 과제 이전에 과제들을 담아두는 장소입니다.

4. stack이 비어있는 경우, 현재 과제와 처리되지 않은 이전 과제들을 비교할 수 없어서 stack에 현재 과제를 추가합니다.

5. stack이 비어있지 않은 경우,

5-1. 현재 과제가 다음 과제 시작시간보다 이전에 끝나는 경우, answer 에 추가합니다.

5-2. 현재 과제가 다음 과제 시작시간을 넘어가는 경우, plans에 다음과제를 처리합니다.

6. plans를 다 순회하게 된다면 남은 과제들을 차례대로 stack 방식으로 answer에 처리되지 않은 과제들을 추가합니다.

7. answer을 반환합니다.

코드

from collections import deque


# 시간 계산
def cal_time(time):
    total_time = 0
    hour, minute = map(int, time.split(':'))
    total_time = hour * 60 + minute
    return total_time


def solution(plans):
    answer = []
    plans = [(name, cal_time(time), int(playtime)) for name, time, playtime in plans]
    # 시작시간 순으로 정렬
    plans.sort(key=lambda x: x[1])
    stack = deque()

	# 시작시간 설정
    now_time = plans[0][1]

    for i in plans:
        second_name, second_time, second_playtime = i

        while stack:
            first_name, first_playtime = stack.pop()
            # 진행중인 과제를 끝낸 경우
            if now_time + first_playtime <= second_time:
                now_time = now_time + first_playtime
                answer.append(first_name)
            # 과제를 끝내지 못하고 다음 과제가 오는 경우
            else:
                stack.append((first_name, (now_time + first_playtime) - second_time))
                now_time = second_time
                break

        stack.append((second_name, second_playtime))
        # 과제가 끝나고 다음 과제 시간으로 설정
        now_time = second_time

	# 미뤄뒀던 과제들 차례대로 마침
    while len(stack) != 0:
        answer.append(stack.pop()[0])

    return answer

결론

stack 방식을 사용해서 풀면된다.

39번째 줄에 있는 코드를 사용하지 않는다면, 2,3,4,5,7 번 case를 틀렸다. 시간 설정을 좀 더 유의해서 할 필요가 있다.

오류가 발생하는 이유는 현재 과제를 처리하고 다음 과제를 처리하기 전까지 시간이 비어있다면 시간 설정에서 오류가 발생했다.

deque 이란?

결론부터 말씀드리자면 list 와 같은 배열이지만 "양쪽에서 요소를 추가와 삭제가 가능한" 자료구조입니다.

Python의 collections 모듈에서 제공하는 deque는 "double-ended queue"(양방향 큐)의 줄임말 입니다. 다시 말해서 queue(큐)에 앞쪽에 연산이 추가된 자료구조라고 볼 수 있습니다.

써야하는 이유

deque 자료구조는 pop, append method는 시간복잡도가 O(1)입니다.

하지만 list 자료구조에서 pop, append method는 시간복잡도가 O(n)입니다.

이러한 이유로 작은 데이터 셋에서는 큰 차이가 없지만 데이터 셋이 큰 경우에 큰 차이를 알 수 있습니다.

특히 BFS를 queue로 구현하면 시간초과가 발생하지만 deque를 통해 구현하면 시간초과가 발생하지 않습니다.

그러므로 간단하거나 작은 데이터의 경우에는 list, 그 외의 경우에는 deque를 사용하는 것을 추천합니다.

메소드 종류

import collections

d = collections.deque()

구현 방법

from collections import deque
d = deque('ghi')                 # 'g', 'h' 'i' 요소를 가진 deque 생성합니다.
for elem in d:                   # deque 요소를 순회하며 출력합니다.
    print(elem.upper())
    
# 출력결과
# G
# H
# I 

d.append('j')                    		# 오른쪽에 'j'를 추가합니다.
d.appendleft('f')                		# 왼쪽에 'f'를 추가합니다.
print(d)                         		# deque 출력합니다.
# deque(['f', 'g', 'h', 'i', 'j'])

print(d.pop())                          # 오른쪽 요소를 제거 및 반환되면서 출력합니다.
# j
print(d.popleft())                      # 왼쪽 요소를 제거 및 반환되면서 출력합니다.
# f
print(list(d))                          # deque의 요소를 모두 출력합니다.
# ['g', 'h', 'i']
print(d[0])                             # 왼쪽의 첫번재 요소 출력합니다.
# g
print(d[-1])                            # 오른쪽의 첫번째 요소 출력합니다.
# i

print(list(reversed(d)))                # deque의 요소를 반전합니다.
# ['i', 'h', 'g']
print('h' in d)                         # deque안에 요소 찾기합니다.
# True
d.extend('jkl')                  		# 오른쪽에 array를 추가합니다.
print(d)
# deque(['g', 'h', 'i', 'j', 'k', 'l'])
d.rotate(1)                      		# 오른쪽으로 1만큼 회전합니다.
print(d)
# deque(['l', 'g', 'h', 'i', 'j', 'k'])
d.rotate(-1)		                     # 왼쪽으로 1만큼 회전합니다.
print(d)
# deque(['g', 'h', 'i', 'j', 'k', 'l'])

print(deque(reversed(d)))               # deque를 반전시킵니다.
# deque(['l', 'k', 'j', 'i', 'h', 'g'])
d.clear()                        		# deque의 요소들을 모두 제거합니다.
d.pop()                          		# deque의 요소들이 없어서 오류를 발생시킵니다.
# 오류출력
# Traceback (most recent call last):
#    File "<pyshell#6>", line 1, in -toplevel-
#        d.pop()
# IndexError: pop from an empty deque

d.extendleft('abc')              # c -> b -> a 순으로 왼쪽에 추가하기 때문에 뒤집에서 추가됩니다.
print(d)
# deque(['c', 'b', 'a'])

관련문제들

https://www.acmicpc.net/problem/10845

list와 deque를 모두 구현해볼 수 있는 문제입니다.

https://www.acmicpc.net/problem/7569

list로 구현하면 시간초과가 발생하고 deque로 구현하면 시간초과가 발생하지 않는 문제입니다.

참고문헌 : https://docs.python.org/ko/3/library/collections.html#collections.deque