# 프로그래머스 문제 '위장'
# https://programmers.co.kr/learn/courses/30/lessons/42578

def solution(clothes):

    cloth_dict = dict()

    for name, kind in clothes:
        cloth_dict[kind] = cloth_dict.get(kind, 0) + 1
    
    answer = 1
    for cloth_len in cloth_dict.values():
        answer *= (cloth_len + 1)

    return answer - 1


if __name__=='__main__':

    test_cases = [
        {
            'clothes': [["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]],
            'answer': 5 
        },
        {
            'clothes': [["crowmask", "face"], ["bluesunglasses", "face"], ["smoky_makeup", "face"]],
            'answer': 3
        }
    ]
    
    for test_case in test_cases:
        clothes = test_case['clothes']
        answer = test_case['answer']
        my_answer = solution(clothes)

        print(f'answer: {answer}, my_answer: {my_answer}')

# 프로그래머스 문제 '베스트앨범'
# https://programmers.co.kr/learn/courses/30/lessons/42579

class Song:

    def __init__(self, song_num, genre, play):
        self.song_num = song_num
        self.genre = genre
        self.play = play
    

def solution(genres, plays):
    genre_dict = {}
    genre_list = []

    for song_num, genre, play in zip(range(len(genres)), genres, plays):
        song = Song(song_num, genre, play)

        if not genre_dict.get(genre):
            genre_list.append(genre)
            genre_dict[genre] = {'total_plays': 0, 'song_list': []}
        
        genre_dict[genre]['total_plays'] += play
        genre_dict[genre]['song_list'].append(song)

    genre_list.sort(reverse=True, key=lambda genre: genre_dict[genre]['total_plays'])

    best_album = []
    for genre in genre_list:
        song_list = genre_dict[genre]['song_list']
        song_list.sort(reverse=True, key=lambda song: (song.play, -song.song_num))
        best_songs = song_list[:2]
        for song in best_songs:
            best_album.append(song.song_num)
    
    return best_album



def solution2(genres, plays):
    genre_dict = {}
    genre_list = []

    for song_num, genre, play in zip(range(len(genres)), genres, plays):
        song = Song(song_num, genre, play)

        if not genre_dict.get(genre):
            genre_dict[genre] = {'total_plays': 0, 'best_songs': [Song(-1, genre, -1), Song(-1, genre, -1)]}
            genre_list.append(genre)

        genre_dict[genre]['total_plays'] += play

        best_songs = genre_dict[genre]['best_songs']
        if best_songs[0].play < play:
            best_songs[1] = best_songs[0]
            best_songs[0] = song
            continue

        if best_songs[0].play == play:
            if best_songs[0].song_num > song_num:
                best_songs[1] = best_songs[0]
                best_songs[0] = song
                continue
        
        if best_songs[1].play < play:
            best_songs[1] = song
            continue
        
        if best_songs[1].play == play:
            if best_songs[1].song_num > song_num:
                best_songs[1] = song

    genre_list.sort(reverse=True, key=lambda genre: genre_dict[genre]['total_plays'])

    best_album = []

    for genre in genre_list:
        best_songs = genre_dict[genre]['best_songs']
        for song in best_songs:
            if song.play >= 0:
                best_album.append(song.song_num)

    return best_album


if __name__=='__main__':

    genres = ["classic", "pop", "classic", "classic", "pop"]
    plays = [500, 600, 150, 800, 2500]
    answer = [4, 1, 3, 0]
    my_answer = solution(genres, plays)

    print(f'answer: {answer}, my_answer: {my_answer}')

def check(buildings, idx):
    l = idx - 2 if idx >= 2 else 0
    r = idx + 3

    sides = buildings[l : idx] + buildings[idx + 1 : r]
    side_max = max(sides)

    height = buildings[idx]

    if height - side_max > 0:
        return height - side_max
    else:
        return 0

T = 10
for t in range(1, T + 1):
    n = int(input().strip())
    buildings = list(map(int, input().split()))

    total = 0
    for idx in range(n):
        total += check(buildings, idx)

    print(f'#{t} {total}')

T = int(input())

mirror = {
    'b': 'd',
    'd': 'b',
    'p': 'q',
    'q': 'p'
}

for t in range(1, T+1):
    word = input()

    result = ''
    for i in range(len(word) - 1, -1, -1):
        result += mirror[word[i]]

    print('#{} {}'.format(t, result))

T = int(input())

for t in range(1, T+1):
    N, K = map(int, input().split())
    MAP = [[0 for _ in range(N+2)] for _ in range(N+2)]

    for i in range(1, N+1):
        MAP[i][1:-1] = map(int, input().split())

    cnt_list = [0 for _ in range(N + 1)]
    for i in range(1, N+1):
        # row
        j = 1
        while j <= N:
            cnt = 0
            while MAP[i][j]:
                cnt += 1
                j += 1
            cnt_list[cnt] += 1
            j += 1

        # col
        j = 1
        while j <= N:
            cnt = 0
            while MAP[j][i]:
                cnt += 1
                j += 1
            cnt_list[cnt] += 1
            j += 1


    print('#{} {}'.format(t, cnt_list[K]))

방법 1) bubble sort

def bubble_sort(lst):
    for i in range(1, len(lst)):
        for j in range(len(lst) - i):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

    return lst

if __name__=='__main__':
    T = int(input())

    for t in range(1, T + 1):
        N = int(input())
        lst = list(map(int, input().split()))

        bubble_sort(lst)

        print('#{}'.format(t), end=' ')
        print(*lst, sep=' ')

방법 2) selection sort

def selection_sort(lst):
    for i in range(len(lst) - 1):
        for j in range(i + 1, len(lst)):
            if lst[i] > lst[j]:
                lst[i], lst[j] = lst[j], lst[i]

    return lst

if __name__=='__main__':
    T = int(input())

    for t in range(1, T + 1):
        N = int(input())
        lst = list(map(int, input().split()))

        selection_sort(lst)

        print('#{}'.format(t), end=' ')
        print(*lst, sep=' ')

방법 3) merge sort

def merge_sort(lst, l, r):
    if r - l <= 1:
        return

    c = (l + r) // 2

    merge_sort(lst, l, c)
    merge_sort(lst, c, r)

    l_ptr = l
    r_ptr = c
    tmp_lst = []
    while l_ptr < c and r_ptr < r:
        if lst[l_ptr] < lst[r_ptr]:
            tmp_lst.append(lst[l_ptr])
            l_ptr += 1
            continue
        else:
            tmp_lst.append(lst[r_ptr])
            r_ptr += 1

    while l_ptr < c:
        tmp_lst.append(lst[l_ptr])
        l_ptr += 1

    while r_ptr < r:
        tmp_lst.append(lst[r_ptr])
        r_ptr += 1

    for tmp_i, i in enumerate(range(l, r)):
        lst[i] = tmp_lst[tmp_i]

    return lst

if __name__=='__main__':
    T = int(input())

    for t in range(1, T + 1):
        N = int(input())
        lst = list(map(int, input().split()))

        merge_sort(lst, 0, len(lst))

        print('#{}'.format(t), end=' ')
        print(*lst, sep=' ')

T = 10

for t in range(1, T+1):
    int(input())
    MAP = [[0 for _ in range(102)] for _ in range(100)]
    for i in range(100):
        MAP[i][1:-1] = map(int, input().split())

    start_j = 0
    for j in range(1, 101):
        if MAP[99][j] == 2:
            start_j = j
            break

    i = 99
    j = start_j
    while i:
        if MAP[i][j + 1]:
            while MAP[i][j + 1]:
                j += 1
            i -= 1
        elif MAP[i][j - 1]:
            while MAP[i][j - 1]:
                j -= 1
            i -= 1
        else:
            i -= 1

    result = j - 1
    print('#{} {}'.format(t, result))

T = int(input())

for t in range(1, T+1):
    N, M = map(int, input().split())
    MAP = []
    for i in range(N):
        MAP.append(list(map(int, input().split())))

    total_map = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(1, N + 1):
            total_map[i][j] = MAP[i - 1][j - 1] + total_map[i - 1][j] + total_map[i][j - 1] - total_map[i - 1][j - 1]

    result = total_map[M][M]
    for i in range(M, N + 1):
        for j in range(M, N + 1):
            total = total_map[i][j] - total_map[i - M][j] - total_map[i][j - M] + total_map[i - M][j - M]
            if total > result:
                result = total

    print('#{} {}'.format(t, result))