import sys
input = sys.stdin.readline
n, m = map(int, input().split())
dic = {}
revDic = {}
for i in range(n):
tmpS = input().strip()
dic[i+1]=tmpS
revDic[tmpS]=i+1
for i in range(m):
tmpV = input().strip()
if tmpV.isdigit():
tmpV= int(tmpV)
print(dic[tmpV])
else:
print(revDic[tmpV])
시간/공간 복잡도
O(n)
어려웠던 점
자료구조 조회할 때, 시간초과를 해결하기 위해서는 리스트보다 해시테이블을 구조인 딕셔너리 사용(O(1)) 이 더 빠르기 때문에 효과적이다.
알게된 점
키 값을 통해 값을 찾거나 밸류 값을 통해 값을 찾아야 하는 경우, 두개의 딕셔너리를 활용하면 아주 효율적이다.
문자열이 숫자 값인지 확인할때, 대상.isdigit()함수를 사용하면 확인할 수 있다. (숫자일 경우 True 반환)
import sys
input = sys.stdin.readline
t = int(input())
def fibonacci(n, count):
if n<=1:
if n ==0:
count[0]+=1
if n==1:
count[1]+=1
print(count[0], count[1])
return n
a = 0
b = 1
for i in range(2, n+1):
c = a + b
a = b
b = c
print(a, b)
return b
for i in range(t):
n = int(input())
count = [0, 0]
fibonacci(n, count)
# 0 1 1 2 3 5 8
시간/공간 복잡도
O(n)
최적화 및 개선
피보나치 함수 알고리즘을 구현할 때, 재귀함수로 구현후 시간 초과가 나면 DP로 구현하면 시간 복잡도를 줄일 수 있다.
import sys
input = sys.stdin.readline
n = int(input())
tmp = []
for i in range(n):
entire = input().strip()
if entire=='all':
tmp = list(range(1, 21))
elif entire=='empty':
tmp.clear()
else:
s, v = entire.split()
v = int(v)
if s == 'add':
if v not in tmp:
tmp.append(v)
if s == 'check':
if int(v) in tmp:
print(1)
else:
print(0)
if s == 'remove':
if v in tmp:
tmp.remove(v)
if s == 'toggle':
if int(v) in tmp:
tmp.remove(v)
else:
tmp.append(v)
시간/공간 복잡도
O(n)
어려웠던 점
입력값의 타입에 대해 잘 고려하지 않아서 조건문이 제대로 실행되지 않았던 점
sys모듈에서 input()함수를 사용할 때, 개행문자(/n)가 붙어서 조건문이 제대로 실행되지 않았던 점
느낀점
sys모듈에서 input()함수를 사용할 때, 개행문자(/n)를 꼭 처리하여 문제를 해결해야겠다.
이때, deque를 활용해 큐를 만들고 큐에 bfs함수를 실행할 당시의 좌표값을 넣어준다. 이때 지렁이의 개수를 +1 한다
bfs함수에서는 큐에서 값을 꺼내어 방문처리를 해주고, 자신의 자리에서 심겨진배추가 이어져 있다는 판단 기준인 위, 아래, 양옆을 조회 한다. 이때, 새로 조회하는 위치가 그림 정보가 적힌 좌표의 범위를 벗어나서도 안되고, 이미 방문 한 적이 있어도 안된다. 또한 0이여도 안된다. 값이 0이 아니고 방문한 적이 없으면 현재자리의 방문체크를 해준다.
그림 정보 순회가 모두 끝나면 임의의 리스트의 원소의 개수와 원소의 최대값을 출력한다.
코드 구현
정답 코드
import sys
from collections import deque
input=sys.stdin.readline
dx= [0, 0, 1, -1]
dy= [1, -1, 0, 0]
answer=[]
def bfs(y, x):
queue = deque()
visited[y][x] = True
queue.append([y, x])
while queue:
ny, nx = queue.popleft()
for ii in range(4):
yy= ny+dy[ii]
xx= nx+dx[ii]
if 0<=yy<n and 0<=xx<m and mapp[yy][xx]==1 and visited[yy][xx] == False:
visited[yy][xx] = True
queue.append([yy, xx])
t = int(input())
for j in range(t):
m, n, k = map(int, input().split())
mapp = [[0] * m for _ in range(n)]
visited = [[False] * m for _ in range(n)]
cnt = 0
for i in range(k):
wm, wn = map(int, input().split())
mapp[wn][wm] = 1
for ix in range(n):
for jx in range(m):
if mapp[ix][jx]==1 and visited[ix][jx] == False:
cnt+=1
bfs(ix, jx)
answer.append(cnt)
for i in answer:
print(i)
시간/공간 복잡도
따로 생각하지 않았다.
최적화 및 개선
따로 하지않음
어려웠던 점
BFS는 큐에 넣기 전에 방문처리를 해야 중복 방문처리를 하지 않게 된다는 것을 알게됐다.
그림 정보가 적힌 좌표를 순회한다. 대신 방문여부를 알 수 있는 visited 배열이 필요하다.
좌표를 순회할때 1을 만나고, 방문한 적이 없으면 bfs함수를 실행한다.
이때, deque를 활용해 큐를 만들고 큐에 bfs함수를 실행할 당시의 좌표값을 넣어준다.
bfs함수에서는 큐에서 값을 꺼내어 방문처리를 해주고, 자신의 자리에서 그림이 이어져 있다는 판단 기준인 위, 아래, 양옆을 조회 한다.
이때, 새로 조회하는 위치가 그림 정보가 적힌 좌표의 범위를 벗어나서도 안되고, 이미 방문 한 적이 있어도 안된다. 또한 0이여도 안된다.
값이 0이 아니고 방문한 적이 없으면 현재자리의 값에서+1을 해준다. 큐에 해당 좌표와 얼마나 끊기지 않고 값을 조회하고있는지에 대한 값 현재 자리의 값+1을 넣어준다.
순회를 하면서 더이상 큐에 값을 이어 넣을 수 없으면(그림이 끊기면), 얼마나 끊기지 않고 값을 조회했는지에 대한 값을 임의의 리스트에 넣어준다.
그림 정보 순회가 모두 끝나면 임의의 리스트의 원소의 개수와 원소의 최대값을 출력한다.
코드 구현
정답 코드
import sys
input=sys.stdin.readline
n, m = map(int, input().split())
from collections import deque
if n==0 and m==0:
print(0)
print(0)
exit(0)
dy=[1, -1, 0, 0]
dx=[0, 0, 1, -1]
tmp=[]
for i in range(n):
tmp2=list(map(int, input().split()))
tmp.append(tmp2)
# 그냥 카운트만 하는애 cnt
# 방문 확인용 visited
cnt = 0
visited = [([False] * m) for _ in range(n)]
bigN = 0
def bfs(cnt, dequeA, visited):
bigN=1
while dequeA:
yy, xx, _ = dequeA.popleft()
visited[yy][xx] = True
for i in range(4):
nx=xx+dx[i]
ny=yy+dy[i]
if ny<0 or nx<0 or ny>=n or nx>=m:
continue
if visited[ny][nx]==True or tmp[ny][nx]==0:
continue
if tmp[ny][nx]>=1 and visited[ny][nx]==False:
tmp[ny][nx] = bigN+1
bigN=bigN+1
visited[ny][nx]=True
dequeA.append([ny,nx, bigN])
return cnt, bigN
tmp3=[]
check = 0
dequeA = deque()
for i in range(n):
for j in range(m):
if tmp[i][j] == 1 and visited[i][j] == False:
dequeA.append([i,j, 1])
cnt+=1
cnt, bigN = bfs(cnt, dequeA, visited)
tmp3.append(bigN)
check =1
print(cnt)
if n == 0 and m ==0 or check ==0:
print(0)
else:
print(max(tmp3))
시간/공간 복잡도
따로 생각하지 않았다.
최적화 및 개선
따로 하지않음
어려웠던 점
BFS 문제를 효율적으로 푸는 방법이 가물가물해서 문제 풀기 어려웠다.
알게된 것
함수 객체 할당과 함수 호출 구문을 구분하지 못해서 생긴 일
여러줄을 받을 때 속도 감소를 위해 input()함수 말고 sys 에서 제공하는 readline()함수를 사용하려는 상황이다.
import sys
n, m = map(int, input().split())
input=sys.stdin.readline()
tmp=[]
for i in range(n):
# tmp2=list(input.split())
tmp2=input.split()
print('tmp2', tmp2)
tmp.append(tmp2)
print(tmp)
문제가 있는 코드: 이코드에서는 2번째줄 3번째줄만 입력을 받는게 된다.
괄호를 붙이지 않은 경우 (input = sys.stdin.readline):
이 경우 sys.stdin.readline 함수 객체를 input이라는 변수에 직접 할당하는 것이다. 이 상태에서는 input은 함수 객체 자체를 참조하게 된다.
괄호를 붙인 경우 (input()):
괄호를 붙이면 함수가 실제로호출된다.함수 호출은 해당 함수가 수행하는 작업을 실행하고, 그 결과를 반환한다.
import sys
n, m = map(int, input().split())
input=sys.stdin.readline
tmp=[]
for i in range(n):
tmp2=input().split()
tmp.append(tmp2)
print(tmp)
s1 = input()
s2 = input()
m=len(s1)
n=len(s2)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1]==s2[j-1]:
dp[i][j]=dp[i-1][j-1]+1
else:
dp[i][j]=max(dp[i][j-1], dp[i-1][j])
result =''
startm = m
startn = n
print(max(dp[-1]))
if max(dp[-1])!=0:
while 1:
if dp[startm][startn]==0:
break
# 위에것이 더 큰지
if dp[startm][startn] == dp[startm-1][startn]:
startm-=1
# 왼쪽 것이 더 큰지
elif dp[startm][startn] == dp[startm][startn-1]:
startn-=1
# 둘다 안크면 대각선 이동
# 값도 넣어줌
elif ((dp[startm][startn]-1) == dp[startm-1][startn-1]):
startm-=1
startn-=1
result+=s2[startn]
print(result[::-1])
시간/공간 복잡도
0.1초로 시간제한이 있었는데, 해당 시간에 1000만 번의 연산을 해야하는거고, 최대로 입력할 수 있는 문자열의 길이가 1000이기 때문에
2. 따라서 0행0열 0행 2열 0행 4열... 2행 0열 2행 2열.... 이렇게 맵의 크기만큼 조회한다.
2-1. 출발지 기준 이때 오른쪽으로 한칸, 아래로 한칸, 아래 오른쪽으로 한칸 을 리스트에 넣는다.
2-2. 리스트에서 두번재로 큰 수만 모아서 또다른 리스트를 만든다.
2번을 맵의 원소가 1개 남을때 까지 반복하다보면 결과 값이 나온다.
코드 구현
정답 코드
import sys
n = int(input())
block=[]
for i in range(n):
tmp = list(map(int, sys.stdin.readline().strip().split()))
block.append(tmp)
while 1:
if len(block[0])==1:
print(block[0][0])
break
makeBlock = [item[:] for item in block]
block = []
for i in range(0, len(makeBlock),2):
tmp=[]
for j in range(0, len(makeBlock[0]),2):
realT=[makeBlock[i][j], makeBlock[i][j+1], makeBlock[i+1][j], makeBlock[i+1][j+1]]
realT.sort(reverse=True)
tmp.append(realT[1])
block.append(tmp)
1. 받은 문장을 한글자씩 순회하며 현재 열려있는 괄호를 스택에 넣는다. (flag 표시를 해준다 flag = 1)
2. 문장을 순회하다가 닫는 괄호가 나오면 바로 직전에 본 글자가 열려있는 괄호인지 확인한다. (확인은 flag를 통해서 한다. )
2-1. flag가 1이면 레이저로 확인되었으므로 그동안 열려있는 괄호의 수만큼 카운트 변수에 +1을 해준다.
2-2. flag가 0이면 단순 닫는 flag이니 괄호를 닫아주되(들어가있는 값중 -1 인덱스의 값이 열린괄호가 있으면 pop), 하나의 종이를 레이저가 한번 자르면 종이가 n개면 +1이 된다는 것을 고려하여 카운트값에 +1을 해준다.
3. 순회가 끝날 때 까지 2번을 반복한다.
코드 구현
정답 코드
# ()는 레이저다
s = input()
stack=[]
cnt = 0
flag=0
for i in s:
if i =='(':
stack.append('(')
flag=1
elif i==')':
if stack[-1] =='(':
stack.pop()
if stack and flag==1:
if flag ==1:
cnt+=len(stack)
if flag ==0:
cnt+=1
flag=0
# print('난 ',i,'에요', stack, 'cnt: ', cnt)
print(cnt)
2-1. 순회하면서 닫는 괄호가 나온 경우, 직전에 여는 괄호가 나왔는지 체크한다. 이것은 괄호를 순회하며 사전에 flag로 지속적으로 체크한다. (flag=1)
2-2. 순회하면서 닫는 괄호가 나온 경우, 직전에 여는 괄호가 나오지 않은 경우, flag는 0인 경우이다.
3. 2-1의 조건을 통과한 경우, 현재 열고있는 괄호의 갯수만큼 카운트 변수에 더해준다.
2-2의 조건을 통과한 경우,
코드 구현
정답 코드
import sys
input = sys.stdin.readline
n, c = map(int, input().split())
tmp=[]
for i in range(n):
x = int(input())
tmp.append(x)
tmp.sort()
print(tmp)
start = 1 # 최소 거리
end = tmp[-1]-tmp[0] # 최대 거리
cnt=1
result = 0
while start<=end:
mid = (start + end) // 2 # 중간 간격 거리
cnt = 1 # 첫번째 원소는 이미 방문한 것으로 침
curr = tmp[0]
for i in range(1, len(tmp)):
if tmp[i] >= mid + curr: # 이동하려는 간격이 (중간간격 거리 + 현재 위치) 보다 크면
cnt+=1
curr=tmp[i]
if cnt >= c: # 공유기 설치가 끝났으면, 범위를 좀 더 퍼트려줄 필요가 있다.
start=mid+1
result=mid
else: # 범위에 못미치면 범위를 줄여줄 필요가 있다.
end=mid-1
print(result)
시간/공간 복잡도
n^2으로 못풂
최적화 및 개선
따로 하지않음
어려웠던 점
상당히 낯설고 어렵게 느껴지는 문제이다.
이분탐색 알고리즘을 적용하고 싶은데 와닿는 이해가 되지 않는 문제였다. => 다음에 다시 풀어볼 문제
