이 문제는 두 개의 배열을 입력받아서 첫번째 것을 두번째 배열과 똑같이 만들려고 하는 것이다. 방법은 2가지인데, W,B가 있으면 두개를 바꾸던가 W->B(혹은 B->W) 이런식으로 바꿀 수 있다. W,B 2개를 바꾸면 한번에 2자리가 해결되는 것이므로 위치 바꿀 수 있으면 이 방법이 최소 횟수일 것이다.
n = int(input())
first = input()
second = input()
for i in range(n):
if first[i]!=second[i]:
arr.append(first[i])
내가 어려웠던 곳은 일단 서로 배열이 다르면 arr 배열에 저장해두었는데, 이걸 어떻게 해야 뒤집고 바꾸는 갯수를 다 알 수 있을까였다. 다른 곳이 짝수이면 나누기 2를 해주어서 몫을 더해줄까.. 이런 생각도 해보았는데
결국은 W랑 B가 있으면 더 큰 수를 출력하면 된다. arr에 입력받은 것이 만약 WBB라면 W랑 B는 서로 위치 바꾸어서 한 번이고, B하나 남은건 W로 바꾸어 줄테니까 총 개수가 2이다.
이건 결국 W랑 B중에 더 큰 수의 개수를 정답으로 하면 된다.
t = int(input())
arr=[]
ans=0
answer=[]
for i in range(t):
n = int(input())
first = input()
second = input()
for i in range(n):
if first[i]!=second[i]:
arr.append(first[i])
if arr.count('B')>=arr.count('W'):
ans=arr.count('B')
else:
ans = arr.count('W')
answer.append(ans)
arr=[]
for a in answer:
print(a)
요세푸스 문제(https://jobdong7757.tistory.com/113?category=916339)와 비슷했던것 같다. 근데 문제는 여기서 s 배열에 음수가 존재하면 오른쪽이 아닌 왼쪽으로 원을 둘러서 가야된다는 사실이다. 이 부분때문에 헷갈려서 헤매었다. 그리고 처음 시작점이 여기서는 0으로 지정되어있다. 그래서 한번 삭제를 하고 반복문을 돌려주어야 한다.
[나의 해결 방안]
n=int(input())
s=list(map(int,input().split()))
start=0
index=[x for x in range(1,n+1)]
answer=[]
temp = s.pop(start)
answer.append(index.pop(start))
while s:
if temp<0:
start = (start+temp)%len(s)
else:
start=(start+temp-1)%len(s)
temp = s.pop(start)
answer.append(index.pop(start))
for i in answer:
print(i,end=' ')
n과 s는 주어진 입력이고 start에는 다음 지점을 저장해주려고 하였다. index는 정답에 저장하기 위해서(정답은 0 index를 1로 바꿔서 출력해주어야하기 때문)에 사용하였다. temp에는 s배열의 값을 temp에 저장해주었다.
while문을 하기 전에 이 문제는 시작점이 0으로 정해져있기 때문에 start=0으로 초기화 하고 temp는 s의 start값의 index를 pop해서 저장해준다.
while문을 이제 시작할때 temp의 값이 음수일때가 문제인데 이 문제를 python의 나머지 기호(%)를 잘몰랐던 나의 무지였었다.
https://seokdev.site/204 이 사이트에서 다시 공부하고 왔다.. python에서는 c언어의 %와 달리 -1%10을 하면 9가 나오게 된다. 즉, A%B 가 있으면, A에다가 B를 계속 더하면서 처음으로 양수가 되었을 때 B로 나눠 나머지를 준다.
예를 들어 -1%10이면 -1+10=9, 9%10=9 이런식으로 나오는 것이다.
이 문제에서 temp가 음수이면 그냥 start에 temp를 더해서 s의 길이로 나누면 왼쪽으로 -temp만큼 가는것처럼 보이게 되는 것이다. 그래서 temp<0일 때를 처리해 줄 수 있다.
[다른 사람 풀이]
위의 풀이가 temp<0을 처리하기 제일 용이했었는데 그것 말고도 deque에 temp<0을 처리해줄 수 있는 방법도 있었다.
enumerate는 반복문 사용 시 몇 번째 반복문인지 확인이 필요할 때 사용할 수 있다. 이거는 index 번호와 collection의 원소를 tuple 형태로 반환한다.
예를 들어 이런식이다.
t = [1, 5, 7, 33, 39, 52]
for p in enumerate(t):
print(p)
(0, 1)
(1, 5)
(2, 7)
(3, 33)
(4, 39)
(5, 52)
그리고 deque의 rotate() 메서드.
deque.rotate(num)을 하면 deque를 num만큼 회전한다.(양수면 오른쪽, 음수면 왼쪽)
문제가 복잡하게 적혀 있는데 괄호로 표현해주어서 이해하기 쉬웠다. 처음에 생각한것은 쇠막대기와 레이저의 출발과 끝을 따로 배열로 저장해서 하나씩 볼려고 하였다. 물론 직관적으로 바로 풀었는데 O(n^2)이라서 문제 맞추면 더 좋은 풀이 생각해야지 했더니만 역시.. 시간초과가 뜨고 말았다.
[처음 풀이] 예시들은 제대로 출력되지만 더 빠른 방법이 정답일것 같았다.
s=input()
pipe=[]
raser=[]
stack=[]
answer=0
for i in range(len(s)):
if s[i]=='(':
stack.append(i)
elif s[i]==')':
if s[i-1]=='(':
stack.pop()
raser.append((i-1,i))
else:
pipe.append((stack.pop(),i))
for i in pipe:
count=0
for j in raser:
if i[0]<j[0] and i[1]>j[0]:
count+=1
answer+=count+1
print(answer)
괄호는 '(', ')' 두개밖에 없고 '('인 경우는 쇠파이프 1개가 새로 시작하거나, 레이저인 경우밖에 없고, ')'인 경우는 쇠파이프 1개가 끝나거나 레이저인 경우밖에 없으므로 결국 input받은걸 하나씩 분석해가면 O(n)안에 문제를 해결할 수 있다.
[나의 해결 방안]
'('인 경우에는 stack안에 집어넣고 ')'인 경우 앞에 것이 바로 '('이면 레이저이므로 stack에 넣은 '('를 빼내준다. 그리고 레이저로 자르면 되는데 이때는 stack의 크기만큼 나온다.
그리고 ')'를 만났는데 그 앞에게 ')'인 경우는 막대기 하나가 끝난경우로 보면 되므로 stack에서 하나 pop해주고 정답을 +1해준다.
s=input()
stack=[]
answer=0
# '('가 들어오는 경우 -> 쇠파이프 1개가 새로 시작하거나, 레이저인 경우
# ')'가 들어오는 경우 -> 쇠파이프 1개가 끝나거나, 레이저인 경우
for i in range(len(s)):
if s[i]=='(':
stack.append(i)
elif s[i]==')':
if s[i-1]=='(':
stack.pop()
answer+=len(stack)
elif s[i-1]==')':
stack.pop()
answer+=1
print(answer)
제일 먼저 생각한것은 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번째 자릿수까지 출력함으로써 소수점을 관리할 수 있다.
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]))
문제 자체는 이해하기 단순했다. 그냥 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이기 때문에 간단하게 풀 수 있을 거라고 생각했다.
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]
처음에 많이 헤맸었다. 먼저 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])
