[1번째 Contest]
100 버추얼 챌린지를 시작했다. 이게 첫번째 버추얼이다.
버추얼은 퍼포를 어떻게 보는지 알 수가 없다. 그래서 그냥 몇 솔로 기록하려고 한다. 처음은 무난하게 3솔 했다.
B, C를 dfs로 풀었는데, 파이썬 억까를 당해서 개같이 멸망했다.
A. Lex String
두 개의 문자열 a, b가 주어진다. 사전 순으로 가장 앞서는 문자열 c를 만들어라.
Operation: a 또는 b에 있는 아무 문자열 하나를 빼고, c의 맨 뒤에 추가할 수 있다. 이 작업은 a나 b 한 문자열에 대해서 최대 k번 연속으로 할 수 있고, 한 문자열에서 k번 작업을 했으면 그 다음은 다른 문자열에서 작업을 실행해야 한다. a 또는 b 가 빌 때까지 위 작업을 계속한다.
풀이
문제에서 제시하는 그대로 하면 된다. a, b를 하나씩 쪼개서 스택에 넣고 사전 역순으로 정렬한다. a, b 스택 마지막 원소를 비교해서 사전 순으로 앞선 문자을 pop해서 c에 push 해주면 된다. k번 이상 동일 문자열에서 작업을 실행할 수 없으므로 잘 처리하면 된다.
난 귀찮아서 좀 길게 처리했지만, 더 똑똑한 방법이 있겠지.
코드
n, m, k = map(int, input().split())
a = list(input())
b = list(input())
a.sort(reverse=True)
b.sort(reverse=True)
c = ''
cnt1, cnt2 = 0, 0
while a and b:
if a[-1] < b[-1]:
if cnt1==k:
c += b.pop()
cnt1, cnt2 = 0, 1
else:
c += a.pop()
cnt1 += 1
cnt2 = 0
else:
if cnt2==k:
c += a.pop()
cnt1, cnt2 = 1, 0
else:
c += b.pop()
cnt2 += 1
cnt1 = 0
print(c)
for __ in range(int(input())):
solve()B. Mystic Permutation
길이가 n인 permutation이 주어진다. permutation은 1부터 n까지 중복이 없는 수가 나열된 거다. 우리가 할 일은 새로운 permutation을 만드는 건데, 주어진 permutation과 모든 위치에 대해 다른 값이어야 한다.
수식으로 표현하면, 이고, 는 각각 주어진 permutation과 새로운 permutation이다. 위 조건을 만족하는 permutation 중에 사전 순으로 앞서는 걸 찾아야 한다.
풀이
간단한 dfs 문제라고 파악했다. (python으로 풀면서 억까 당할까봐 두려웠다,,) 너무 간단해서 자세한 설명은 생략하고, 에디토리얼 풀이도 추가로 정리해봤다.
코드
# 내 무지성 dfs 풀이
def solve():
n = int(input())
arr = list(map(int, input().split()))
arr = [(arr[i], i) for i in range(n)]
arr.sort()
visited = [0]*1010
def dfs(idx):
if idx==n:
return [0]
for i in range(n):
if not visited[i] and arr[i][1]!=idx:
visited[i] = 1
ret = dfs(idx+1)
if ret!=[-1]:
return [arr[i][0]] + ret
visited[i] = 0
return [-1]
ans = dfs(0)
if ans[-1]==0:
ans.pop()
print(*ans)
for __ in range(int(input())):
solve()에디토리얼은 반복문으로 풀었다. 실제로 이런 풀이 방식이 웰논 같은데 난 아직 무지성 dfs가 편한가보다,,,
1번째부터 n-2번째까지의 값을 구해준다. 이건 각 i번째 값을 구할 때, 1부터 n까지 탐색하며 아직 쓴 적이 없다면 i번째 값으로 바로 출력한다. 여기서 n-2번째까지 하는 이유가 있는데 n-2번째까지는 위 방식으로 하면 문제가 없다. 마지막 n-1과 n-2번째는 문제가 생길 수 있다.
# 에디토리얼의 예쁜 코드
def solve():
n = int(input())
arr = list(map(int, input().split()))
if n==1:
print(-1)
return
visited = [0]*1010
for i in range(1, n-1):
k = 1
while visited[k] or arr[i-1]==k:
k += 1
print(k, end=' ')
visited[k] = 1
a, b = 0, 0
for i in range(1, n+1):
if not visited[i]:
if a:
b = i
else:
a = i
if a==arr[n-2] or b==arr[n-1]:
print(b, a)
else:
print(a, b)
for __ in range(int(input())):
solve()마지막으로 짜리 풀이도 있다. 주어진 permutation과 [1, ..., n]으로 구성된 permutation을 비교하면서 swap해주는 방식이다. 이것도 마지막 원소에서 예외가 발생할 수 있어서 처리가 필요하다. 예시를 끄적여보면 알 수 있어서 패스,, (사실 다 쓰고 날라감)
// 에디토리얼의 O(n) 짜리 예쁜 코드
import sys
input = lambda : sys.stdin.readline().rstrip()
def solve():
n = int(input())
arr = list(map(int, input().split()))
brr = list(range(1, n+1))
if n==1:
print(-1)
return
for i in range(n-1):
if arr[i]==brr[i]:
brr[i], brr[i+1] = brr[i+1], brr[i]
if arr[n-1]==brr[n-1]:
brr[n-2], brr[n-1] = brr[n-1], brr[n-2]
print(*brr)
for __ in range(int(input())):
solve()
C. Infected Tree
최상위 루트 노드가 1로 고정된 이진 트리가 주어진다. 노드 1은 감염된 상태이고 자식 노드로 감염은 이동한다. 1번에 1칸씩 감염이 진행되는데, 우리는 트리를 끊어서 감염을 멈춰야 한다. 최대한 많이 살릴 수 있는 노드 수를 구하라.
풀이
코드
D. Lena and Matrix
풀이
코드
