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

https://programmers.co.kr/learn/courses/30/lessons/86491?language=python3 

풀이 과정

1. 지갑 크기를 명함 크기들과 순차적으로 비교하면서 갱신해 나간다.
   1. 기존 지갑 크기보다 명함의 크기가 더 크다면 갱신하는 방식
   2. 명함을 가로 방향과 세로 방향으로 집어넣을수 있으므로 각각의 케이스에 맞추어서 지갑의 크기를 갱신해 보고 지갑이 최소 넓이가 되는 경우로 지갑의 크기를 갱신시켜 준다.
2. 최종적으로 갱신된 지갑의 넓이를 리턴해주면 된다.

소스 코드

def solution(sizes):
    answer = 0
    
    card_w = 0
    card_h = 0
    for w, h in sizes:
        temp_w1, temp_h1 = max(w, card_w), max(h, card_h)
        temp_w2, temp_h2 = max(w, card_h), max(h, card_w)
        
        if temp_w1 * temp_h1 < temp_w2 * temp_h2:
            card_w, card_h = temp_w1, temp_h1
        else:
            card_w, card_h = temp_w2, temp_h2
    
    answer = card_w * card_h
    return answer

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

풀이 과정

1. 문제를 잘 읽어봐야 한다. 한번 기울이게 되면 빨간공이랑 파란공 둘다 벽에 부딪히거나 구멍에 들어갈때까지 그 방향 끝까지 가야 함.
2. 두개의 공 모두 벽이나 구멍을 만날때까지, 혹은 공끼리 부딪힐때까지 파란공과 빨간공을 네가지 방향으로 이동시켜 본다. (위, 아래, 왼쪽, 오른쪽)
   1. 이 때, 빨간공이 구멍에 들어가고, 파란공이 구멍에 들어가지 않는다면 정답이므로 이동 거리를 출력한다.
   2. 파란공이 구멍에 들어가게 되면 틀린것이므로 해당 방향으로 이동한 케이스는 큐에 삽입하지 않는다.
   3. 공이 부딪히게 되는 경우, 공의 위치를 잘 조정해주어야 한다. - 이부분 틀려서 시간 오래 걸림.
3. 두개의 구멍 모두 들어가는 케이스는 정답이 아닌 것이므로 해당 케이스도 큐에 삽입하지 않는다.
4. 이동거리가 11 이상인 경우 -1 출력하고, 나머지 경우 이동거리를 출력시켜 준다.

소스 코드

import sys
from collections import deque

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

N, M = map(int, input().split())

matrix = [list(input()) for _ in range(N)]

b_pos = [0, 0]
r_pos = [0, 0]
for i in range(N):
    for j in range(M):
        if matrix[i][j] == 'B':
            b_pos[0], b_pos[1] = i, j
            matrix[i][j] = '.'
        if matrix[i][j] == 'R':
            r_pos[0], r_pos[1] = i, j
            matrix[i][j] = '.'

def bfs(matrix, bpos, rpos):
    queue = deque([[bpos[0], bpos[1], rpos[0], rpos[1], 1]])
    N, M = len(matrix), len(matrix[0])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    visited = set([(bpos[0], bpos[1], rpos[0], rpos[1])])
    while queue:
        b_x, b_y, r_x, r_y, cost = queue.popleft()
        b_pos,r_pos = [b_x, b_y], [r_x, r_y]
        if cost == 11:
            break
        for i in range(4):
            bx, by = b_pos
            rx, ry = r_pos
            b_finish, r_finish = False, False
            b_end, r_end = False, False
            while True:
                # 벽을 만날때까지 파란 공 이동
                if matrix[bx + dx[i]][by + dy[i]] != '#':
                    bx, by = bx + dx[i], by + dy[i]
                else:
                    b_end = True

                # 벽을 만나거나 구멍을 만날때까지 빨간 공 이동
                if matrix[rx + dx[i]][ry + dy[i]] != '#' and not r_finish:
                    rx, ry = rx + dx[i], ry + dy[i]
                else:
                    r_end = True

                # 빨간공과 파란공이 만났을 때
                if rx == bx and ry == by:
                    if r_finish: # 빨간색이 구멍에 들어간 경우 파란공도 들어가는 것
                        b_finish = True
                    # 이미 빨간공이 멈춰선 경우 파란공 위치 조정
                    if r_end:
                        bx, by = bx - dx[i], by - dy[i]
                    # 이미 파란공이 멈춰선 경우 빨간공 위치 조정
                    elif b_end:
                        rx, ry = rx - dx[i], ry - dy[i]
                    break

                # 파란공이 구멍에 들어간 경우 finish 처리
                if matrix[bx][by] == 'O':
                    b_finish = True
                    break
                
                # 빨간공이 구멍에 들어간 경우 finish 처리
                if matrix[rx][ry] == 'O':
                    r_finish = True

                # 둘다 벽을 만난 경우 종료
                if b_end and r_end:
                    break
                
            # 빨간공은 들어가고 파란공은 들어가지 않은 경우 거리 리턴
            if r_finish and not b_finish:
                return cost

            # set에 방문기록 저장 (재방문하지 않도록)
            if (bx, by, rx, ry) not in visited and not b_finish:
                visited.add((bx, by, rx, ry))
                queue.append([bx, by, rx, ry, cost+1])

    return -1

print(bfs(matrix, b_pos, r_pos))

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

풀이 과정

1. 최대 집하장의 개수가 200개이기도 하고, 각각의 집하장에서 가장 먼저 거쳐야 하는 집하장을 구해야 하므로 다익스트라 알고리즘보다는 플로이드 알고리즘이 더 괜찮아 보인다.
2. 최단 경로를 구하는 것이 아닌, 어디를 거쳐야 하는지를 구해야 하므로, 플로이드 알고리즘으로 거리를 갱신하면서 갱신할때 거치는 노드를 따로 저장해 둔다.
3. 마지막으로, 플로이드 알고리즘을 사용하면 가장 마지막에 거쳐가는 노드를 저장하므로, 이를 타고 올라가서 가장 먼저 거쳐야 하는 집하장을 구하여 저장해 둔다.
4. 저장해 둔 전체 경로표를 출력시켜 준다.

소스 코드

import sys

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

INT_MAX = int(10e9)
n, m = map(int, input().split())

matrix = [[INT_MAX] * (n+1) for _ in range(n+1)]
answer = [[0] * (n+1) for _ in range(n+1)]
for i in range(n+1):
    matrix[i][i] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    matrix[a][b] = min(matrix[a][b], c)
    matrix[b][a] = min(matrix[b][a], c)
    answer[a][b] = b
    answer[b][a] = a


# 최단거리 구하는 파트
# 최단거리 구하면서 거리 갱신 시 어느 노드를 들리는지 정보 저장
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            if matrix[j][k] > matrix[j][i] + matrix[i][k]:
                matrix[j][k] = matrix[j][i] + matrix[i][k]
                answer[j][k] = i

# 다른 노드를 들리게 되는 경우,
# 거슬러 올라가서 가장 먼저 거쳐야 하는 집하장으로 바꾸어 줌
for i in range(1, n+1):
    for j in range(1, n+1):
        if answer[i][j] == 0:
            answer[i][j] = '-'
            continue
        p = answer[i][j]
        while p != answer[i][p]:
            p = answer[i][p]
        answer[i][j] = p

for a in answer[1:]:
    print(*a[1:])

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

풀이 과정

1. 일반적인 BFS 문제들과 비슷
   • 현재 0의 위치가 X,Y라고 할 때, 0의 위치로 이동할 수 있는 점은 (X-1,Y)에서, (X, Y-1)에서, (X+1, Y)에서, (X, Y+1)에서 총 네가지 경우라고 볼 수 있음. 물론 배열의 범위를 벗어나게 되는 경우는 제외해야 함.
2. 어려웠던 점은.. 메모리 초과 문제
   • 한번 방문했던 지점을 다시 방문하지 않도록 하기 위해 저장을 해야 하는데, 방문한 2차원 배열을 그대로 저장하면 메모리 초과 문제가 나타남.
   • 따라서, 방문 기록과 큐에 저장할 때 문자열 형태로 저장, 예시로 [[1,2,3], [4,5,6], [7,8,0]]인 경우, 123456780으로 저장한 다음, 큐에서 꺼낼 때 다시 2차원 배열 형태로 바꿔줌.
3. 데이터를 저장할 때는 메모리를 최대한 아끼는 쪽으로 저장해야 됨.

소스 코드

import sys
import copy
from collections import deque

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

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

def find_0(matrix):
    for i in range(3):
        for j in range(3):
            if matrix[i][j] == 0:
                return [i, j]
    return None

def check_finish(matrix):
    answer = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
    for i in range(3):
        for j in range(3):
            if answer[i][j] != matrix[i][j]:
                return False
    return True

def atos(matrix):
    result = ''
    for i in range(3):
        for j in range(3):
            result += str(matrix[i][j])
    return result

def stoa(string):
    return [[int(string[3*i+j]) for j in range(3)] for i in range(3)]

def bfs(matrix):
    visited = set([atos(matrix)])
    queue = deque()
    queue.append([atos(matrix), 0])
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    while queue:
        mat, movement = queue.popleft()
        mat = stoa(mat)
        if check_finish(mat):
            return movement
        x, y = find_0(mat)
        for i in range(4):
            target_x = x + dx[i]
            target_y = y + dy[i]
            if target_x >= 0 and target_x < 3 and target_y >= 0 and target_y < 3:
                mat[x][y], mat[target_x][target_y] = mat[target_x][target_y], mat[x][y]
                if atos(mat) not in visited:
                    visited.add(atos(mat))
                    queue.append([atos(mat), movement+1])
                mat[x][y], mat[target_x][target_y] = mat[target_x][target_y], mat[x][y]
    
    return -1

print(bfs(matrix))

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

풀이 과정

• 이전 문제랑 크게 다르지 않은듯 하면서 많이 다른 문제.. split을 쓰는것보다는 직접 진행하는것이 훨씬 쉽게 풀었던 것 같음.. 이전 문제가 더 쉬웠는데 왜 이번 문제가 정답률이 높지??..

1. 왼쪽에서 진행하면서 '<' 문자를 만났을 때와 안만났을 때로 구분한다.
   • '<' 문자를 만났을 때
     • 이전 스택에 저장되어있던 문자를 모두 pop해주면서 저장 (이전 문자는 뒤집힘)
     • 문자를 그대로 저장
   • '<' 문자를 만나지 않았을 때
     • 문자를 스택에 저장
2. 공백을 만나게 되면(' ')
   • '<>' 내부라면 그냥 저장해주면 된다.
   • '<>' 내부가 아니라면 공백을 만나기 전까지 스택에 저장된 문자들을 모두 pop해주면서 저장하고, 공백을 뒤에 붙여준다.
3. 맨 마지막에, 스택에 문자가 남아있다면 모두 pop해준 다음 저장해둔다.
4. 저장해둔 문자를 출력한다.

소스 코드

import sys

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

sentence = input()
stack = []
skip = False
answer = ''
for ch in sentence:
    if ch == '<':
        while stack:
            answer += stack.pop()
        skip = True
    elif ch == '>':
        answer += '>'
        skip = False
        continue

    if skip:
        answer += ch
    else:
        if ch == ' ':
            while stack:
                answer += stack.pop()
            answer += ch
        else:
            stack.append(ch)

while stack:
    answer += stack.pop()

print(answer)

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

풀이 과정

1. 입력받은 문장을 공백 기준으로 단어별로 쪼갠다.
2. 각 단어별로 진행하면서 알파벳을 순서대로 스택에 넣는다
3. 다시 스택에서 빼주면 알파벳이 뒤집어진 단어가 나온다.
4. 단어들을 붙여서 출력해주면 된다.

소스 코드

import sys

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

T = int(input())
for _ in range(T):
    sentence = input().split()
    stack = []
    for word in sentence:
        convert = ''
        for ch in word:
            stack.append(ch)
        while stack:
            print(stack.pop(), end="")
        print(" ", end="")
    print()

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

풀이 과정

1. 문제를 간단하게 생각하면 이진 탐색으로 위치를 찾으면 왼쪽 구간의 요소의 개수가 바로 먹을수 있는 수이다. 
   • 즉, 이진 탐색 결과가 곧 개수이다.
2. A의 각각의 요소들을 리스트 B에 대해서 이진탐색 진행
   • 같은 경우 왼쪽 구간 진행(같아도 안되므로)
   • 파이썬의 bisect_left 함수 사용
3. 요소의 개수의 합을 출력해주면 된다.

소스 코드

import sys
from bisect import bisect_left

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

T = int(input())

for _ in range(T):
    A, B = map(int, input().split())
    T1 = sorted(map(int, input().split()))
    T2 = sorted(map(int, input().split()))
    count = 0
    for e1 in T1:
        pos = bisect_left(T2, e1)
        count += pos
    print(count)

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

풀이 과정

1. 오목판의 왼쪽 위에서 아래쪽으로 진행하면서 전체 경우의 수를 탐색하면 된다.
   • 왼쪽 위에서 아래로 진행하므로, 위쪽 방향으로는 조사할 필요 없이 아래 방향으로만 조사하면 된다.
2. 단, 6개 이상의 돌이 연속으로 있는 경우는 안되므로 (0, 0)에서 (5, 5)까지 6개가 있는걸 (1, 1)에서부터 시작해서 (5, 5)까지 5개가 있는걸로 잘못 처리되는걸 방지하기 위해 visited 배열을 따로 둔다.
   • visited 배열의 경우는 [19][19][4] 형식으로 구성. 4는 왼쪽아래 대각, 아래, 오른쪽아래 대각, 오른쪽 총 4개의 방향으로 방문 가능하므로 3차원 배열로 구성
   • 이미 방문한 경우는 재방문하지 않도록 처리
3. 전체 경우의 수를 돌면서 오목인 경우, 해당 위치와 돌의 종류를 출력시켜주면 된다.
   • 예외사항으로, 왼쪽아래 대각 방향이 정답인 경우는 가장 왼쪽 돌을 출력해주라고 하였으므로 현재 위치 기준 x+4, y-4 해주면 된다.

소스 코드

import sys

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

matrix = [list(map(int, input().split())) for _ in range(19)]
visited = [[[False] * 4 for _ in range(19)] for _ in range(19)]

def check(matrix, visited, x, y):
    direction = [[1, -1], [1, 0], [0, 1], [1, 1]]
    p = matrix[x][y]

    for idx, d in enumerate(direction):
        temp_x, temp_y = x, y
        if visited[temp_x][temp_y][idx]:
            continue
        visited[temp_x][temp_y][idx] = True
        count = 1
        while True:
            temp_x, temp_y = temp_x + d[0], temp_y + d[1]
            if 0 <= temp_x and temp_x < 19 and 0 <= temp_y and temp_y < 19:
                if matrix[temp_x][temp_y] == p:
                    visited[temp_x][temp_y][idx] = True
                    count += 1
                else:
                    break
            else:
                break
            if count >= 6:
                break

        if count == 5:
            if d[0] == 1 and d[1] == -1:
                return [x+4, y-4]
            return [x, y]
        
    return None

end = False
for i in range(len(matrix)):
    for j in range(len(matrix)):
        if matrix[i][j] != 0:
            result = check(matrix, visited, i, j)
            if result is not None:
                i, j = result
                print(matrix[i][j])
                print(i+1, j+1)
                end = True
        if end:
            break
    if end:
        break

if not end:
    print(0)

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

풀이 과정

1. 방으로 셀수있는 경우의 수는 두가지이다.

   • 대각선끼리 교차하는 경우
   • 지나가지 않은 간선으로 이미 방문한 노드를 다시 방문하게 될 때

2. 각각의 경우에 맞추어서 대각선끼리 교차할 때와 재방문할때 방의 개수를 하나씩 늘려주면 된다.

3. 여기서 해맸던 점이.. 한방향 방문 처리만 해주어서 다른 방향으로 다시 방문할때 방의 개수가 계속 늘어나게 되는 문제가 있었다.

   • 따라서, (a,b) -> (c,d)로 진행한다면, (c,d) -> (a,b)도 방문처리 해주어야 함.

소스 코드

def movement(x, y, arrow):
    if arrow == 7:
        x += 1
        y -= 1
    if arrow == 6:
        y -= 1
    if arrow == 5:
        x -= 1
        y -= 1
    if arrow == 4:
        x -= 1
    if arrow == 3:
        x -= 1
        y += 1
    if arrow == 2:
        y += 1
    if arrow == 1:
        x += 1
        y += 1
    if arrow == 0:
        x += 1
    return x, y

def cross_check(edge, x, y, arrow):
    if arrow == 1:
        if (x, y+1, x+1, y) in edge or (x+1, y, x, y+1) in edge:
            return True
    elif arrow == 5:
        if (x, y-1, x-1, y) in edge or (x-1, y, x, y-1) in edge:
            return True
    elif arrow == 7:
        if (x, y-1, x+1, y) in edge or (x+1, y, x, y-1) in edge:
            return True
    elif arrow == 3:
        if (x-1, y, x, y+1) in edge or (x, y+1, x-1, y) in edge:
            return True

    return False


def solution(arrows):
    answer = 0
    visited = set()
    edge = set()
    x, y = 0, 0
    visited.add((x, y))
    for arrow in arrows:
        currentX, currentY = x, y
        x, y = movement(x, y, arrow)

        # 교차하는 대각선 여부 확인
        if arrow in [1, 3, 5, 7] and cross_check(edge, currentX, currentY, arrow):
            if (x, y, currentX, currentY) not in edge: 
                answer += 1

        if (x, y) in visited:
            # 반대로 돌아오는 간선 있는지 체크
            if (x, y, currentX, currentY) not in edge: 
                answer += 1
        else:
            visited.add((x, y))

        # 현재 간선정보 저장
        edge.add((currentX, currentY, x, y))
        edge.add((x, y, currentX, currentY))
    return answer

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

풀이 과정

1. 수열의 왼쪽에서부터 순차적으로 진행한다.

   • 현재의 숫자가 존재하지 않는다면 큐에 넣어준다.
   • 현재의 숫자가 큐에 존재한다면, 현재 숫자가 나올때 까지 큐에서 빼내준 다음 현재 숫자를 넣는다.

2. 현재 큐의 길이를 따로 저장해 둔다.

   • 이유는 현재 숫자가 5고, 큐에 [2, 3, 5]가 들어있다면 경우의 수는 [2, 3, 5], [3, 5], [5] 3가지 즉, 큐의 길이만큼의 경우의 수가 나올 수 있다.

3. 저장해둔 큐의 길이의 합계를 출력해주면 된다

   • 전체 경우의 수를 구해야 하므로

소스 코드

import sys
from collections import deque

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

n = int(input())
sequence = list(map(int, input().split()))

dp = [0] * len(sequence)
queue = deque()
current = set()
for i in range(len(sequence)):
    if sequence[i] in current:
        while queue:
            pos, value = queue.popleft()
            current.remove(value)
            if value == sequence[i]:
                break
    queue.append([i, sequence[i]])
    current.add(sequence[i])

    dp[i] = len(current)

print(sum(dp))