Jin의 일상

solution 함수의 독스트링을 통해 알고리즘을 확인하시길 바랍니다!

import sys
from collections import deque


INPUT = sys.stdin.readline
N, M = map(int, INPUT().split())
BOARD = [list(map(int, INPUT().split())) for _ in range(N)]
DIRECTION = ((0, -1), (0, 1), (-1, 0), (1, 0))


def cheese_to_air(loc_list):
    """ BOARD에 있는 공기에 닿아 있는 치즈를 공기로 바꿈.

    * BOARD에서 0은 공기, 1은 치즈를 의미.
    """
    for x, y in loc_list:
        BOARD[y][x] = 0


def bfs():
    """ 공기에 닿아 있는 치즈의 좌표들을 구한 뒤, 리스트 형식로 리턴.

    * bfs로 구현함.
    - continue 조건: (1)좌표상 범위 (2)방문했던 좌표 (3)치즈를 만났을 때
    """
    outside_cheese_loc_list = []
    visited = [[0] * M for _ in range(N)]
    q = deque([(0, 0)])
    while q:
        x, y = q.popleft()
        for i in range(4):
            next_x = x + DIRECTION[i][0]
            next_y = y + DIRECTION[i][1]
            if (0 > next_x or next_x >= M) or (0 > next_y or next_y >= N):
                continue

            if visited[next_y][next_x] == 1:
                continue

            visited[next_y][next_x] = 1

            if BOARD[next_y][next_x] == 1:
                outside_cheese_loc_list.append((next_x, next_y))
                continue

            q.append((next_x, next_y))
    return outside_cheese_loc_list


def solution():
    """ 공기와 닿은 치즈의 개수가 0이 될 때 까지 넓이 우선 탐색을 반복적으로 수행함.

    * 1회 반복에 발생하는 상태 변화
    (1) 공기와 맞닿은 치즈의 좌표 목록 구하기
    (2) 경과 시간(hour)이 1만큼 증가
    (3) 공기와 맞닿은 치즈들을 공기로 바꿈
    (4) 현재 치즈의 개수 저장


    while문 종료 후에 반복 수행된 횟수(hour)와 1시간 전 치즈의 개수를 출력(print)함.
    """
    hour = 0
    while outside_cheeses := bfs():
        hour += 1
        cheese_to_air(outside_cheeses)
        cheese_num_1hour_ago = len(outside_cheeses)
    print(hour)
    print(cheese_num_1hour_ago)


if __name__ == '__main__':
    solution()

옷의 타입별 개수를 구해서 조합을 구했다.

두 가지 방식으로 풀이했는 (1) 딕셔너리 사용 (2) set과 list의 count를 사용해서 옷 타입 개수 구하기

1번 방식의 풀이가 더욱 직관적이지만, 2번 방식의 접근이 신선하다.

리스트 타입에 있는 원소들을 set()하여 고유의 원소만 새로운 변수에 담았다.

그 다음 리스트의 count()를 사용해서 각 리스트에 있는 원소의 개수를 구했다.

(1) 딕셔너리 사용 

import sys

INPUT = sys.stdin.readline


def get_comb_num_except_zero(cnt_per_type):
    """ 착용 가능한 의상의 조합 수를 구한다.
    - 각 의상은 종류별로 한 번만 착용 가능하다.
    - 모든 의상을 착용하지 않는 경우는 없다.

    cnt_per_type: 의상 종류별 개수, 딕셔너리
    """
    res = 1
    for num in cnt_per_type.values():
        res *= num + 1
    return res - 1


def solution():
    """
    test_case_num: 테스트 케이스 개수
    clothes_num: 하나의 테스트 케이스에 주어진 의상의 개수
    clothes_type: 의상의 종류
    cnt_per_type: 의상의 종류별 개수, 딕셔너리
    """
    for _ in range(test_case_num := int(INPUT())):
        cnt_per_type = dict()
        for _ in range(clothes_num := int(INPUT())):
            _, clothes_type = input().split()
            cnt_per_type[clothes_type] = cnt_per_type.get(clothes_type, 0) + 1
        print(get_comb_num_except_zero(cnt_per_type))

if __name__ == "__main__":
    solution()

(2) set과 list의 count를 사용

import sys
# sys.stdin = open("input.txt", "r")

INPUT = sys.stdin.readline


def solution():
    for _ in range(test_case_num := int(INPUT())):
        types = []
        for _ in range(clothes_num := int(INPUT())):
            _, clothes_type = INPUT().split()
            types.append(clothes_type)

        set_types = set(types)

        cnt_per_type = map(lambda x: types.count(x) + 1, set_types)

        res = 1
        for num in cnt_per_type:
            res *= num
        print(res - 1)

if __name__ == "__main__":
    solution()

# programmers, 베스트앨범

from collections import defaultdict


def get_elbum_list(genres_in_order, play_list_by_genre):
    elbum_list = []
    for genre in genres_in_order:
        play_list_by_genre[genre].sort(key=lambda x: (-x[0], x[1]))
        elbum_list.extend(list(map(lambda x: x[1], play_list_by_genre[genre][:2])))
    return elbum_list


def get_order_by_genres(total_play_by_genre):
    return sorted(total_play_by_genre.keys(), key=lambda x: total_play_by_genre[x], reverse=True)


def solution(genres, plays):
    total_play_by_genre = defaultdict(int)
    play_list_by_genre = defaultdict(list)

    for i in range(len(genres)):
        total_play_by_genre[genres[i]] += plays[i]
        play_list_by_genre[genres[i]].append((plays[i], i))

    genres_in_order = get_order_by_genres(total_play_by_genre)
    return get_elbum_list(genres_in_order, play_list_by_genre)

if __name__ == '__main__':
    genres = ["classic", "classic", "classic", "pop"]
    plays = [1000, 1000, 1000, 100]
    print(solution(genres, plays))

"""
백준, 11000 강의실 배정

(1) 빨리 시작하고, 빨리 끝나는 강의 순서로 정렬한 다음
(2) heapq 알고리즘을 이용하여 바로 시작 가능한 강의실 배정
  - 수업이 끝났으면 기존 강의실
  - 끝난 수업이 없으면 새로운 강의실
"""

import sys
import heapq
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def get_num_classroom(num_lecture, schedule_list):
    hq = []
    for i in range(num_lecture):
        if hq and hq[0] <= schedule_list[i][0]:
            heapq.heappop(hq)
        heapq.heappush(hq, schedule_list[i][1])
    return len(hq)


def solution():
    num_lecture = int(input())
    schedule_list = []
    for _ in range(num_lecture):
        start_time, end_time = map(int, input().split())
        schedule_list.append((start_time, end_time))

    schedule_list.sort()
    return get_num_classroom(num_lecture, schedule_list)

if __name__ == "__main__":
    print(solution())

"""
백준, 2504 괄호의 값
"""

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def get_point(s):
    point_by_bracket_type = {'(': 1, '[': 1}
    res_list = [0]
    for bracket in s:
        if bracket in point_by_bracket_type:
            if bracket == '(':
                point_by_bracket_type['('] *= 2
            else:
                point_by_bracket_type['['] *= 3
            res_list[-1] = point_by_bracket_type['('] * point_by_bracket_type['[']
        else:
            if bracket == ')':
                point_by_bracket_type['('] //= 2
            else:
                point_by_bracket_type['['] //= 3
            res_list.append(0)
    return sum(res_list)


def is_right_form(s):
    bracket_form_dict = {'(': ')', '[': ']'}
    stack = []
    for i in range(len(s)):
        if s[i] in bracket_form_dict:
            stack.append(s[i])
        elif stack and bracket_form_dict[stack[-1]] == s[i]:
            stack.pop()
        else:
            return False
    if not stack:
        return True


def solution():
    s = input()
    if is_right_form(s):
        return get_point(s)
    else:
        return 0


if __name__ == "__main__":
    print(solution())

"""
백준, 11659 구간 합 구하기 4

구간 합 알고리즘
(1) 주어진 리스트의 누적합 결과를 리스트(cumulative_sum_list) 1 ~ n의 각 원소에 넣음 (0번 인덱스는 0임).
(2) i ~ j의 구간 합(1 <= i <= j): cumulative_sum_list[j] - commulative_sum_list[i - 1]
"""

import sys

# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def get_cumulative_sum_list(number_list):
    cumulative_sum_list = [0]
    for i in range(len(number_list)):
        cumulative_sum_list.append(cumulative_sum_list[-1] + number_list[i])
    return cumulative_sum_list


def solution():
    n, m = map(int, sys.stdin.readline().split(' '))
    number_list = list(map(int, sys.stdin.readline().split(' ')))

    cumulative_sum_list = get_cumulative_sum_list(number_list)
    for _ in range(m):
        i, j = map(int, sys.stdin.readline().split(' '))
        print(cumulative_sum_list[j] - cumulative_sum_list[i-1])  # get result.

if __name__ == "__main__":
    solution()

"""
백준, 1157 단어공부
대문자 변환 -> 알파벳별 사용된 횟수 -> 가장 많이 사용된 알파벳 리턴
* 가장 많이 사용된 알파벳이 2개 이상이면 ? 리턴
"""

import sys

# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def get_most_used_alphabet(used_number_alphabet_dict):
    most_used_num = max(used_number_alphabet_dict.values())
    most_used_alphabet = ''
    for alphabet, number in used_number_alphabet_dict.items():
        if most_used_num == number:
            if most_used_alphabet != '':
                return '?'
            most_used_alphabet = alphabet
    return most_used_alphabet


def count_used_number_alphabet(word):
    used_num_alphabet_dict = {}
    for i in range(len(word)):
        used_num_alphabet_dict[word[i]] = used_num_alphabet_dict.get(word[i], 0) + 1
    return used_num_alphabet_dict


def make_upper_case(word):
    return list(map(lambda x: x.upper(), word))


def answer(word):
    upper_cased_word_list = make_upper_case(word)
    used_number_alphabet_dict = count_used_number_alphabet(upper_cased_word_list)
    return get_most_used_alphabet(used_number_alphabet_dict)


if __name__ == "__main__":
    word = input()
    print(answer(word))

문제 풀이

1. 문자열의 길이만큼, 주어진 문자열의 맨 앞에 값을 맨 뒤로 보내야 하므로 데크 자료구조를 사용

2. 변환된 문자열이 올바른지 확인하기 위해 스택 자료구조 사용

  - 괄호 형태들을 dictionary로 저장하여 가독성을 높임.

코드 

  
from collections import deque
bracket_form_dict = {"(": ")", "{": "}", "[": "]"}

def is_right_form(s):
    stack = []
    for bracket in s:
        if bracket in bracket_form_dict:
            stack.append(bracket)
        elif stack and bracket_form_dict[stack[-1]] == bracket:
            stack.pop()
        else:
            return False
    if not stack:
        return True


def solution(s):
    answer = 0
    s_deque = deque(s)
    for _ in range(len(s)):
        s_deque.append(s_deque.popleft())
        if is_right_form(s_deque):
            answer += 1
    return answer