그냥 코딩하는 사람의 블로그

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

풀이 과정

1. 문제를 풀면서 고려해야 할 점이 좀 있음..
   1. Q 위치 이후에 채팅을 친 사람들은 무조건 읽은 사람
   2. Q 위치 이전에 채팅을 친 사람들 중 Q 위치에서 읽은 사람과 읽지 않은 인원이 같은 경우에도 해당 사람 또한 읽은 사람이라고 볼 수 있다.
2. 두가지 케이스에 맞추어서 정답 출력을 하면 된다. 단, 읽지 않은 사람의 수가 0인 경우에는 -1을 출력해준다.
   
   • 여기서 읽지 않은 사람의 카운트를 입력받은걸로 하지 않고.. 정답 리스트의 길이가 0인 경우로 했다가 오답처리가 계속 나왔다.. 

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()

N, K, Q = map(int, input().split())
people = set([chr(ch) for ch in range(ord('A'), ord('A')+N)])
people.remove('A')
messages = [[0, 0]] + [input().split() for _ in range(K)]

for i in range(Q, len(messages)):
    if messages[i][1] in people:
        people.remove(messages[i][1])

for i in range(Q-1, 0, -1):
    if messages[i][0] == messages[Q][0]:
        if messages[i][1] in people:
            people.remove(messages[i][1])
    else:
        break

people_list = sorted(list(people))
if messages[Q][0] == '0':
    print(-1)
else:
    print(*people_list)

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

풀이 과정

1. 생각보다는 간단한데 조건이 너무 많아서 까다로움..
2. 초기에는 C 물통에만 물이 담겨져 있음.
3. BFS를 진행하면서 각각의 물통에 담겨져있는 물을 다른 물통으로 이동시킬 수 있는 모든 경우의 수 탐색
   
   1. 시작은 [0, 0, C 물통의 크기] => C 물통에만 물이 담겨져 있으므로.
   2. 각각의 물통에 담겨져있는 크기가 0보다 큰 경우 이동 가능
      1. a -> b,c / b -> a,c / c -> a, b 총 6가지 경우의 수 탐색
      2. 물이 넘치는 경우에는 옮기는 물통의 크기까지만 물을 넣고, 남은 물은 다시 자기 자신에 넣어줌.
   3. BFS를 진행하면서 a 물통의 크기가 0일 때의 c 물통의 크기들을 따로 저장
4. 저장해 둔 c 물통의 크기 리스트를 오름차순으로 정렬한 다음 출력
5. if문 조건 작성이 조금 난해하기도 하고, a 물통의 크기가 0일 때의 c 물통의 크기를 저장해야 하는것을 못봐서 그냥 c 물통의 크기를 저장했다가 계속 틀렸음.. 문제 잘 봐야 함.

소스 코드

import sys
from collections import deque

def bfs(max_a, max_b, max_c):
    answer = set()
    queue = deque()
    visited = set()
    queue.append([0, 0, max_c])
    visited.add(tuple([0, 0, max_c]))

    while queue:
        aL, bL, cL = queue.popleft()
        if aL == 0:
            answer.add(cL)

        # a -> b, c
        if aL > 0:
            if bL + aL <= max_b and (0, bL+aL, cL) not in visited:
                visited.add((0, bL+aL, cL))
                queue.append([0, bL+aL, cL])
            elif bL + aL > max_b and ((bL+aL)-max_b, max_b, cL) not in visited:
                visited.add(((bL+aL)-max_b, max_b, cL))
                queue.append([(bL+aL)-max_b, max_b, cL])

            if cL + aL <= max_c and (0, bL, cL+aL) not in visited:
                visited.add((0, bL, cL+aL))
                queue.append([0, bL, cL+aL])
            elif cL + aL > max_c and ((cL+aL)-max_c, bL, max_c) not in visited:
                visited.add(((cL+aL)-max_c, bL, max_c))
                queue.append([(cL+aL)-max_c, bL, max_c])

        # b -> a, c
        if bL > 0:
            if bL + aL <= max_a and (bL+aL, 0, cL) not in visited:
                visited.add((bL+aL, 0, cL))
                queue.append([bL+aL, 0, cL])
            elif bL + aL > max_a and (max_a, (bL+aL)-max_a, cL) not in visited:
                visited.add((max_a, (bL+aL)-max_a, cL))
                queue.append([max_a, (bL+aL)-max_a, cL])

            if cL + bL <= max_c and (aL, 0, cL+bL) not in visited:
                visited.add((aL, 0, cL+bL))
                queue.append([aL, 0, cL+bL])
            elif cL + bL > max_c and (aL, (cL+bL)-max_c, max_c) not in visited:
                visited.add((aL, (cL+bL)-max_c, max_c))
                queue.append([aL, (cL+bL)-max_c, max_c])

        # c -> a, b
        if cL > 0:
            if cL + aL <= max_a and (cL+aL, bL, 0) not in visited:
                visited.add((cL+aL, bL, 0))
                queue.append([cL+aL, bL, 0])
            elif cL + aL > max_a and (max_a, bL, (cL+aL)-max_a) not in visited:
                visited.add((max_a, bL, (cL+aL)-max_a))
                queue.append([max_a, bL, (cL+aL)-max_a])

            if cL + bL <= max_b and (aL, bL+cL, 0) not in visited:
                visited.add((aL, bL+cL, 0))
                queue.append([aL, bL+cL, 0])
            elif cL + bL > max_b and (aL, max_b, (bL+cL)-max_b) not in visited:
                visited.add((aL, max_b, (bL+cL)-max_b))
                queue.append([aL, max_b, (bL+cL)-max_b])
                
    return answer
            
        
    

a, b, c = map(int, sys.stdin.readline().rstrip().split())
temp = sorted(list(bfs(a, b, c)))
print(*temp)

https://programmers.co.kr/learn/courses/30/lessons/86971

풀이 과정

1. 전선들중 하나씩 빼보면서 분리된 전력망에 각각 몇개의 송전탑이 들어가는지 확인
   • 각각의 송전탑이 어느 전력망에 속하는지 구하기 위해 Union-Find 알고리즘 사용
2. 트리의 특성 상, 하나의 노드라도 연결을 끊으면 두개의 그룹으로 나뉘어질거라 생각하여, 파이썬의 defaultdict를 활용하여 각 전력망에 있는 송전탑의 개수를 저장한 다음, 두 값의 차이의 절댓값과 기존 정답의 비교를 통해 정답을 갱신한다.

소스 코드

from collections import defaultdict

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
    return parent[a]

def union(parent, a, b):
    pa = find(parent, a)
    pb = find(parent, b)
    if pa != pb:
        parent[pa] = parent[pb]

def solution(n, wires):
    answer = int(10e9)
    for skip in range(len(wires)):
        parent = [i for i in range(n+1)]
        for idx, wire in enumerate(wires):
            if skip == idx:
                continue
            if find(parent, wire[0]) != find(parent, wire[1]):
                union(parent, wire[0], wire[1])
        
        group_value = defaultdict(int)
        for i in range(1, n+1):
            group_value[find(parent, i)] += 1
        values = list(group_value.values())
        groupA, groupB = values[0], values[1]
        answer = min(answer, abs(groupA - groupB))
             
    return answer

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

풀이 과정

1. 숫자 K개를 지워서 얻을수 있는 가장 큰 수를 구하려면.. 첫자리를 가장 크게, 두번째 자리를 그다음 크게, ... 진행하여야 한다.
2. 따라서 스택으로 풀이를 하면 된다.
   1. 왼쪽 자리에서부터 오른쪽 자리 순서로 스택에 넣는다.
   2. 스택에 넣을 때, 기존 스택의 맨 위 숫자보다 현재 숫자가 크다면 해당 숫자를 빼내준다.
   3. 숫자를 빼낸 횟수가 K개라면 (2)는 생략한다.
3. 전체 자리에 대해 진행이 되었다면, 마지막으로 K개보다 숫자를 덜 빼냈을수도 있을 것이다.
4. 따라서, K개가 될때까지 스택에서 pop해주면 된당.

소스 코드

import sys

input = lambda : sys.stdin.readline().rstrip()

N, K = map(int, input().split())
number = list(map(int, list(input())))
stack = []
delete_count = 0

for n in number:
    while stack and n > stack[-1] and delete_count < K:
        stack.pop()
        delete_count += 1
    stack.append(n)

if delete_count < K:
    for _ in range(K-delete_count):
        stack.pop()

if len(stack) == 0:
    print(0)
else:
    print("".join(map(str, stack)))

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

풀이 과정

1. 학번을 키, 신청 인덱스를 값으로 하는 딕셔너리를 만들어 준다.
   • 매 신청마다 인덱스를 1씩 증가시키면서 입력받은 키 값에 인덱스를 저장한다.
2. 딕셔너리의 키-값을 값을 기준으로 오름차순 정렬시켜 준다.
   • 딕셔너리의 값이 낮은 경우 먼저 수강신청 한 것이며, 값이 높은 경우 늦게 수강신청 한것으로 간주
3. 정렬된 딕셔너리의 앞에서 L개의 원소를 꺼내면 해당 인원들이 수강신청되는 인원들이므로 출력해주면 된다.

소스 코드

import sys

input = lambda : sys.stdin.readline().rstrip()

K, L = map(int, input().split())

hashtable = dict()
idx = 0
for _ in range(L):
    idx += 1
    sid = input()
    hashtable[sid] = idx

sugang_data = sorted(hashtable.items(), key=lambda x:x[1])
sugang_data = sugang_data[:K]

for student, _ in sugang_data:
    print(student)

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

풀이 과정

문제가 너무 길어서 다 문제인가 했는데 맨 마지막 부분만 문제다

1. 포켓몬의 개수와 번호를 리스트로 두는 경우에는 N, M이 100000까지 가능하므로 시간 초과가 나타날 수 있으므로 해시 방식을 사용해야 한다. 해시는 딕셔너리로 구현할 수 있다.
2. 두개의 딕셔너리를 사용한다.
   1. [포켓몬 이름] => 번호 
   2. [번호] => 포켓몬 이름
3. 먼저, 포켓몬 정보에 맞추어서 딕셔너리를 채워준다.
   • 인덱스를 하나씩 늘려가면서 포켓몬 이름에 대응되는 인덱스, 인덱스에 대응되는 포켓몬 이름을 채워준다.
4. 문제가 주어지면 우선 문제가 숫자인지 검사하고, 숫자라면 [인덱스] => 포켓몬 이름 형식의 딕셔너리에서 값을 가져오고, 아니라면 [포켓몬 이름] => 인덱스 형식의 딕셔너리에서 값을 가져와서 출력해주면 된다.

소스 코드

import sys

input = lambda : sys.stdin.readline().rstrip()

n, m = map(int, input().split())

num_to_pokemon = {}
pokemon_to_num = {}
idx = 1

for _ in range(n):
    pokemon = input()
    num_to_pokemon[idx] = pokemon
    pokemon_to_num[pokemon] = idx
    idx += 1

for _ in range(m):
    question = input()
    if question.isdigit():
        print(num_to_pokemon[int(question)])
    else:
        print(pokemon_to_num[question])

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

풀이 과정

1. 함수를 회전시켜주는 함수를 만들어 둔다.
   • r, c, s를 받으면 [r-s, c-s] ~ [r+s, c+s] 정사각형의 테두리를 회전시켜주는 함수
   • 테두리 회전 시, 왼쪽 세로 -> 아래 가로 -> 오른쪽 세로 -> 위쪽 가로 순으로 구현하는게 개인적으로 제일 편했음.
   • 시작점의 값[r-s, c-s]만 따로 저장해둔 다음. 위 순서로 현재 위치 다음칸의 값을 현재 위치의 값으로 덮어씌워준다.
   • 이 때, s를 1 줄여서 재귀함수로 만들어 주면, 내부 사각형도 같이 회전되서 문제에서 제시하는 회전 연산이 된다.
2. permutations 함수를 사용하여서 돌릴수 있는 모든 경우의 수를 구한다.
   • 각각의 케이스를 테스트 해보면서 최솟값 갱신
3. 최솟값을 출력시켜 준다.

소스 코드

import sys
import copy
from itertools import permutations

input = lambda : sys.stdin.readline().rstrip()
N, M, K = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]

def rotate(target, r, c, s):
    if s == 0:
        return
    r, c = r-1, c-1
    start_x, start_y = r-s, c-s
    end_x, end_y = r+s, c+s
    x, y = start_x, start_y
    first_value = target[start_x][start_y]
    
    for i in range(start_x, end_x):
        target[i][start_y] = target[i+1][start_y]

    for i in range(start_y, end_y):
        target[end_x][i] = target[end_x][i+1]

    for i in range(end_x, start_x, -1):
        target[i][end_y] = target[i-1][end_y]

    for i in range(end_y, start_y, -1):
        target[start_x][i] = target[start_x][i-1]
        
    target[start_x][start_y+1] = first_value
    rotate(target, r+1, c+1, s-1)

def get_max_sumation(target):
    return min([sum(q) for q in target])

rotate_information = []
rotate_idx = [i for i in range(K)]
rotate_sequence = list(permutations(rotate_idx, K))

for _ in range(K):
    rotate_information.append(list(map(int, input().split())))

answer = int(10e9)

for sequence in rotate_sequence:
    temp = copy.deepcopy(matrix)

    for i in sequence:
        r, c, s = rotate_information[i]
        rotate(temp, r, c, s)

    answer = min(answer, get_max_sumation(temp))
    
print(answer)

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

풀이 과정

1. 가능한 모든 경우의 수에 대해서 탐색한다.(dfs 사용)
   1. 배열을 왼쪽 위에서부터 오른쪽 아래로 진행하면서 1을 만나게 되면, 해당 위치에서 1x1부터 5x5까지 붙일수 있는지 검사하고, 붙일수 있다면 붙인 후 다음 1을 찾는다. 이 때, 붙이게 된 경우 1을 0으로 수정해 주고, 다시 떼는 경우 0을 1로 수정해 준다. 
   2. 붙일수 있는지 없는지는 현재 위치[i, j]에서 [i~i+색종이 크기] [j~j+색종이 크기] 정사각형에 0이 있는지 없는지로 판단한다.
   3. 색종이의 개수가 1x1, 2x2, 3x3, 4x4, 5x5 모두 5장씩만 있으니 개수를 따로 저장 관리해주어야 한다.
   4. 모두 붙인 경우 최소 색종이 개수를 갱신시켜 준다.
2. recursion에서 하나의 위치만 담당해야 하는데, 가지치기가 제대로 되지 않아 계속 틀렸다.,, 하나의 recursion에서 하나의 색종이만 담당하도록 색종이를 발견하면 다음 recursion은 색종이 다음 위치부터 시작하게 처리하였으며, 색종이 처리가 끝나면 바로 리턴하도록 수정하였더니 통과하였다.

소스 코드

import sys

input = lambda : sys.stdin.readline().rstrip()

matrix = [list(map(int, input().split())) for _ in range(10)]

card_count = [0, 5, 5, 5, 5, 5] # 각 색종이 개수

min_card_count = int(10e9)

def check_card(x, y, size):
    if x+size > len(matrix) or y+size > len(matrix[0]):
        return False
    
    for i in range(x, x+size):
        for j in range(y, y+size):
            if matrix[i][j] == 0:
                return False
    return True

def set_value_to_matrix(x, y, size, value):
    if x+size > len(matrix) or y+size > len(matrix[0]):
        return
    for i in range(x, x+size):
        for j in range(y, y+size):
            matrix[i][j] = value

def check_finish():
    p = sum([p for m in matrix for p in m if p == 1])
    if p > 0:
        return False
    else:
        return True

def get_card_count():
    total_card_count = 0
    for i in range(1, 6):
        total_card_count += (5 - card_count[i])
    return total_card_count

def dfs(a, b):
    global min_card_count
    for i in range(a, len(matrix)):
        for j in range(b, len(matrix[0])):
            if matrix[i][j] == 1:
                for card in range(1, 6):
                    if not check_card(i, j, card):
                        return   
                    if card_count[card] > 0:
                        card_count[card] -= 1
                        set_value_to_matrix(i, j, card, 0)
                        dfs(i, 0)
                        set_value_to_matrix(i, j, card, 1)
                        card_count[card] += 1
                return
                        
    if check_finish():
        min_card_count = min(min_card_count, get_card_count())

dfs(0, 0)
if min_card_count == int(10e9):
    print(-1)
else:
    print(min_card_count)

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

풀이 과정

1. 문제를 잘 읽자.. 궁수들이 서로 다른 적만을 공격하는줄 알고 문제를 풀었다가 계속 틀렸다.. 맞왜틀 맞왜틀 하면서 무한 제출 하지 말자.. 
2. 두가지 단계로 문제를 풀이한다.
   1. 궁수들이 적들에게 활을 쏘는 단계
   2. 격자판을 한칸 밑으로 내리는 단계
3. 적들에게 활을 쏠 때, 각각의 궁수들이 맞추는 최단 거리의 적들 중, 가장 왼쪽에 있는 적을 골라야 하며, 3명의 궁수가 동시에 활을 쏘므로, 같은 적을 맞출수도 있으므로 중복을 카운팅하지 않도록 처리해주어야 하는게 포인트
4. 궁수의 위치같은 경우 최대 3명 배치 가능하므로 [0~M-1]까지의 리스트로 요소의 개수가 3개인 조합을 만들어준 다음 각각의 조합에 대해 시뮬레이션을 진행한다.
5. 시뮬레이션 해보면서 최대로 제거할수 있는 적의 수를 갱신한다.

소스 코드

import sys
import copy
from collections import deque
from itertools import combinations

input = lambda : sys.stdin.readline().rstrip()

N, M, D = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]

def movement_one_time(matrix):
    # 전체 배열 한칸씩 내림
    row, col = len(matrix), len(matrix[0])
    for j in range(col):
        for i in range(row-1, 0, -1):
            matrix[i][j] = matrix[i-1][j]

    for j in range(col):
        matrix[0][j] = 0

def kill_target(matrix, arthor_pos, attack_range):
    queue = deque([[arthor_pos[0], arthor_pos[1], 0]])
    visited = set((arthor_pos[0], arthor_pos[1]))
    ans_cost = -1
    dx = [0, -1, 0]
    dy = [-1, 0, 1]
    answer_list = []
    while queue:
        x, y, cost = queue.popleft()
        
        if cost == attack_range:
            continue
        
        if matrix[x][y] == 1:
            if ans_cost == -1:
                ans_cost = cost
                answer_list.append([x, y])
            else:
                if ans_cost == cost:
                    answer_list.append([x, y])
            continue

        for i in range(3):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < len(matrix) and 0 <= ny and ny < len(matrix[0]) and \
               (nx, ny) not in visited:
                visited.add((nx, ny))
                queue.append([nx, ny, cost+1])

    if len(answer_list) == 0:
        return None

    # 가장 왼쪽에 있는 적 찾는 부분
    min_left = int(10e9)
    min_index = 0
    for i in range(len(answer_list)):
        if answer_list[i][1] < min_left:
            min_index = i
            min_left = answer_list[i][1]
            
    target_x, target_y = answer_list[min_index]
    return [target_x, target_y]
                

all_case = list(combinations([i for i in range(M)], 3))

answer = 0
for case in all_case:
    test_matrix = copy.deepcopy(matrix)
    kill_count = 0
    for i in range(N):
        kill_set = set()
        for archor in case:
            P = kill_target(test_matrix, [N-1, archor], D)
            if P is not None:
                target_x, target_y = P
                kill_set.add((target_x, target_y))
        for x, y in kill_set:
            test_matrix[x][y] = 0
        kill_count += len(kill_set)
        movement_one_time(test_matrix)
    answer = max(answer, kill_count)

print(answer)

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

이게 이지야? 이지 같은 소리 하네 증말

문제 설명

1. 전체 이동 횟수가 최대 5번이므로 전체 대략 4^5제곱 정도의 케이스가 나온다.
   1. 1번, 2번, 3번, 4번 이동하는 케이스의 경우 결국 5번 이동할동안 거쳐가는 부분이므로 패스
2. 위, 아래, 좌, 우 이동 파트를 구현한다.
   1. 구현하는 방식은, 이동시킨 결과물을 저장할 새로운 배열을 만들어준 다음, 예시로 위쪽 이동의 경우 각 열마다 위에서 아래로 반복문을 돌면서 스택에 넣어준다.
   2. 스택의 맨 위 요소와 현재 넣는 요소의 값이 같으면 합쳐주고, 추후에 합쳐주지 않기 위해 플래그를 따로 걸어둔다.
   3. 스택의 맨 위 요소와 현재 넣는 요소의 값이 다르면 그냥 스택에 넣어주면 된다.
   4. 하나의 열에 대한 반복문이 종료되었으면 스택의 요소들을 첫번째 요소부터 새로운 배열의 맨 위에서부터 넣어주면 된다.
   5. 이 과정을 전체 열에 대해서 적용하면 위쪽 방향 이동이 종료된다.
   6. 위와 같은 방식으로 위, 아래, 좌, 우 이동 파트를 구현한다.
3. 전체 케이스에 대해서 실제로 이동시켜 보면서 이동시킬 때마다 배열의 최댓값을 갱신시켜주면 된다.
   • 대략 4^5제곱 정도 케이스가 나온다고 보면 된다.

소스 코드

import sys
import copy

from itertools import product

input = lambda : sys.stdin.readline().rstrip()
N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]

def up_down_movement(way, matrix):
    # way : 1, 2, 각각 위, 아래
    N = len(matrix)
    if way == 1:
        start, end, add = 0, N, 1
    elif way == 2:
        start, end, add = N-1, -1, -1

    new_matrix = [[0] * len(matrix) for _ in range(len(matrix))]
    for j in range(N):
        stack = []
        for i in range(start, end, add):
            if not stack and matrix[i][j] != 0:
                stack.append([matrix[i][j], False])
            elif stack and stack[-1][1] == False and stack[-1][0] == matrix[i][j]:
                latest, _ = stack.pop()
                stack.append([matrix[i][j] + latest, True])
            elif stack and matrix[i][j] != 0:
                stack.append([matrix[i][j], False])

        for i in range(len(stack)):
            if way == 1:
                new_matrix[i][j] = stack[i][0]
            elif way == 2:
                new_matrix[N-1-i][j] = stack[i][0]
                
    return new_matrix

def left_right_movement(way, matrix):
    # way가 각각 1,2일때 왼쪽, 오른쪽
    N = len(matrix)

    if way == 1:
        start, end, add = 0, N, 1
    elif way == 2:
        start, end, add = N-1, -1, -1

    new_matrix = [[0] * len(matrix) for _ in range(len(matrix))]
    for i in range(N):
        stack = []
        for j in range(start, end, add):
            if not stack and matrix[i][j] != 0:
                stack.append([matrix[i][j], False])
            elif stack and stack[-1][1] == False and stack[-1][0] == matrix[i][j]:
                latest, _ = stack.pop()
                stack.append([matrix[i][j] + latest, True])
            elif stack and matrix[i][j] != 0:
                stack.append([matrix[i][j], False])

        for j in range(len(stack)):
            if way == 1:
                new_matrix[i][j] = stack[j][0]
            elif way == 2:
                new_matrix[i][N-1-j] = stack[j][0]

    return new_matrix

def get_max(matrix):
    return max([max(q) for q in matrix])

ways = [list('ulrd') for _ in range(5)]

answer = 0
# 5번 모든 경우의 수 돌면서 이동시켜 봄.
for way in list(product(*ways)):
    new_matrix = matrix
    for each_way in way:
        if each_way == 'u':
            new_matrix = up_down_movement(1, new_matrix)
        elif each_way == 'd':
            new_matrix = up_down_movement(2, new_matrix)
        elif each_way == 'l':
            new_matrix = left_right_movement(1, new_matrix)
        elif each_way == 'r':
            new_matrix = left_right_movement(2, new_matrix)
        answer = max(answer, get_max(new_matrix))

print(answer)