Codeforces Round 855 (Div. 3) (버츄얼)

 

결과

 

A번 풀이

문제

https://codeforces.com/contest/1800/problem/A

Problem - A - Codeforces

알고리즘 분류 

문자열, 구현

 

풀이

딱 보자마자 어떤 문제인지는 감이 왔다.

그런데 막상 구현하려니 생각보다 애를 많이 먹었다.

결과적으로는 스택을 이용해서 풀어주었지만 분명 더 좋은 풀이가 있을 것이란 생각이 든다.

 

m, e, o, w 중 하나라면 스택의 맨 위의 값과 비교해서 넣거나 넣지 않는다.

결국 순서대로 알맞게 들어갔다면 스택 안에는 4개의 값만 들어있을 것이고 그것이 정답 배열과 같다면 "YES" 아니면 "NO 를 출력해주었다.

from sys import stdin
input=stdin.readline
for i in range(int(input())):
    n=int(input())
    s=[i.lower() for i in input().rstrip()]
    order=['w','o','e','m']
    idx=0
    st=[]
    while s:
        now=s.pop()
        if st and st[-1]==now and now in order:
            pass
        else:
            st.append(now)
    if st==order:
        print('YES')
    else:
        print('NO')

 

B번 풀이

문제

https://codeforces.com/contest/1800/problem/B

Problem - B - Codeforces

알고리즘 분류 

그리디, 문자열

 

풀이

조금 고민을 했던 문제이다.

일단 각 알파뱃의 대문자와 소문자의 개수를 저장해준 뒤 각 알파벳의 min(대문자의 개수, 소문자의 개수) 만큼 더해서 k번의 변경 없는 상태에서의 쌍의 개수를 구할 수 있다.

 

그리고 대문자의 개수와 소문자의 개수의 차이를 이용해서 정답을 구해주면 된다. 대문자의 개수가 하나 늘거나 줄 때 소문자의 개수는 하나 줄거나 늘게 된다는 사실을 명심해야 한다.

 

따라서 대소문자 개수 차이의 // 2만큼 k번 바꿔주면 답을 구할 수 있다.

from sys import stdin
input=stdin.readline

for _ in range(int(input())):
    n,k=map(int,input().split())
    s=input().rstrip()
    l=[0]*26
    u=[0]*26
    for i in range(n):
        if s[i].isupper():
            u[ord(s[i])-65]+=1
        else:
            l[ord(s[i])-97]+=1
    ans=0
    for i in range(26):
        if abs(l[i]-u[i])//2<=k:
            k-=abs(l[i]-u[i])//2
            l[i]=u[i]=abs(l[i]-u[i])//2+min(l[i],u[i])
        else:
            l[i]=u[i]=min(l[i],u[i])+k
            k=0
        ans+=min(l[i],u[i])
    print(ans)

 

C(1,2)번 풀이

문제

https://codeforces.com/contest/1800/problem/C1

Problem - C1 - Codeforces

https://codeforces.com/contest/1800/problem/C2

Problem - C2 - Codeforces

알고리즘 분류 

그리디

풀이

스택+우선순위 큐로 해결했다.

살짝 뇌절한 부분이 있었지만 일단 중요한 것은 영웅 카드를 뽑기 전까지 얻은 보너스 카드중 가장 큰 카드들만 사용하면 된다.

이 때 적절한 방법을 이용해서 이전까지 나온 카드 중 가장 큰 값을 계속 맨 위로 올려주면 된다.

나는 스택과 우선순위 큐를 이용해주었다.

 

from sys import stdin
from heapq import heappush,heappop
input=stdin.readline

for _ in range(int(input())):
    n=int(input())
    deck=list(map(int,input().split()))
    bonusdeck=[]
    ans=0
    discard=[]
    for i in range(n):
        if deck[i]==0:
            if bonusdeck and discard:
                if bonusdeck[-1]<-discard[0]:
                    ans-=heappop(discard)
                else:
                    ans+=bonusdeck.pop()
            elif bonusdeck:
                ans+=bonusdeck.pop()
            elif discard:
                ans-=heappop(discard)
        else:
            if bonusdeck:
                if bonusdeck[-1]<=deck[i]:
                    bonusdeck.append(deck[i])
                else:
                    heappush(discard,-deck[i])
            else:
                bonusdeck.append(deck[i])
    print(ans)

 

D번 풀이

문제

https://codeforces.com/contest/1800/problem/D

Problem - D - Codeforces

알고리즘 분류 

그리디, 문자열, 자료구조

 

풀이

연속된 2개의 문자를 지웠을 때 나오는 경우의 수를 구하는 문제이다.

연속된 글자를 지웠을 때 같은 결과가 나오는 경우를 생각해보았다.

글자 3개가 있을 때 모두 같은 경우(aaa) 어떤 2개를 지워도 다 같은 결과이다. 앞 뒤만 같은 경우 (aba) 마찬가지로 어떤 2개를 지워도 다 같은 결과이다.

따라서 이전에 지운 문자열과 비교를 해서 set(s[i-1]+s[i]) == set(s[i]+s[i+1]) 인 경우 이전에 지운 것과 동일한 결과를 낳는다.

 

from sys import stdin
from math import comb as c
from collections import defaultdict
input=stdin.readline

for _ in range(int(input())):
    n=int(input())
    s=input().rstrip()
    bef=''
    cnt=0
    for i in range(1,n):
        now=s[i]+s[i-1]
        if set(now)!=set(bef):
            cnt+=1
        bef=now
    print(cnt)

 

 

E번 풀이

문제

https://codeforces.com/contest/1800/problem/E1

Problem - E1 - Codeforces

https://codeforces.com/contest/1800/problem/E2

Problem - E2 - Codeforces

알고리즘 분류 

DFS, 구성적

 

풀이

문자 하나를 노드로 생각하고 그 문자와 거리가 k, k+1인 노드들이 연결되어 있다고 생각하고 풀면 될 거라 생각했다. 이 연결된 노드들을 구성하는 문자들이 순서와는 상관없이 동일하지 않다면 불가능하다고 생각했다.

그런데 왜인지 계속 런타임 에러가 발생해서 굉장히 고생을 했다.

 

그래서 생각을 뒤집어 보았다. 구성하는 문자열이 될 수 없는 문자열들이 있다. 예를 들어 해당 위치가 idx-k<0 그리고 idx+k<=n 인 경우 움직일 수 없는 곳이다. 해당 위치의 문자열이 아니라면 결국 하나의 문자열로 묶이게 되어있다.

따라서 해당 위치의 s[idx]와 t[idx]가 다르다면 NO 모두 같다면 YES를 출력해주면 된다.

 

from sys import stdin
input=stdin.readline

def solve():              
    n,k=map(int,input().split())
    s=input().rstrip()
    t=input().rstrip()
    if sorted(s)!=sorted(t):
        return 0
    able=True
    for i in range(n):
        if i-k<0 and i+k>=n:
            if s[i]!=t[i]:
                return 0
    return 1

for _ in range(int(input())):
    print("YES" if solve() else "NO")