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으로 못풂
최적화 및 개선
따로 하지않음
어려웠던 점
상당히 낯설고 어렵게 느껴지는 문제이다.
이분탐색 알고리즘을 적용하고 싶은데 와닿는 이해가 되지 않는 문제였다. => 다음에 다시 풀어볼 문제
# 크기 RxC 격자
# 폭탄칸 3초 지난후 폭발 => 폭탄 칸 파괴되어 빈칸됨 => 인접한 네 칸도 파괴됨
# 만약 폭탄 폭발시 인접 네칸에 폭탄이 있는 경우, 해당 폭탄은 폭발없이 파괴됨 = 연쇄반응X
# 1. 일부 칸에 폭탄 설치 = 모든 폭탄이 설치된 시간은 같음 0초
# 2. 다음 1초 동안 아무것도 하지 않음
# 3. 다음 1초 동안 폭탄이 설치되지 않은 모든 칸에 폭탄 설치=모든 칸은 폭탄을 가짐 =동시에 설치
# 4. 1초 지난 후, 3초 전에 설치된 폭탄이 모두 폭발
# 5. 3-4 반복
import sys
input= sys.stdin.readline # 뒤에 괄호 붙이지 않도록 조심.
dy=[0, 0, 1, -1]
dx=[1, -1, 0, 0]
r, c, n = map(int, input().split())
bombMap = []
for i in range(r):
tmp = list(input().strip())
bombMap.append(tmp)
print(bombMap)
time = 0
check=0
for i in range(r):
for j in range(c):
if bombMap[i][j] == '.':
bombMap[i][j]=0
else:
bombMap[i][j]=1
print('초기상태')
print('check', check)
print('time: ', time)
for i in range(len(bombMap)):
print('check', bombMap[i])
print()
realzero=1
while 1:
time+=1
check+=1
if check==1:
if realzero==1:
realzero=0
for i in range(r):
for j in range(c):
if bombMap[i][j] > 0:
bombMap[i][j]+=1
elif realzero ==0:
for i in range(r):
for j in range(c):
bombMap[i][j]+=1
else:
if check ==2 :
for i in range(r):
for j in range(c):
bombMap[i][j]+=1
rem = [item[:] for item in bombMap]
if time >=5:
for i in range(r):
for j in range(c):
if rem[i][j]==3:
bombMap[i][j]=0
for k in range(4):
ni = i + dy[k]
nj = j + dx[k]
if 0<=ni<r and 0<=nj<c:
bombMap[ni][nj]=0
elif check ==3:
for i in range(r):
for j in range(c):
if rem[i][j]==3:
bombMap[i][j]=0
for k in range(4):
ni = i + dy[k]
nj = j + dx[k]
if 0<=ni<r and 0<=nj<c:
bombMap[ni][nj]=0
if time >= n:
print('check', check)
print('time: ', time)
for i in range(len(bombMap)):
print('hello', bombMap[i])
print()
for i in range(r):
tmpS=''
for j in range(c):
if bombMap[i][j]>0:
s='O'
tmpS+=s
else:
s='.'
tmpS+=s
print(tmpS)
break
rem = [item[:] for item in bombMap]
print('check', check)
print('time: ', time)
for i in range(len(bombMap)):
print('hello', bombMap[i])
print()
if check ==3:
check=1
정답 코드
# 크기 RxC 격자
# 폭탄칸 3초 지난후 폭발 => 폭탄 칸 파괴되어 빈칸됨 => 인접한 네 칸도 파괴됨
# 만약 폭탄 폭발시 인접 네칸에 폭탄이 있는 경우, 해당 폭탄은 폭발없이 파괴됨 = 연쇄반응X
# 1. 일부 칸에 폭탄 설치 = 모든 폭탄이 설치된 시간은 같음 0초
# 2. 다음 1초 동안 아무것도 하지 않음
# 3. 다음 1초 동안 폭탄이 설치되지 않은 모든 칸에 폭탄 설치=모든 칸은 폭탄을 가짐 =동시에 설치
# 4. 1초 지난 후, 3초 전에 설치된 폭탄이 모두 폭발
# 5. 3-4 반복
import sys
input= sys.stdin.readline # 뒤에 괄호 붙이지 않도록 조심.
dy=[0, 0, 1, -1]
dx=[1, -1, 0, 0]
r, c, n = map(int, input().split())
bombMap = []
for i in range(r):
tmp = list(input().strip())
bombMap.append(tmp)
time = 0
for i in range(r):
for j in range(c):
if bombMap[i][j] == '.':
bombMap[i][j]=0
else:
bombMap[i][j]=1
# 유지 time ==1
time+=1
for i in range(r):
for j in range(c):
if bombMap[i][j] > 0:
bombMap[i][j]+=1
if n==1:
if time == n:
for i in range(r):
tmpS=''
for j in range(c):
if bombMap[i][j]>0:
s='O'
tmpS+=s
else:
s='.'
tmpS+=s
print(tmpS)
else:
while 1:
time+=1
if time % 4==1:
# 유지
for i in range(r):
for j in range(c):
if bombMap[i][j] > 0:
bombMap[i][j]+=1
rem = [item[:] for item in bombMap]
# 폭발
for i in range(r):
for j in range(c):
if rem[i][j]==3:
bombMap[i][j]=0
for k in range(4):
ni = i + dy[k]
nj = j + dx[k]
if 0<=ni<r and 0<=nj<c:
bombMap[ni][nj]=0
elif time % 4 == 3:
# 폭발
rem = [item[:] for item in bombMap]
for i in range(r):
for j in range(c):
if rem[i][j]==3:
bombMap[i][j]=0
for k in range(4):
ni = i + dy[k]
nj = j + dx[k]
if 0<=ni<r and 0<=nj<c:
bombMap[ni][nj]=0
else:
# 설치, 증가
for i in range(r):
for j in range(c):
bombMap[i][j]+=1
if time == n:
for i in range(r):
tmpS=''
for j in range(c):
if bombMap[i][j]>0:
s='O'
tmpS+=s
else:
s='.'
tmpS+=s
print(tmpS)
break
시간/공간 복잡도
시뮬레이션 문제 같아서 아예 시간복잡도 계산을 배제하고 문제를 풀었다.
최적화 및 개선
따로 하지않음
어려웠던 점
이 문제는 문제를 풀 때 단순하게 생각하면 안된다.
시간을 보내는것과 보내는 중일때 할 일을 잘 구분해야한다.
처음에 폭탄 패턴이 두개 돌거란 생각을 하지 못했다. 따라서 문제 자체가 이해 안되고, 심지어 문제에 문제가 있는거 아닌가 하는 생각을 했었다. 항상 무조건 진행 과정에 대해서 헷깔리거나 파악이 안될때 종이에 해당 과정을 손으로 쓰면서 따라가보는게 중요한 것 같다.
규칙을 찾아야한다. 규칙을 찾는게 제일 중요한 것 같다.
알게된 것
sys모듈의 sys.stdin.readLine는 코드로 작성할 때 괄호를 붙이면 안된다.
sys.stdin.readLine을 사용할때, 뒤에 개행문자가 따라붙는다. 따라서 사용시 주의해줘야한다.
개행문자를 제거하는 함수 사용시 참고할 부분이다.
strip()이랑 rstrip() 무슨차이인가?
.strip()과 .rstrip()은 모두 문자열의 양 끝에서 공백 문자를 제거하는 메서드이지만, 제거하는 위치가 다름
import sys
n=int(sys.stdin.readline())
total=[]
minn=2100000000
maxx=0
for i in range(n):
# 입장시간, 퇴장시간
e, x = map(int, sys.stdin.readline().split())
#print(e, x)
if e<minn:
minn=e
if x>maxx:
maxx=x
total.append([e,x-1])
#print(minn, maxx)
total
tmp=[]
for i in range(maxx):
tmp.append(0)
for i in total:
s, e = i
for i in range(s, e+1):
tmp[i]+=1
#print(tmp)
check = 0
start = -1
end = -1
result = []
cnt=0
for i, value in enumerate(tmp):
if value == max(tmp):
if start != -1:
check=1
continue
else:
#최초로 넣을때
check=1
start = i
result.append(i)
cnt+=1
start=-1
else:
if check==1:
check=0
end=i
result.append(i)
end = -1
#print(result)
print(max(tmp))
origin = result[0]
originEnd = 0
originStart=0
for i, value in enumerate(result):
if i ==0:
originStart=value
continue
if origin +1 == value:
origin+=1
else:
originEnd=result[i-1]
break
if originEnd==0:
originEnd=result[-1]
print(originStart, originEnd)
정답 코드
(주석 있는 버전)
import sys
from collections import defaultdict
input = sys.stdin.readline
n = int(input())
d = defaultdict(int)
print('defaultdict', d)
for i in range(n):
s, e = map(int, input().split())
d[s] += 1
d[e] -= 1
m, cnt = 0, 0 # cnt는 모기 마릿수 m은 최대갱신 모기 마릿수
tem, txm = 0, 0# 최댓값 갱신시 시간과 갱신 해제시 시간
flag = False
for i in sorted(d.keys()):
print(i)
cnt += d[i]
# 기존 최대 모기수 보다 현재 모기수가 더 클때
# == 최고일때만 계산함
if cnt > m:
m = cnt
tem = i
flag = True
# 현재 모기수 cnt보다 최대 갱신 모기수가 더 크고
# 만약, 현재 값이 모기가 나가는 타이밍일때
# 현재 모기수에서 지금 시간의 모기를 빼면 음수값이라 더한 격이 되어
# 지금 나간 모기를 더했을때의 값 = 최대값이 m인 경우이다.
# FLAG가 TRUE인 상태
# 마찬가지로 최고자리가 박탈 됐을때 계산함
elif cnt < m and cnt - d[i] == m and flag:
txm = i
flag = False
print(m)
print(tem, txm)
(주석 없는 버전) - 변수명 변경됨
import sys
from collections import defaultdict
input = sys.stdin.readline
n=int(input())
dict = defaultdict(int)
for i in range(n):
# 입장시간, 퇴장시간
e, x = map(int, input().split())
dict[e] += 1
dict[x] -= 1
maxx, nowMos = 0, 0
startTime, endTime = 0, 0
flag = False
for i in sorted(dict.keys()):
nowMos += dict[i]
if nowMos > maxx:
maxx = nowMos
startTime = i
flag = True
elif nowMos < maxx and nowMos - dict[i] == maxx and flag:
flag = False
endTime = i
print(maxx)
print(startTime, endTime)
시간/공간 복잡도
입력값보다 입력값의 값의 범위가 워낙 커서 웬만하면 N으로 구현해야 했다.
최적화 및 개선
기존에는 입력값의 범위를 전부 순회하면서 최대 모기수를 체크해서 시간초과가 발생했었다.
이런 방식의 관점을 바꿨다.
=> 현재 방에 있는 모기의 수가 갱신이 되는 모기의 수일 경우에만 체크
어려웠던 점
시간복잡도에 대한 개념은 알고있지만, 여전히 문제 풀기전에 시간복잡도에 대한 계산을 하는것이 어렵다.
파이썬의 경우 1초에 최대 연산횟수가 logN인 알고리즘으로 계산해도 최대 연산 횟수가 10억번인데, 이 문제의 경우 값의 범위가 10억을 훌쩍넘어 20억쯤 된다. 이런 경우는 시간복잡도 계산을 어떻게 해야하는지 모르겠다.
알게된 것
sys모듈의 sys.stdin.readLine() 함수를 input 변수로 저장 할 생각을 못하고 계속 수기로 작성해왔었는데 이제는 변수로 저장할 줄 알게됐다.
import sys, copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님
# 다른 스티커와 겹침X, 노트북 벗어나면X,
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽)
# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기
# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.
# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?
#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)
n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
#모눈종이의 행, 열
r, c = map(int, sys.stdin.readline().split())
stickerPocketEntire.append([r,c])
tmp2=[]
for j in range(r):
tmp1 = list(map(int, sys.stdin.readline().split()))
tmp2.append(tmp1)
stickerPocket.append(tmp2)
print(stickerPocket)
#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임.
# 단, 붙일 수 없는 경우는 판별해줌
# 붙일 수 없는 경우
# 1. 노트북을 벗어나는경우[조건문]
# 2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
# ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
# ->다음 스티커로 넘어간다.
# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다.
visited=[ [0] * m for i in range(n)]
print('visited', visited)
def rotation(cnt, i):
r, l = stickerPocketEntire[i]
# 3번만 돌림
#90도로 돌리기
tmp = stickerPocket[i]
nn=len(tmp)
mm=len(tmp[0])
tmpList =[]
for qq in range(mm):
tmpList2=[]
for pp in range(nn-1, -1, -1):
tmpList2.append(tmp[pp][qq])
tmpList.append(tmpList2)
stickerPocket[i]=tmpList
stickerPocketEntire[i]=[mm, nn]
print('checkcnt: ', cnt)
cnt+=1
print('cnt: ', cnt)
return cnt
def backtrack(p, q, i, r, l, visited):
rem = copy.deepcopy(visited)
print('초기 rem', rem)
# 이부분 백트래킹으로 구현해야할듯
for j in range(r):
for jj in range(l):
#왼쪽 위부터 조회
nr = p+j
nl = q+jj
if 0<=nr<n and 0<=nl<m:
print('i:', i, "j:", j, "jj", jj)
if stickerPocket[i][j][jj]==1:
#두번째 스티커를 자리에 붙여본다
if visited[p+j][q+jj]!=1:
#겹치는지 확인후 붙여보기
visited[p+j][q+jj]=1
else:
#겹친다.
#스티커를 붙이기 전으로 원래대로 돌아가기
visited=copy.deepcopy(rem)
check = 0
print('리턴 visited', visited)
return visited, check
check = 1
else:
print("뭐지 nr:", nr, "nl:", nl)
visited=copy.deepcopy(rem)
check = 0
print('리턴 visited', visited)
return visited, check
if check == 1:
return visited, check
i=0
cnt=0 # 회전 횟수
check=1
while(1):
r, l = stickerPocketEntire[i]
if (n<r or m<l) or check ==0:
# 모눈종이의 크기가 노트북을 넘어가면
# 90도 회전 적용
if cnt <=3:
cnt = rotation(cnt, i)
r, l = stickerPocketEntire[i]
else:
i+=1
cnt=0
if i == 0:
#항상 0,0에서 부터 시작해야함
for j in range(r):
for jj in range(l):
if stickerPocket[0][j][jj]==1:
visited[j][jj]=1
i+=1
cnt=0
else:
for p in range(n):
for q in range(m):
if i ==k:
break
print('hi')
print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
visited, check = backtrack(p, q, i, r, l, visited)
print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
print('hi end')
if check==1 or cnt>3: #스티커를 제대로 붙였을 때
i+=1
cnt=0
if check==0 and cnt>3:
break
if check==0 and cnt>3:
break
if i ==k:
break
print("?????????")
sum=0
for end in visited:
for end2 in end:
if end2==1:
sum+=1
print(sum)
import sys, copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님
# 다른 스티커와 겹침X, 노트북 벗어나면X,
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽)
# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기
# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.
# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?
#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)
n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
#모눈종이의 행, 열
r, c = map(int, sys.stdin.readline().split())
stickerPocketEntire.append([r,c])
tmp2=[]
for j in range(r):
tmp1 = list(map(int, sys.stdin.readline().split()))
tmp2.append(tmp1)
stickerPocket.append(tmp2)
print(stickerPocket)
#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임.
# 단, 붙일 수 없는 경우는 판별해줌
# 붙일 수 없는 경우
# 1. 노트북을 벗어나는경우[조건문]
# 2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
# ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
# ->다음 스티커로 넘어간다.
# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다.
visited=[ [0] * m for i in range(n)]
print('visited', visited)
def rotation(cnt, i):
r, l = stickerPocketEntire[i]
# 3번만 돌림
#90도로 돌리기
tmp = stickerPocket[i]
nn=len(tmp)
mm=len(tmp[0])
tmpList =[]
for qq in range(mm):
tmpList2=[]
for pp in range(nn-1, -1, -1):
tmpList2.append(tmp[pp][qq])
tmpList.append(tmpList2)
print('before',stickerPocket[i])
stickerPocket[i]=tmpList
stickerPocketEntire[i]=[mm, nn]
print('after',tmpList)
print('checkcnt: ', cnt)
cnt+=1
print('cnt: ', cnt)
return cnt
def backtrack(p, q, i, r, l, visited):
rem = copy.deepcopy(visited)
print('초기 rem', rem)
# 이부분 백트래킹으로 구현해야할듯
for j in range(r):
for jj in range(l):
#왼쪽 위부터 조회
nr = p+j
nl = q+jj
if 0<=nr<n and 0<=nl<m:
print('i:', i, "j:", j, "jj", jj)
if stickerPocket[i][j][jj]==1:
#두번째 스티커를 자리에 붙여본다
if visited[p+j][q+jj]!=1:
#겹치는지 확인후 붙여보기
visited[p+j][q+jj]=1
else:
#겹친다.
#스티커를 붙이기 전으로 원래대로 돌아가기
visited=copy.deepcopy(rem)
check = 0
print('리턴 visited', visited)
return visited, check
check = 1
else:
print("뭐지 nr:", nr, "nl:", nl)
visited=copy.deepcopy(rem)
check = 0
print('리턴 visited', visited)
return visited, check
if check == 1:
return visited, check
i=0
cnt=0 # 회전 횟수
check=1
while(1):
r, l = stickerPocketEntire[i]
if (n<r or m<l) or check ==0:
if l<=n and r<=m:
# 모눈종이의 크기가 노트북을 넘어가면
# 90도 회전 적용
# 회전의 조건: 모눈종이가 노트북에 딱 들어맞지 않는경우(단, 가로 세로는 뒤집혔을때 노트북에 들어갈 수 있어야 함)
if cnt <3:
cnt = rotation(cnt, i)
r, l = stickerPocketEntire[i]
else:
i+=1
cnt=0
else:
i+=1
if i == 0:
#항상 0,0에서 부터 시작해야함
for j in range(r):
for jj in range(l):
if stickerPocket[0][j][jj]==1:
visited[j][jj]=1
i+=1
cnt=0
else:
for p in range(n):
for q in range(m):
if i ==k:
break
r, l = stickerPocketEntire[i]
print('hi')
print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
visited, check = backtrack(p, q, i, r, l, visited)
print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
print('hi end')
if check==1 or cnt>3: #스티커를 제대로 붙였을 때
i+=1
cnt=0
if check==0 and cnt>3:
break
if check==0 and cnt>3:
break
if i ==k:
break
print("?????????")
sum=0
for end in visited:
for end2 in end:
if end2==1:
sum+=1
print(sum)
import sys, copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님
# 다른 스티커와 겹침X, 노트북 벗어나면X,
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽)
# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기
# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.
# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?
#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)
n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
#모눈종이의 행, 열
r, c = map(int, sys.stdin.readline().split())
stickerPocketEntire.append([r,c])
tmp2=[]
for j in range(r):
tmp1 = list(map(int, sys.stdin.readline().split()))
tmp2.append(tmp1)
stickerPocket.append(tmp2)
#print(stickerPocket)
#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임.
# 단, 붙일 수 없는 경우는 판별해줌
# 붙일 수 없는 경우
# 1. 노트북을 벗어나는경우[조건문]
# 2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
# ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
# ->다음 스티커로 넘어간다.
# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다.
visited=[[0] * m for i in range(n)]
#print('visited', visited)
def rotation(cnt, i):
r, l = stickerPocketEntire[i]
# 3번만 돌림
#90도로 돌리기
tmp = stickerPocket[i]
nn=len(tmp)
mm=len(tmp[0])
tmpList =[]
for qq in range(mm):
tmpList2=[]
for pp in range(nn-1, -1, -1):
tmpList2.append(tmp[pp][qq])
tmpList.append(tmpList2)
#print('before',stickerPocket[i])
stickerPocket[i]=tmpList
stickerPocketEntire[i]=[mm, nn]
# print('after',tmpList)
# print('checkcnt: ', cnt)
cnt+=1
# print('cnt: ', cnt)
return cnt
def backtrack(p, q, i, r, l, visited):
rem = copy.deepcopy(visited)
# print('초기 rem', rem)
# 이부분 백트래킹으로 구현해야할듯
for j in range(r):
for jj in range(l):
#왼쪽 위부터 조회
nr = p+j
nl = q+jj
if 0<=nr<n and 0<=nl<m:
# print('i:', i, "j:", j, "jj", jj)
if stickerPocket[i][j][jj]==1:
#두번째 스티커를 자리에 붙여본다
if visited[p+j][q+jj]!=1:
#겹치는지 확인후 붙여보기
visited[p+j][q+jj]=1
else:
#겹친다.
#스티커를 붙이기 전으로 원래대로 돌아가기
visited=copy.deepcopy(rem)
check = 0
# print('리턴 visited', visited)
return visited, check
check = 1
else:
# print("뭐지 nr:", nr, "nl:", nl)
visited=copy.deepcopy(rem)
check = 0
# print('리턴 visited', visited)
return visited, check
if check == 1:
return visited, check
i=0
cnt=0 # 회전 횟수
check=1
while(1):
r, l = stickerPocketEntire[i]
if (n<r or m<l) or check ==0:
if l<=n and r<=m:
# 모눈종이의 크기가 노트북을 넘어가면
# 90도 회전 적용
# 회전의 조건: 모눈종이가 노트북에 딱 들어맞지 않는경우(단, 가로 세로는 뒤집혔을때 노트북에 들어갈 수 있어야 함)
if cnt <3:
cnt = rotation(cnt, i)
r, l = stickerPocketEntire[i]
else:
i+=1
cnt=0
else:
i+=1
if i == 0:
#항상 0,0에서 부터 시작해야함
for j in range(r):
for jj in range(l):
if stickerPocket[0][j][jj]==1:
visited[j][jj]=1
i+=1
cnt=0
else:
for p in range(n):
for q in range(m):
if i ==k:
break
r, l = stickerPocketEntire[i]
# print('hi')
# print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
visited, check = backtrack(p, q, i, r, l, visited)
# print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
# print('hi end')
if check==1 or cnt>3: #스티커를 제대로 붙였을 때
i+=1
cnt=0
if check==0 and cnt>3:
break
if check==0 and cnt>3:
break
if i ==k:
break
#print("?????????")
sum=0
for end in visited:
for end2 in end:
if end2==1:
sum+=1
print(sum)
import sys
#import copy
# 스티커 각 칸은 상하좌우로 모두 연결되어있어야함 = 어디 끊기면 안됨
# 모눈종이에 스티커가 없는 불필요한 행이나 열이 있으면 정상아님
# 다른 스티커와 겹침X, 노트북 벗어나면X,
# 노트북의 위쪽부터 채움(우선순위 = 1. 가장 위쪽의 위치
# , 위쪽에 여러곳일 경우2. 가장 왼쪽)
# 만약 스티커 붙일 자리가 안보인다면, 스티커를 시계방향 90도 회전 후
# 붙일 자리 찾기
# 스티커를 0도, 90도, 180도, 270도 회전시켜 봤음에도
# 스티커를 붙이지 못했다면 해당 스티커를 붙이지 않고 버린다.
# 다 붙인 후에 노트북에서 몇개의 칸이 채워졌는가?
#시간 복잡도
# 세로N(40) 가로M(40) 스티커의 개수K(100)
n, m, k = map(int, sys.stdin.readline().split())
stickerPocket = []
stickerPocketEntire=[]
for i in range(k):
#모눈종이의 행, 열
r, c = map(int, sys.stdin.readline().split())
stickerPocketEntire.append([r,c])
tmp2=[]
for j in range(r):
tmp1 = list(map(int, sys.stdin.readline().split()))
tmp2.append(tmp1)
stickerPocket.append(tmp2)
#print(stickerPocket)
#스티커는 받았던것 부터 차례로 붙임 (최대한 붙여야하고 이런거 없음)
#전체에서 1번을 먼저 붙임.
# 단, 붙일 수 없는 경우는 판별해줌
# 붙일 수 없는 경우
# 1. 노트북을 벗어나는경우[조건문]
# 2. 회전을 시도해본다 (3회전) -> 그래도 벗어나면 버림[시계방향90도로 넘겨주는 함수]
# 붙일 수 있는 경우
# ->맨위, 맨왼쪽에 붙인다. =>[전체에서 스티커 붙여졌는지 확인하는 배열]
# ->다음 스티커로 넘어간다.
# 두번째 스티커를 붙일때 부터는 스티커를 붙일 수 없는 자리를
# 피해서 스티커를 붙여야 한다.
visited=[[0] * m for i in range(n)]
#print('visited', visited)
def rotation(cnt, i):
r, l = stickerPocketEntire[i]
# 3번만 돌림
#90도로 돌리기
tmp = stickerPocket[i]
nn=len(tmp)
mm=len(tmp[0])
tmpList =[]
for qq in range(mm):
tmpList2=[]
for pp in range(nn-1, -1, -1):
tmpList2.append(tmp[pp][qq])
tmpList.append(tmpList2)
#print('before',stickerPocket[i])
stickerPocket[i]=tmpList
stickerPocketEntire[i]=[mm, nn]
# print('after',tmpList)
# print('checkcnt: ', cnt)
cnt+=1
# print('cnt: ', cnt)
return cnt
def backtrack(p, q, i, r, l, visited):
#rem = copy.deepcopy(visited)
rem = [item[:] for item in visited]
# print('초기 rem', rem)
# 이부분 백트래킹으로 구현해야할듯
for j in range(r):
for jj in range(l):
#왼쪽 위부터 조회
nr = p+j
nl = q+jj
if 0<=nr<n and 0<=nl<m:
# print('i:', i, "j:", j, "jj", jj)
if stickerPocket[i][j][jj]==1:
#두번째 스티커를 자리에 붙여본다
if visited[p+j][q+jj]!=1:
#겹치는지 확인후 붙여보기
visited[p+j][q+jj]=1
else:
#겹친다.
#스티커를 붙이기 전으로 원래대로 돌아가기
#visited=copy.deepcopy(rem)
visited=[item[:] for item in rem]
check = 0
# print('리턴 visited', visited)
return visited, check
check = 1
else:
# print("뭐지 nr:", nr, "nl:", nl)
#visited=copy.deepcopy(rem)
visited = [item[:] for item in rem]
check = 0
# print('리턴 visited', visited)
return visited, check
if check == 1:
return visited, check
i=0
cnt=0 # 회전 횟수
check=1
while(1):
r, l = stickerPocketEntire[i]
if (n<r or m<l) or check ==0:
if l<=n and r<=m:
# 모눈종이의 크기가 노트북을 넘어가면
# 90도 회전 적용
# 회전의 조건: 모눈종이가 노트북에 딱 들어맞지 않는경우(단, 가로 세로는 뒤집혔을때 노트북에 들어갈 수 있어야 함)
if cnt <3:
cnt = rotation(cnt, i)
r, l = stickerPocketEntire[i]
else:
i+=1
cnt=0
else:
i+=1
if i == 0:
#항상 0,0에서 부터 시작해야함
for j in range(r):
for jj in range(l):
if stickerPocket[0][j][jj]==1:
visited[j][jj]=1
i+=1
cnt=0
else:
for p in range(n):
for q in range(m):
if i ==k:
break
r, l = stickerPocketEntire[i]
# print('hi')
# print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
visited, check = backtrack(p, q, i, r, l, visited)
# print(visited, 'check: ', check, ' i:', i, 'cnt:', cnt)
# print('hi end')
if check==1 or cnt>3: #스티커를 제대로 붙였을 때
i+=1
cnt=0
if check==0 and cnt>3:
break
if check==0 and cnt>3:
break
if i ==k:
break
#print("?????????")
sum=0
for end in visited:
for end2 in end:
if end2==1:
sum+=1
print(sum)
정답 코드
import sys
n, m, k = map(int, sys.stdin.readline().split())
# 스티커 받고, 스티커 함에 넣기
stickerPocket = [] # 모눈종이 각각 map 모음
stickerPocketEntire=[] # 모눈종이 r, l 모아놓는 함
for i in range(k):
#모눈종이의 행, 열
r, c = map(int, sys.stdin.readline().split())
stickerPocketEntire.append([r,c])
sticker=[]
for j in range(r):
tmp = list(map(int, sys.stdin.readline().split()))
sticker.append(tmp)
stickerPocket.append(sticker)
# 붙여졌나요?
visited=[[0] * m for i in range(n)]
# 90도 회전 함수
def rotation(cnt, i):
r, l = stickerPocketEntire[i]
# (90, 180, 270)도에 해당하게끔 3번만 돌림
sticker = stickerPocket[i]
nn=len(sticker) # 기존의 행을 열로 사용
mm=len(sticker[0]) # 기존의 열을 행으로 사용
newSticker =[]
for qq in range(mm):
tmp=[]
for pp in range(nn-1, -1, -1):
tmp.append(sticker[pp][qq])
newSticker.append(tmp)
stickerPocket[i]=newSticker
stickerPocketEntire[i]=[mm, nn]
# 회전카운트 증가시킴
cnt+=1
return cnt
def backtrack(p, q, i, visited):
# 스티커를 붙일 수 없을 경우, 붙이려는 스티커를 붙이기 전 상태로 돌아오기위한것
rem = [item[:] for item in visited]
# 붙이려는 스티커의 행열 조회
r, c = stickerPocketEntire[i]
for j in range(r): # 행
for jj in range(c): # 열
#왼쪽 위부터 조회
nr = p+j # 행/ 기존 행:n
nc = q+jj # 열/ 기존 열:m
# 스티커가 노트북 범위 안에 들어오면
if 0<=nr<n and 0<=nc<m:
# 모눈종이에서 붙여야 하는 지점인 경우
if stickerPocket[i][j][jj]==1:
# 미리 붙여진 스티커가 없다.
if visited[nr][nc]!=1:
# 스티커 붙이기
check = 1
visited[p+j][q+jj]=1
# 미리 붙여진 스티커가 있다. 겹친다.
else:
# 스티커를 붙이기 전(원래대로)으로 돌아가기
visited=[item[:] for item in rem]
# 스티커를 못붙였다는 표식
check = 0
return visited, check
# 모눈종이에서 빈칸인 경우
else:
continue
# 스티커가 노트북 범위 안에 못을어오면
else:
# 노트북 원상복구
visited = [item[:] for item in rem]
# 스티커를 못붙였다는 표식
check = 0
return visited, check
# 스티커를 정상적으로 붙인 경우
if check == 1:
return visited, check
# 시작 스티커 번호
i=0
# 붙일 스티커 번호가 증가한 후 한번도 스티커를 회전한적 없는경우를 가리기 위한 변수
first=1
# 회전 횟수
cnt=0
# 스티커를 붙이지 않았다는 표식
check=0
needRotation=0
while(1):
rotat=0
# 붙일 스티커가 없는 경우 종료
if i == k:
break
# 스티커의 행 열
r, c = stickerPocketEntire[i]
# 스티커의 행이나 열중 하나가 노트북을 벗어나는 경우
if n<r or m<c:
#스티커의 행을 열로, 열을 행으로 바꿨을때(회전했을 때) 노트북에 들어가는 경우
if c<=n and r<=m:
if cnt <3: # 0-0, 90-1, 180-2, 270-3
cnt = rotation(cnt, i)
rotat = 1
# 회전을 4번다 한 경우, 다음 스티커로 넘어감
else:
i+=1
cnt=0
first=1
# 스티커의 행을 열로, 열을 행으로 바꿨을때(회전했을 때) 노트북에 안들어가는 경우=붙일 수 없는 경우
elif c>n and r>m:
# 다음 스티커로 넘어감
first=1
i+=1
cnt=0
# 스티커가 붙여지지 않았고 0도 일때 스티커 붙이는 시도를 다 해본경우
# 회전이 270까지 되지 않은 경우=> 회전
if check == 0 and first==0 and rotat==0 and needRotation==1:
if cnt<=3:
cnt = rotation(cnt, i)
for p in range(n):
for q in range(m):
# 한번 돌았으면 first=0
rotat=0
first=0
# 붙일 스티커가 없는 경우 종료
if i == k:
break
# 붙일 스티커 붙여보기
visited, check = backtrack(p, q, i, visited)
#스티커를 제대로 붙였으면 빠져나감
if check==1:
break
#다음으로 붙일 스티커로 넘어가고, 회전 횟수 초기화
#스티커를 붙였으면 빠져나감
if check==1:
check = 0
i+=1
cnt=0
first=1
needRotation=0
break
if check == 0:
needRotation=1
if cnt==3:
i+=1
first=1
cnt=0
# 붙일 스티커가 없는 경우 종료
if i ==k:
break
# 노트북에 붙여진 스티커 개수 세기
sum=0
for end in visited:
for end2 in end:
if end2==1:
sum+=1
print(sum)
시간/공간 복잡도
N(40)*M(40)*K(100) = 16000이라 1초 기준으로 NlogN으로 풀어야 하는 문제이다. 근데 문제에서 2초를 주엇으니 사실상
2NlogN인건가?
스터디할 때 물어볼 것
최적화 및 개선
sys 모듈 sys.stdin.readline()을 사용하여 반복적으로 입력받을 때 input()에 비해 시간을 확 줄였음
copy 모듈의 deepcopy함수는 시간을 많이 잡아먹으니, 다른 방식으로 리스트 복사를 해야 시간초과가 나지 않는다.
어려웠던 점
문제를 정확하게 이해해야 빈틈없이 구현할 수 있다.
시뮬레이션 문제는 빈틈없이 구현하는게 가장 중요한것 같다.
알게된 것
copy모듈의 deepcopy()함수는 시간을 많이 잡아먹는다. 따라서 다른 방법을 이용해야한다.(시간초과의 주범)
# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, input().split())
check=[]
for i in range(n):
k, value = input().split()
check.append([k, int(value)])
#받은값 정렬해줌
# check = sorted(check, key = lambda x: x[1])
tmp = []
# 값 받고
for i in range(m):
value = int(input())
tmp.append(value)
tmp.sort()
cnt = 0
for i in tmp:
if i <= check[cnt][1]:
print(check[cnt][0])
else:
while 1:
cnt+=1
if i <= check[cnt][1]:
print(check[cnt][0])
break
# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, input().split())
check=[]
for i in range(n):
k, value = input().split()
check.append([k, int(value)])
#받은값 정렬해줌
# check = sorted(check, key = lambda x: x[1])
tmp = []
# 값 받고
for i in range(m):
value = int(input())
tmp.append(value)
tmp.sort()
############################
mid, high, low = (n-1)//2, n-1, 0
print('mid, high, low:', mid, high, low)
for i in range(m):
target = tmp[i]
print("target:", target)
print("check:", check)
while 1:
if target <= check[mid][1]:
print(check[mid][0])
break
elif target > check[mid][1]:
low = mid+1
mid = (low+high)//2
elif target < check[mid][1]:
high = mid-1
mid = (low+high)//2
bisect 모듈을 통해 풀이한 코드
from bisect import bisect_left
import sys
# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, input().split())
checkChing=[]
checkValue=[]
for i in range(n):
k, value = sys.stdin.readline().split()
checkChing.append(k)
checkValue.append(int(value))
# 값 받고
tmp = []
for i in range(m):
value = int(sys.stdin.readline())
tmp.append(value)
for i in range(m):
target = tmp[i]
tmpIndex=bisect_left(checkValue, target)
print(check2[tmpIndex])
bisect 모듈 없이 풀이한 코드
import sys
# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, sys.stdin.readline().split())
check=[]
for i in range(n):
k, value = sys.stdin.readline().split()
check.append([k, int(value)])
#받은값 정렬해줌
check = sorted(check, key = lambda x: x[1])
tmp = []
# 값 받고
for i in range(m):
value = int(sys.stdin.readline().rstrip())
tmp.append(value)
for i in range(m):
high = len(check)
low = 0
result = 0
target = tmp[i]
while low <= high:
mid = (low + high)//2
if target <= check[mid][1]:
high = mid-1
result = mid
elif target > check[mid][1]:
low = mid+1
print(check[result][0])
시간/공간 복잡도
모든 경우를 다 조회할 경우 N은 100만까지 가능함.
이 경우, 시간 초과를 면하기 위해서는 O(NlogN)의 시간복잡도가 되게끔 코드를 작성해야 한다.
(기존에 작성한 코드에서 사용한 이중 반복문으로 구현하면 안됨,,)
(백준한정)추가시간 없음 이라는 말은 파이썬은 기존에 1초에 2천만번 연산 가능함 원래는 이런말 없으면 1초에 1억번 연산가능함
최적화 및 개선
sys 모듈 sys.stdin.readline()을 사용하여 반복적으로 입력받을 때 input()에 비해 시간을 확 줄였음
어려웠던 점
이분탐색 개념이 가물가물 했다.
어이없는 실수: 받은 값을 정렬함으로써 아무리 알고리즘을 맞게 짜도 출력 자체가 이상하게 되도록 함; (스스로 재앙을 불러옴)
3. quack을 문자마다 0, 1, 2, 3, 4로 표기함. 즉, 오리가 quack을 완성할수록 하나의 인덱스의 값은 0에서 4까지 1씩 증가함
4. 리스트에서 제일먼저 k까지 울은 오리의 index를 따로 다른 리스트를 만들어서 오리를 순서대로 줄세워둠
5. 최근에 k까지 울은 오리를 먼저 뽑아서 (스택 스타일) q를 먼저 줌(해당 인덱스에 0으로 갱신) = 먼저 울게 해준다.
6. 정상적으로 울지 않는 것에 대해서는 예외처리를 통해 처리하고, -1을 출력함.
코드 구현
# 울음 소리를 한 번 또는 그 이상 연속해서 내는 것
# quack이 끝나기전에 q가 나오면 다른 마리인 것.
# quack이 완벽하게 끝나고 또 quack이 완벽하게 끝나면 한마리로 침
tmp = []
s = input()
waitList=[]
check = 0
for i in s:
if i == 'q':
if waitList:
where = waitList.pop()
tmp[where] = 0
else:
tmp.append(0)
elif i == 'u':
try:
where = tmp.index(0)
except ValueError:
check = 1
break
tmp[where]+=1
elif i == 'a':
try:
where = tmp.index(1)
except ValueError:
check = 1
break
tmp[where]+=1
elif i == 'c':
try:
where = tmp.index(2)
except ValueError:
check = 1
break
tmp[where]+=1
elif i == 'k':
try:
where = tmp.index(3)
except ValueError:
check = 1
break
tmp[where]+=1
waitList.append(where)
result = 0
if check ==1:
print(-1)
else:
for i in tmp:
if i == 4:
result +=1
else:
print(-1)
check = 1
break
if check !=1:
print(result)
시간/공간 복잡도
O(N)
최적화 및 개선
따로 하지 않음.
어려웠던 점
리스트에서 특정 값을 통해 index를 구할때, index()함수만 쓸 줄 알았다. 그리고 그 함수가 찾고자 하는 값을 못찾을때 -1을 반환하기 보다는 ValueError를 발생시킬줄 몰랐다. 찾아보니 find()함수가 문자열에서 찾고자 하는 값을 못찾을때 -1을 반환했다.
하지만 find()함수를 사용하지 않았다. quack 우는 것을 숫자로 표기해서 문제푸는게 넘 편한데 다시 문자열로 변환할 필요를 못느꼈다.
처음에 문제의 감을 못잡아서 문자열 앞에서부터 quack을 지워갈 생각을 했다. ㅎ;
코딩테스트 문제 풀면서 예외처리문을 처음 사용해본것 같다. 사용법에 대해서 잘 숙지하고 있어야겠다.
코드에 중복되는 부분이 많아서 함수로 표현을 하면 좋을것 같았다. 함수로 코드를 짜버릇 해야겠다.
가희는jo_test폴더에 들어와 있습니다. 가희는jo_test에 있는 파일N개를 아래 기준에 따라 정렬하려고 합니다.
파일명 (FILENAME) 사전순으로
파일명 (FILENAME)이 같다면 가희가 설치한 OS에서 인식하는 확장자가 붙은 것이 먼저 나오게
1과 2로도 순서를 결정할 수 없다면, 파일 확장자 (EXTENSION) 사전 순으로
파일N개를 문제에서 설명하는 정렬 기준에 따라 정렬해 주세요. 사전순의 기준은 아스키 코드 순입니다.
문제 해결 방법
이름, 확장자 순으로 sorted 함수에서 lambda를 통해 키를 설정후 정렬했다.
이 과정에서 이름이 같은 값 중에서 확장자가 없것에 대해서 (확장자 없는 이름, 확장자 있는 이름) 순일 경우에만 확장자 없는 이름을 확장자 있는 이름 뒤로 자리를 바꿔줬다. 이 조건이 아닐경우, 정렬이 흐트러질 수 있기때문이다.
코드 구현
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
name = [input().rstrip() for _ in range(N)]
extent = set(input().rstrip() for _ in range(M))
tmpValue = []
for value in name:
tmpValue.append(value.split('.'))
#print(extent)
tmpValue = sorted(tmpValue, key = lambda x: (x[0], x[1]))
# sorted함수에 key를 lambda함수로 정해줬다.
#print('tmpValue', tmpValue)
for i in range(N-1):
if tmpValue[i][0] == tmpValue[i+1][0]:
if tmpValue[i][1] not in extent and tmpValue[i+1][1] in extent:
tmp = tmpValue[i]
tmpValue[i] = tmpValue[i+1]
tmpValue[i+1] = tmp
#print('tmpValue', tmpValue)
for i in tmpValue:
#strr, extt = i
print(i[0]+'.'+i[1])
시간/공간 복잡도
O(N)
최적화 및 개선
input을 통해 하나의 변수가 아닌 여러 변수를 연속적으로 받을때는 입력에 input함수를 사용하면 시간초과가 걸릴 수 있
다. 이를 개선하기 위해 sys.stdin.readline을 사용하면 시간을 줄일 수 있다.
특정 값이 순서와 관계없이 시퀀스 자료에서 존재하는지 확인만 하고 싶을 경우, 해당 시퀀스 자료의 자료형을 set으로 설정하는 것이 list나 다른 자료형 보다 시간을 확 줄일 수 있다.
근거는 다음과 같다.
Set은 List보다 더 빠른 탐색 속도를 가진다.
그 이유는 내부적인 데이터 구조와 탐색 알고리즘의 차이 때문입니다.
1. 데이터 구조:
- Set은 해시 테이블(Hash Table)로 구현되어 있습니다. 해시 테이블은 값에 대한 고유한 해시 코드를 계산하고, 해당 해시 코드를 기반으로 값을 저장하고 검색합니다. 이렇게 함으로써 Set은 중복된 값을 허용하지 않으며, 값에 상수 시간(O(1))으로 접근할 수 있습니다.
- List는 배열(Array)로 구현되어 있습니다. 배열은 각 요소가 인덱스로 직접 접근되므로 인덱스를 알면 상수 시간(O(1))에 해당 요소에 접근할 수 있습니다. 하지만 List에서 값을 검색하기 위해서는 전체 리스트를 순회해야 하므로 최악의 경우 선형 시간(O(N))이 걸릴 수 있습니다.
2. 탐색 알고리즘:
- Set에서 값의 존재 여부를 확인하는 연산은 내부적으로 해시 함수와 버킷(bucket)을 사용하여 상수 시간O(1) 안에 처리됩니다.
- List에서 값의 존재 여부를 확인하기 위해서는 순차적인 비교 연산을 수행해야 합니다. 따라서 최악의 경우 리스트의 모든 요소를 순회해야 하므로 선형 시간O(n)이 걸립니다. 따라서 Set은 내부적인 데이터 구조와 탐색 알고리즘을 통해 중복을 제거하고 빠른 탐색 속도를 제공합니다.
그러나 Set은 순서가 보장되지 않으며, 인덱스 기반 접근이 불가능하기 때문에 특정 위치의 요소에 바로 접근하는 용도보다는 멤버십(Membership) 확인(=존재유무확인) 등을 위한 용도로 주로 사용됩니다.
철수는 롤케이크를 두 조각으로 잘라서 동생과 한 조각씩 나눠 먹으려고 합니다. 이 롤케이크에는 여러가지 토핑들이 일렬로 올려져 있습니다. 철수와 동생은 롤케이크를 공평하게 나눠먹으려 하는데, 그들은 롤케이크의 크기보다 롤케이크 위에 올려진 토핑들의 종류에 더 관심이 많습니다. 그래서 잘린 조각들의 크기와 올려진 토핑의 개수에 상관없이 각 조각에 동일한 가짓수의 토핑이 올라가면 공평하게 롤케이크가 나누어진 것으로 생각합니다.
예를 들어, 롤케이크에 4가지 종류의 토핑이 올려져 있다고 합시다. 토핑들을 1, 2, 3, 4와 같이 번호로 표시했을 때, 케이크 위에 토핑들이 [1, 2, 1, 3, 1, 4, 1, 2] 순서로 올려져 있습니다. 만약 세 번째 토핑(1)과 네 번째 토핑(3) 사이를 자르면 롤케이크의 토핑은 [1, 2, 1], [3, 1, 4, 1, 2]로 나뉘게 됩니다. 철수가 [1, 2, 1]이 놓인 조각을, 동생이 [3, 1, 4, 1, 2]가 놓인 조각을 먹게 되면 철수는 두 가지 토핑(1, 2)을 맛볼 수 있지만, 동생은 네 가지 토핑(1, 2, 3, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것이 아닙니다. 만약 롤케이크의 네 번째 토핑(3)과 다섯 번째 토핑(1) 사이를 자르면 [1, 2, 1, 3], [1, 4, 1, 2]로 나뉘게 됩니다. 이 경우 철수는 세 가지 토핑(1, 2, 3)을, 동생도 세 가지 토핑(1, 2, 4)을 맛볼 수 있으므로, 이는 공평하게 나누어진 것입니다. 공평하게 롤케이크를 자르는 방법은 여러가지 일 수 있습니다. 위의 롤케이크를 [1, 2, 1, 3, 1], [4, 1, 2]으로 잘라도 공평하게 나뉩니다. 어떤 경우에는 롤케이크를 공평하게 나누지 못할 수도 있습니다.
롤케이크에 올려진 토핑들의 번호를 저장한 정수 배열 topping이 매개변수로 주어질 때, 롤케이크를 공평하게 자르는 방법의 수를 return 하도록 solution 함수를 완성해주세요.
문제 해결 방법
topping을 딕셔너리를 통해 분류후 개수를 센다.
집합 자료형을 하나 만들어서 topping을 순회하며 하나씩 담고, topping 딕셔너리에도 수정사항을 반영해준다.
이때, 집합 자료형과, 만들어둔 딕셔너리의 크기를 비교해서 같으면 카운트 해준다.
코드 구현
from collections import Counter
def solution(topping):
answer = 0
topping_counter = Counter(topping)
# print(len(topping_counter)) 딕셔너리의 키 개수가 나옴
half_topping_set = set()
for t in topping:
half_topping_set.add(t)
topping_counter[t] -= 1
if topping_counter[t] == 0:
topping_counter.pop(t)
if len(half_topping_set) == len(topping_counter):
answer +=1
return answer
시간/공간 복잡도
O(n)
최적화 및 개선
처음에는 슬라이스도 쓰고 이중반복문도 쓰고 해서 거의 O(N^3)의 시간복잡도로 코드를 작성했는데 시간초과가 나서 수정했다.
어려웠던 점
딕셔너리를 저렇게 활용할 생각을 못했다.
저렇게 구현하는 방법을 생각해내는 것이 어렵다.
딕셔너리의 개수를 세아리면 key의 개수가 나온다는 것을 알게됐고, 딕셔너리는 키값으로 pop()을 하면 해당 키값과 value값은 삭제되는 것을 알게됐다. set함수는 값을 추가할 때, add를 사용하는것을 완전히 알게됐다.
그리고 리스트가 있을때, 딕셔너리의 형태로 정리하고싶으면 Counter함수를 사용하면 쉽게 정리가 된다는 것을 알게됐다.
N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.
이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다. 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.
각 격자칸의 높이가 담긴 2차원 배열 land와 이동 가능한 최대 높이차 height가 매개변수로 주어질 때, 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값을 return 하도록 solution 함수를 완성해주세요.
제한사항
land는 N x N크기인 2차원 배열입니다.
land의 최소 크기는 4 x 4, 최대 크기는 300 x 300입니다.
land의 원소는 각 격자 칸의 높이를 나타냅니다.
격자 칸의 높이는 1 이상 10,000 이하인 자연수입니다.
height는 1 이상 10,000 이하인 자연수입니다.
문제 해결 방법
BFS를 활용해서 문제를 풀었다. 그런데 BFS를 할 때, 고려해줘야 하는게 있었다.
바로 사다리 설치비용이다. 문제에서 요구한대로 최소한의 사다리 설치 비용을 산출해내야 되기 때문에, 좌표에서 상, 하, 좌, 우 이동시 발생할 수 있는 사다리 설치 비용에 대해서 우선순위를 매겨야한다. 이때 heapq 우선순위 큐를 활용하여 문제를 해결했다.
코드 구현
BFS, heapq 자료구조를 이용해 풀이한 코드
import heapq
def solution(land, height):
answer = 0
# 좌표 움직임을 위한 배열
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
#시작 좌표
startX, startY = 0, 0
# 방문 여부 확인을 위한 배열
visited = [[False] * len(land) for _ in range(len(land[0]))]
heap = []
def bfs(stratX, startY):
answer = 0
heapq.heappush(heap, [0, startX, startY]) # 비용, startX, startY
while len(heap) != 0:
cost, x, y = heapq.heappop(heap)
#print('cost', cost)
if visited[y][x] == False:
visited[y][x] = True
answer += cost
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 새로운 좌표가 정사각 격자 형태의 지형을 벗어나는지 체크
if ny >= len(land) or nx >= len(land[0]) or ny < 0 or nx < 0:
continue
if abs(land[y][x]-land[ny][nx]) <= height:
newcost = 0
else:
newcost = abs(land[y][x]-land[ny][nx])
heapq.heappush(heap, [newcost, nx, ny])
return answer
answer = bfs(startX, startY)
#print(answer)
return answer
BFS구현 및 deque로 구현하려다가 실패한 코드
from collections import deque
def solution(land, height):
answer = 0
realAnswer = 0
# 좌표 움직임을 위한 배열
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
#시작 좌표
startX, startY = 0, 0
# 방문 여부 확인을 위한 배열
visited = [[False] * len(land) for _ in range(len(land[0]))]
check = [[10000] * len(land[0]) for _ in range(len(land))]
print(visited)
queue = deque()
def bfs(stratX, startY):
#시작하는 좌표를 큐에 넣고,
# 큐에 값이 있으면 큐에서 값을 꺼내어 방문 처리를 한다.
# 꺼낸 값에 인접한 값 중에서 방문하지 않은 좌표인지 확인한 후,
# 방문하지 않았으면 큐에 넣는다.
queue.append([startX, startY])
nx = 0
ny = 0
while len(queue) != 0:
x, y = queue.popleft()
visited[y][x] = True
print('')
print('x, y', x, y)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
print('i', i, 'nx, ny:', nx, ny)
# 새로운 좌표가 정사각 격자 형태의 지형을 벗어나는지 체크
if ny >= len(land) or nx >= len(land[0]) or ny < 0 or nx < 0:
print('?1')
continue
if visited[ny][nx] == True:
print(visited)
print('?2')
continue
print('nx, ny', nx, ny, 'x', 'y', x, y)
print(land[y][x], land[ny][nx])
if abs(land[y][x]-land[ny][nx]) <= height:
check[ny][nx] = abs(land[y][x]-land[ny][nx])
print('input', nx, ny)
queue.append([nx, ny])
# else:
# if check[ny][nx] > abs(land[y][x]-land[ny][nx]):
# check[ny][nx] = abs(land[y][x]-land[ny][nx])
# print('input', nx, ny)
# queue.append([nx, ny])
bfs(startX, startY)
check[0][0]=0
print('check', check)
return answer
