이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다.
평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.
입력
첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)
다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.
출력
첫째 줄에 좋은 단어의 수를 출력한다.
예제 입력과 출력
알고리즘 분류
스택 문자열 처리
정답
from collections import deque
import sys
input = lambda : sys.stdin.readline().strip()
n=int(input())
a=[list(input()) for i in range(n)]
c= 0
for i in a:
li=deque()
for j in i:
if len(li) == 0:
li.append(j)
elif len(li) >= 1:
if li[-1] == j:
li.pop()
else:
li.append(j)
if len(li) == 0:
c +=1
print(c)
1. 첫번째 알파벳을 덱 li에 넣습니다. 2. 스택 맨 위의 알파벳과 넣을 알파벳이 같으면 pop을 하고 같지 않으면 push 합니다. 3. 덱의 길이가 0이면 좋은 단어 개수를 하나 올려줍니다. 4. 좋은 단어 개수를 출력합니다.
스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.
입력
첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.
출력
입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.
예제 입력과 출력
알고리즘 분류
스택
정답
from collections import deque
import sys
input = lambda : sys.stdin.readline().strip()
def push(i):
s.append(i)
li.append('+')
def popp():
li.append('-')
s.pop()
n=int(input())
a=[int(input()) for i in range(n)]
s=deque()
li=deque()
p='Y'
for i in range(1,a[0]+1):
push(i)
m=max(s)
popp()
for i in range(1,n):
if a[i] < a[i-1]:
if s[-1] == a[i]:
popp()
else:
p='NO'
break
elif a[i] > a[i-1]:
for j in range(m+1,a[i]+1):
push(j)
m=max(s)
popp()
if p == 'NO':
print(p)
else:
for i in li:
print(i)
1. 첫번째 수까지 push하고 pop을 합니다. 2. 두번째부터 n번째까지 스택을 이용해 수열을 만들 수 있는지 확인합니다. 3. 리스트의 앞자리와 뒷자리의 수를 비교합니다. 3-1. 앞자리가 더 큰 경우 스택의 마지막 값과 뒷자리의 수가 같으면 pop을 합니다. 3-2. 뒷자리가 더 큰 경우 스택에 해당 수까지 push 합니다. 4. 각 단계마다 리스트 li에 push에는 '+'를, pop에는 '-'를 추가하여 출력합니다.
n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.
시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.
아래 그림은 n=8인 경우의 한 예이다.
위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)의 방)을 흰 방으로 바꾸면, 시작방에서 끝방으로 갈 수 있지만, 어느 검은 방 하나만을 흰 방으로 바꾸어서는 불가능하다. 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오.
단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답이다.
입력
첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.
출력
첫 줄에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력한다.
예제 입력과 출력
정답
from collections import deque
n=int(input())
a=[list(map(int,input())) for i in range(n)]
ch=[[-1] * n for i in range(n)]
dx=[-1,0,1,0]
dy=[0,1,0,-1]
def bfs():
de=deque()
de.append([0,0])
ch[0][0]=0
while de:
x,y=de.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n:
if ch[nx][ny] == -1:
if a[nx][ny] == 0:
ch[nx][ny]= ch[x][y] + 1
de.append([nx,ny])
else:
ch[nx][ny]= ch[x][y]
de.appendleft([nx,ny])
bfs()
print(ch[n-1][n-1])
흰방에 도착하면 이동거리는 이전과 같고 먼저 흰방을 방문하기 위해 appendleft를 사용합니다. 검은방에 도착하면 이동거리는 이전에서 +1해주고 append를 사용합니다.
N×M (5≤N, M≤100)의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.
<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.
모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.
출력
출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.
예제 입력과 출력
정답
from collections import deque
n,m=map(int,input().split())
a=[list(map(int, input().split())) for i in range(n)]
c= 0
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
def bfs():
de=deque()
de.append([0,0])
ch=[[-1]*m for i in range(n)]
ch[0][0] = 0
while de:
x, y=de.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if ch[nx][ny] == -1:
if a[nx][ny] >= 1:
a[nx][ny] += 1
else:
ch[nx][ny] = 0
de.append([nx,ny])
while True:
bfs()
cht = 0
for i in range(n):
for j in range(m):
if a[i][j] >= 3:
a[i][j] = 0
cht = 1
elif a[i][j] == 2:
a[i][j] = 1
if cht == 1:
c += 1
else:
break
print(c)
1. bfs를 통해 인접한 칸이 치즈면 값을 1 증가하고 공기칸이면 방문확인을 해주고 이동합니다. 2. 리스트 a에서 3이상인 것은(인접한 칸에 공기가 2개 이상인 것, 1부터 시작했으니까) 치즈가 녹았으니 0으로 바꿔주고 2인 것은 인접한 칸에 공기가 1개인 것이니 1로 바꿔 그대로 치즈로 유지합니다. 3. 위의 과정을 치즈가 모두 녹을때까지 반복하여 걸리는 시간을 출력합니다.
아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.
이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.
다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.
<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.
입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.
출력
첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.
예제 입력과 출력
정답
import sys
from collections import deque
import copy
input = lambda : sys.stdin.readline().strip()
h,w=map(int,input().split()) #h세로 w가로
a=[list(map(int,input().split())) for i in range(h)]
b=copy.deepcopy(a)
ch=[[-1]*w for i in range(h)]
dx=[-1,0,1,0]
dy=[0,1,0,-1]
li=[]
def air(s1,s2):
de=deque()
de.append([s1,s2])
b[s1][s2] = -1
while de:
x,y=de.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < h and 0 <= ny < w:
if a[nx][ny] == 0 and ch[nx][ny] == -1:
b[nx][ny] = -1
ch[nx][ny] = 0
de.append([nx,ny])
def air2(s1,s2):
ch=[[-1]*w for i in range(h)]
de=deque()
de.append([s1,s2])
b[s1][s2] = -1
while de:
x,y=de.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < h and 0 <= ny < w:
if (b[nx][ny] == 0 or b[nx][ny] in li) and ch[nx][ny] == -1:
b[nx][ny] = -1
ch[nx][ny] = 0
de.append([nx,ny])
def cheese(s1,s2,c):
global answer
for i in range(4):
nx = s1 + dx[i]
ny = s2 + dy[i]
if 0 <= nx < h and 0 <= ny < w:
if b[nx][ny] in li:
b[s1][s2] = c
answer += 1
break
air(0,0)
c= 1
li.append(-1)
while True:
c += 1
answer=0
for i in range(h):
for j in range(w):
if b[i][j] != -1 and b[i][j] not in li:
cheese(i,j,c)
li.append(c)
one = 0
for i in b:
one += i.count(1)
if one == 0:
print(c-1)
print(answer)
break
air2(0,0)
1. 입력받은 리스트 a를 b로 복사합니다.
2. 함수 air를 통해 공기(-1), 구멍(0)과 치즈(1)를 분리합니다. 3. 함수 cheese를 통해서 치즈에서 공기와 접한 곳들을 확인해 값 c를 넣어줍니다. c는 걸린시간 +1 4. 리스트 b에서의 치즈의 개수를 확인합니다. 4-1. 치즈의 개수가 없다면 치즈가 모두 녹는데 걸린 시간과 모두 녹기 한 시간 전에 남아있는 치즈의 개수를 확인해 출력합니다. 4-2. 치즈가 아직 남아있다면 함수 air2를 통해 치즈가 녹으면서 늘어난 곳을 확인해 공기로 바꿔줍니다. 5. 3와 4과정을 4-1이 될때까지 반복합니다.
위의 풀이과정은 비효율적인 코드입니다.
import sys
from collections import deque
input = lambda : sys.stdin.readline().strip()
h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
c=0
re=[]
dx=[-1,0,1,0]
dy=[0,1,0,-1]
def bfs():
de=deque()
de.append([0,0])
ch=[[-1]*w for i in range(h)]
ch[0][0]=0
while de:
x,y=de.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < h and 0 <= ny < w:
if ch[nx][ny] == -1:
if a[nx][ny] >= 1:
a[nx][ny] += 1
else:
ch[nx][ny] = 0
de.append([nx,ny])
while True:
bfs()
cht = 0
cou=0
for i in range(h):
for j in range(w):
if a[i][j] >= 2:
a[i][j] = 0
cou += 1
cht = 1
if cht == 1:
c += 1
re.append(cou)
else:
break
print(c)
print(re.pop())
1. bfs를 통해 인접한 칸이 치즈면 치즈를 1 증가하고 공기칸이면 방문확인을 해주고 이동합니다. 2. 리스트 a에서 2이상인 것은 치즈가 녹았으니 0으로 바꾸고 해당 시간에 녹인 치즈의 수를 구해 리스트에 저장합니다. 3. 위의 과정을 치즈가 녹을때까지 반복하고 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈의 개수를 구해 출력합니다.
세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.
말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.
좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.
입력
첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.
출력
첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.
예제 입력과 출력
알고리즘 분류
DFS 백트래킹
정답
import sys
input = lambda: sys.stdin.readline().strip()
r,c=map(int,input().split())
a=[list(map(lambda x : ord(x)-65, input())) for i in range(r)]
ch=[0] * 26 # 26은 알파벳 개수
dx=[-1,0,1,0]
dy=[0,1,0,-1]
def dfs(x, y, z):
global answer
answer=max(answer, z)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < r and 0 <= ny < c and ch[a[nx][ny]] == 0:
ch[a[nx][ny]] = 1
dfs(nx, ny, z+1)
ch[a[nx][ny]] = 0
answer=1
ch[a[0][0]] = 1
dfs(0, 0, answer)
print(answer)
python 시간초과로 PyPy3로 제출했습니다.
입력받은 알파벳들을 아스키 코드 값으로 바꿔 저장합니다. 해당 알파벳을 거쳤는지 확인할 리스트 ch를 이용하기 위해서입니다.
