둔필승총

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

[나의 문제 분석]

제일 먼저 생각한것은 stack구조였다. 알파벳이 하나씩 나오다가 연산자를 맞닥뜨리면 그때 연산자와 맨 마지막에 들어간 알파벳 2개를 서로 연산해주면 된다고 생각했다. 로직은 간단했는데 내가 부족한 스킬이 몇개가 있었다. 첫번째는 알파벳을 입력받은 배열의 숫자로 어떻게 바꾸어주냐에 관련한 것이였고, 두번째는 정답을 출력할때 소수 2번째까지 출력해주어야하는데 기억이 안나서 살짝 헤매었다. 

1. 알파벳 입력을 숫자로 바꾸어주는것은 일반 nums라는 배열에 0을 저장해두고 알파벳을 확인할때 해당 nums의 index에 맞는 숫자를 출력해주면 된다. 

    if a.isupper():
        s.append(nums[ord(a)-ord('A')])

이 코드처럼 a가 대문자임을 if문으로 확인하고, nums배열에서 A가 0번째, B가 1번째,... 이런식으로 가니까 만약 A라면 ord(a) - ord('A')는 0이되므로 nums의 첫번째에 해당하는 것이 나오게 된다. B,C,D도 마찬가지이다.

2. 소수 2번째까지 출력해주는 방법은 파이썬에서 여러가지가 있다. 

- 내가 사용한것은 format 서식 지정으로 소수점을 관리하였다. 

print("{:.nf}".format(number)) 로 number의 소수점 n+1번째 자릿수에서 반올림해서 소수점 n번째 자릿수까지 출력함으로써 소수점을 관리할 수 있다.

- f-string에서 소수점 관리

: print(f"{number:.nf}")로 number의 소수점 n+1번째 자릿수에서 반올림해서 소수점 n번째 자릿수까지 출력한다.

- %.?f

print('%.nf' %number)로 number의 소수점 n+1번째 자릿수에서 반올림해서 소수점 n번째 자릿수까지 출력한다.

[나의 해결 방안]

n = int(input())
sen = input()
s=[]
nums=[0]*n
for i in range(n):
    nums[i]=int(input())
for a in sen:
    if a.isupper():
        s.append(nums[ord(a)-ord('A')])
    elif a=='+':
        one = s.pop()
        two = s.pop()
        s.append(two+one)
    elif a=='-':
        one = s.pop()
        two = s.pop()
        s.append(two-one)
    elif a=='*':
        one = s.pop()
        two = s.pop()
        s.append(two*one)
    elif a=='/':
        one = s.pop()
        two = s.pop()
        s.append(two/one)
print("{:.2f}".format(s[0]))

[다른 사람 풀이]

조금 어지럽게 푼 느낌이 있어서 다른 사람들 풀이도 찾아보았다. 

https://velog.io/@dailyhyun/BOJ%EB%B0%B1%EC%A4%80-1935.-%ED%9B%84%EC%9C%84%ED%91%9C%EA%B8%B0%EC%8B%9D2

기본적인 로직은 비슷하였고 대문자임을 판단하는 방식을 

if 'A' <= i <= 'Z': 로 하였다. 나머지는 비슷한것 같다.

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

나의 문제 분석

문제 자체는 이해하기 단순했다. 그냥 k번째 수를 계속 빼서 정답 배열에 넣어서 출력하면 되는 것이었다. 나는 덱을 사용하여서 왼쪽에서 k-1번째까지 빼고 뒤에 다시 넣고 k번째 뺀것은 answer 배열에 넣어서 n번 반복하였다. 그리고 answer를 출력해주었다. 

나의 해결 방안

#(n,k) - 요세푸스 순열
from collections import deque
n,k = map(int,input().split())
answer = []
q1=deque([])
for i in range(n):
    q1.append(i+1)
for _ in range(n):
    for _ in range(k-1):
        num = q1.popleft()
        q1.append(num)
    num = q1.popleft()
    answer.append(num)
print("<",end='')
for i in range(n-1):
    print(answer[i],end=', ')
print(answer[n-1],end='>')

중간중간 deque의 사용방법이 걸려서 찾아보면서 해결하였다.

다른 사람 풀이

사실 deque로 푸는 것보다 queue로 푼 해설을 찾아보고 싶었다. 파이썬에서는 list자체가 queue이기 때문에 간단하게 풀 수 있을 거라고 생각했다. 

아래 풀이를 참고했다.

https://infinitt.tistory.com/213

여기서는 arr을 처음에 앉아있는 사람들 배열로 저장해주었고 제거될 사람을 num 변수로 계산하였다. 내가 처음에 고민했던 부분은 나중에 k보다 사람이 적었을때 한바퀴 돌고 다시 돌아와야된다는 점을 어떻게 해결할지 고민이였다. 

여기서는 num이 arr의 길이보다 크면 num = num % len(arr)을 통해서 num의 값을 맞춰주었다. 

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

[문제 풀이]

문제에서 주어진 알고리즘대로 진행하면 된다. 

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
 4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
 4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
 4-3. ')'를 다시 붙입니다.
 4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
 4-5. 생성된 문자열을 반환합니다.

1번부터 보면 빈 문자열은 빈 문자열 반환하면 된다. p가 빈 문자열이면 그대로 return한다.

2번은 u와 v로 분리해야 한다. u와 v로 분리하기위해 sep(p) 함수를 만들었다. '(' 괄호와 ')' 괄호의 수가 같을 때, 그 지점까지를 u에 넣고 그 뒤에 부분을 v에 넣는다.

3번은 u가 '올바른 괄호 문자열'인지 확인해야 한다. 이를 위해 check(p) 함수를 만들었다. 올바른 괄호 문자열이면 True, 아니면 False를 반환하도록 하였다. 

4번은 재귀적으로 해결하면 된다. 4-4 부분이 해석하기가 어려웠다. 먼저 u를 u[1:-1]로 저장하여 첫번째와 마지막 원소를 떼어낸다. 그리고 괄호방향을 뒤집기 위해 reverse함수를 만들어서 '(' 모양은 ')' 모양으로 ')'모양은 '('모양으로 바꾸어주었다. 

def solution(p):
    answer = ''
    if p == '':
        return p
    if check(p):
        return p
    u=sep(p)[0]
    v=sep(p)[1]
    if check(u):
        return u+solution(v)
    else:
        answer+='('
        answer+=solution(v)
        answer+=')'
        u=u[1:-1]
        for i in reverse(u):
            answer+=i
        return answer


def check(p):
    x = y = 0
    for i in range(len(p)):
        if p[i] == '(':
            x += 1
        elif p[i] == ')':
            y += 1
        if x < y:
            return False
    return True


def sep(p):
    x = y = 0
    num = 0
    u = ''
    v = ''
    while True:
        if p[num] == '(':
            x += 1
        elif p[num] == ')':
            y += 1
        num += 1
        if x == y:
            for i in range(num):
                u += p[i]
            for j in range(num, len(p)):
                v += p[j]
            break
    return u,v
def reverse(strings):
    r = {"(":")", ")": "("}
    return [r[s] for s in strings]

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

[문제 풀이]

처음에 많이 헤맸었다. 먼저 BFS를 최대한 활용하려고 했었는데 사실 활용하려고 한 게 더 복잡하게 이끌어 간 것 같다. 

이 문제는 s라는 변수에 시간이 주어지고 그 시간때에 위치를 출력하면 되는 문제이기 때문에 BFS를 활용하기 보다는 s만큼 움직여주고 그때의 값을 출력해주는 것이 더 편했다. queue를 만들어줘서 바이러스가 작은 순으로 저장해주고 각각의 바이러스를 꺼내어 상하좌우를 탐색하였다. 

from collections import deque
n,k = map(int,input().split())
graph=[] # n*n
for i in range(n):
    graph.append(list(map(int,input().split())))
s,u,v = map(int,input().split())
# s초 뒤에 (u,v)에 존재하는 바이러스의 종류 출력 -> 밑에서 x,y를 사용해서 u,v로 바꿈
dx=[-1,1,0,0]
dy=[0,0,1,-1]
q=deque()
for a in range(1,k+1):
    for i in range(n):
        for j in range(n):
            if graph[i][j]==a:
                q.append((i,j))
# print(q.popleft())
for _ in range(s):
    for _ in range(len(q)):
        x,y=q.popleft()
        num = graph[x][y]
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<n and ny>=0 and ny<n and graph[nx][ny]==0:
                graph[nx][ny]=num
                q.append((nx,ny))
print(graph[u-1][v-1])

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

1.

처음에 풀었을 때 BFS로 미로찾기와 비슷하게 풀었는데 메모리 초과가 생겼다. 

from collections import deque
import sys
input = sys.stdin.readline
n,m,k,x = map(int,input().split())
#도시의 개수 n, 도로의 개수 m, 거리 정보 k, 출발 도시의 번호 x
graph=[[0]*(n+1) for _ in range(n+1)]
distance=[99999]*(n+1)
visited=[False]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    graph[a][b]=1

def bfs(v):
    q=deque([v])
    distance[v]=0
    while q:
        x = q.popleft()
        for i in range(1,n+1):
            if graph[x][i]==1:
                q.append(i)
                distance[i]=min(distance[x]+1,distance[i])
bfs(x)
answer=[]
for i in range(len(distance)):
    if distance[i]==k:
        answer.append(i)
if len(answer)==0:
    print(-1)
else:
    for i in range(len(answer)):
        print(answer[i])

거리가 K인 것만 출력하면 된다는 사실과 graph를 통해 모든 지점을 탐색할 필요는 없다는 점을 통해 메모리 초과를 해결할 수 있었다.

2.

모든 도로의 거리는 1이다. 너비 우선 탐색을 이용하여 해결할 수 있다. 앞서 미로찾기와 같이 이동할 때의 거리는 +1하면서 해결할 수 있다. 문제의 조건에서 노드의 개수 N은 최대 300000개, 도로의 개수 M은 최대 1000000개이다. 따라서 BFS를 사용하여 시간 복잡도 O(N+M)으로 작동하는 소스코드를 작성하여 해결할 수 있다.

from collections import deque
n,m,k,x = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
distance = [-1]*(n+1)
distance[x]=0

q=deque([x])
while q:
    now = q.popleft()
    for next_node in graph[now]:
        if distance[next_node]==-1:
            distance[next_node]=distance[now]+1
            q.append(next_node)
check = False
for i in range(1,n+1):
    if distance[i]==k:
        print(i)
        check = True
if check==False:
    print(-1)

3.

다익스트라 알고리즘이 유용하게 쓰이진 않지만 그 틀을 사용해서 풀었다.

import sys
input = sys.stdin.readline
from collections import deque

n,m,k,x = map(int,input().split())
visited = [False]*(n+1)
graph = [[] for _ in range(n+1)]
answer=[]

for _ in range(m):
    i,j = map(int,input().split())
    graph[i].append(j)

queue=deque()
queue.append((x,0))
visited[x]=True

while queue:
    v,dist=queue.popleft()
    if dist == k:
        answer.append(v)
    elif dist<k:
        for i in graph[v]:
            if not visited[i]:
                visited[i]=True
                queue.append((i,dist+1))

if len(answer)==0:
    print(-1)
else:
    answer.sort()
    for i in range(len(answer)):
        print(answer[i])

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

[문제 풀이]

(1,1)에서 출발하여 (N,M)까지 가는 길 중 최소의 칸 수를 가야하는 길을 구해야 한다. 이 문제는 1인 영역만 일단 지나도록 설계한다. 1인 지역을 지나갈때 그 전의 지역의 graph 수에서 1을 추가해준다. 그렇게 하면 graph의 (N,M) 좌표를 출력하면 몇게의 길을 지나왔는지 알 수 있다. 나는 BFS를 통해 풀었다.

from collections import deque
n,m = map(int,input().split())
graph=[]
for i in range(n):
    graph.append(list(map(int,input())))
def bfs(a,b):
    q=deque()
    q.append((a,b))
    dx=[-1,1,0,0]
    dy=[0,0,1,-1]
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx>=0 and nx<n and ny>=0 and ny<m and graph[nx][ny]==1:
                q.append((nx,ny))
                graph[nx][ny]=graph[x][y]+1
bfs(0,0)
print(graph[n-1][m-1])

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

from collections import deque
import sys
input = sys.stdin.readline
q=deque()
n= int(input())
for i in range(n):
    question = input().split()
    if len(question)==2:
        order = question[0]
        number = int(question[1])
        q.append(number)
    else:
        if question[0]=='pop':
            if len(q)==0:
                print(-1)
            else:
                print(q.popleft())
        elif question[0]=='size':
            print(len(q))
        elif question[0]=='empty':
            if len(q)==0:
                print(1)
            else:print(0)
        elif question[0]=='front':
            if len(q)==0:
                print(-1)
            else:
                print(q[0])
        elif question[0]=='back':
            if len(q)==0:
                print(-1)
            else:
                print(q[-1])

기본적으로 큐를 구현하여 푸는 문제이다. 큐의 다양한 기능들을 조건문을 통하여 해결하였다.

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

import sys
input = sys.stdin.readline
from collections import deque

q=deque()
n=int(input())
for i in range(n):
    question = input().split()
    if len(question)==2:
        order=question[0]
        number=question[1]
        if order=='push_front':
            q.appendleft(number)
        elif order=='push_back':
            q.append(number)
    else:
        if question[0]=='pop_front':
            if q:
                print(q.popleft())
            else:
                print(-1)
        elif question[0]=='pop_back':
            if q:
                print(q.pop())
            else:
                print(-1)
        elif question[0]=='size':
            print(len(q))
        elif question[0]=='empty':
            if q:
                print(0)
            else:
                print(1)
        elif question[0]=='front':
            if q:
                print(q[0])
            else:
                print(-1)
        elif question[0]=='back':
            if q:
                print(q[-1])
            else:
                print(-1)

10845와 같이 deque를 사용하여서 문제를 해결하였다.

위에 두 문제에서 핵심은 input()대신 sys.stdin.readline()을 사용하여야 된다는 것이다.

반복문으로 여러줄을 입력 받아야 할 때 input()은 시간초과를 일으킬 수 있다.

# ) sys.stdin.readline()은 한줄 단위로 입력받기 때문에, enter가 같이 입력이된다.

# ) strip()은 문자열 맨 앞과 맨 끝의 공백문자를 제거한다.

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

[문제 풀이]

이 문제는 위에 두 문제와 비슷하다고 생각하고 쉽게 풀려고 했는데 잘 풀리지 않았다. 먼저 위에 두 문제처럼 풀었다.

from collections import deque
import sys
input = sys.stdin.readline
q=deque()
str = input()
for i in range(len(str)):
    q.append(str[i])
m=int(input())
cursor=len(q)
for i in range(m):
    question=input().split()
    if len(question)==2:
        number=question[1]
        q.insert(cursor,number)
        cursor+=1
    else:
        if question[0]=='L':
            if cursor!=0:
                cursor-=1
        elif question[0]=='D':
            if cursor!=len(q):
                cursor+=1
        elif question[0]=='B':
            if cursor!=0:
                q = list(q)
                q.pop(cursor-1)
                q=deque(q)
                cursor-=1
for i in range(len(q)):
    print(q[i],end='')

위에 방식대로 풀려고 했는데 시간초과, 런타임에러(TypeError)같은 에러가 계속 났다. 시간 초과를 해결하는 것이 이 문제의 핵심이라 생각했다. 문제를 보면 시간제한이 다른 문제보다 적다.

input도 sys.stdin.readline으로 바꿔도 보고, 내가 할 수 있는 일들을 해봤지만 시간초과는 계속 났다. 그리고 입력 부분을 다시 봤다.

내가 푼 방식으로는 문자열의 길이가 N일때 O(N)의 시간복잡도가 발생한다. 그렇다면 최악의 경우 100,000길이인 문자열을 500,000번 다루면 100,000 X 500,000 번의 연산이 필요하게 된다. M을 줄이기보다 문자열 통째로 연산하는 것을 부분적으로 할 수 있도록 줄여봐야 된다고 생각했다.

https://bnzn2426.tistory.com/112

여기서 많은 도움을 받게 되었다. 

두 개의 스택을 이용해 커서의 앞 부분과 커서의 뒷 부분을 구분하여 생각한다.

먼저 첫번째 스택에 모두 들어가고 두번째 스택은 비어있다. 만약 L을 입력받아 커서가 왼쪽으로 움직인다면 첫번째 스택은 pop을 통해 꺼내고 두번째 스택에 push되는 것이다. 

반대로 D를 입력받으면 첫번째 스택에 push, 두번째 스택에서 pop을 하는 것이다. 

from sys import stdin
input = stdin.readline
first = list(stdin.readline().strip())
second = []
m= int(input())
for i in range(m):
    question=input().split()
    if question[0]=='L':
        if first: #첫번째 스택이 존재할때 (없으면 더 왼쪽으로 커서가 못가니까)
            second.append(first.pop())
    elif question[0]=='D':
        if second:
            first.append(second.pop())
    elif question[0]=='B':
        if first:
            first.pop()
    elif question[0]=='P':
        first.append(question[1])
print("".join(first+list(reversed(second))))

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

문제

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

출력

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산해서 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

예제 입력 1 

5 3 1
0 -1 0 0 0
-1 -1 0 1 1
0 0 0 1 1

예제 출력 1 

-1

예제 입력 2 

5 3 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0

예제 출력 2 

4

예제 입력 3 

4 3 2
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
-1 -1 -1 -1
1 1 1 -1

예제 출력 3 

0

[문제 풀이]

먼저 이전에 풀었던 토마토 2차원 문제에서 이 문제는 3차원 문제로 업그레이드 되었다. 3차원 배열을 입력받는 부분은 예제의 입력에서 힌트를 얻었다. h만큼 덩어리가 생기므로 m은 list로 해서 입력받고 그 입력 받은 리스트를 range(n)으로 for문 한 번, range(h)로 for문 한 번 사용해서 입력받는다. (입력받은걸 확인하기 위해 매번 print()사용한다..)

데큐를 사용해서 bfs를 이용하겠다. 일단 익은 것들이 하루에 다른 덜익은 토마토를 익히는 건 범위의 한계가 있다. 하루에 상하좌우해서 1칸씩 밖에 안된다. 우리가 원래 사용하던 bfs를 변형시키면 된다. 

먼저 처음에 주어진 토마토 박스에서 익은 것들을 q에 저장해준다.(q는 deque()로 만든 것이다) 그리고 q에 들어간 값들의 개수를 count에 저장한다. (count=len(q)) 그리고 dx,dy,dz를 count만큼만 해주면 그날 하루하루 익은 것들만 0에서 1로 바꿀 수 있다.

나머지 조건들도 (처음부터 다익은 경우, 시간이 아무리 지나도 안익는 것 존재하는 경우)들도 처리해준다.

from collections import deque
m,n,h = map(int,input().split())
#tomato[h][n][m]
tomato=[[list(map(int,input().split())) for _ in range(n)] for _ in range(h)]
#print(tomato)
q=deque()
for i in range(h):
    for j in range(n):
        for k in range(m):
            if tomato[i][j][k]==1:
                q.append((i,j,k))
day=0
while q:
    count=len(q)
    dx=[-1,1,0,0,0,0]
    dy=[0,0,-1,1,0,0]
    dz=[0,0,0,0,-1,1]
    day += 1
    for _ in range(count):
        z, y, x = q.popleft()
        for i in range(6):
            nx = x+dx[i]
            ny = y+dy[i]
            nz = z+dz[i]
            if 0<=nz<h and 0<=ny<n and 0<=nx<m and tomato[nz][ny][nx]==0:
                q.append((nz,ny,nx))
                tomato[nz][ny][nx]=1
            else:
                continue
for i in range(h):
    for j in range(n):
        for k in range(m):
            if tomato[i][j][k]==0:
                print(-1)
                exit(0)
print(day-1)