ABC 301 복기.. C - AtCoder Cards (문자열 그리디 알고리즘)

1. 문제

 

C - AtCoder Cards

C - AtCoder Cards

 

2. 풀이

 

문제는 요약하자면 두 문자열이 주어지는데, @는 a,t,c,o,d,e,r중 하나로 바꿀 수 있다.

 

두 문자열을 적절하게 배열시켰을때, 서로 같게 만들 수 있느냐? 불가능하느냐?

 

딱 봤을때는 도저히 모르겠더라..

 

최대 길이가 2*10^5인게 압박

 

브루트포스로 하면 당연히 시간초과일거고

 

근데 계속 보면서 생각해보니까 그리디적으로 사고했을때 두 문자열의 구성이 같으면 결국에 서로 같게 만들 수 있잖아

 

그러니까 굳이 정렬, 배열 안시켜봐도, 두 문자열의 구성이 같은지 아닌지만 검사하면 된다는 소리

 

그래서 먼저 Counter를 이용해서 두 문자열 s,t의 구성을 찾는다

 

from collections import Counter
 
s = Counter(input())
t = Counter(input())

 

s의 key,value를 순회해서 t에 key,value가 존재하는지 검사해볼건데...

 

여기서 집중해서 사고해야돼

 

s에 존재하는 key에 대응하는 value가 t에 정확히 일치해서 존재해야함

 

s에 존재하는 key가 t에 존재하지 않는다면?

 

1) t에 @가 존재하는지 확인

 

t에 @가 없다면, key로 바꿀수 없기때문에 어떻게 해도 s,t의 구성은 같을 수가 없다

 

바로 no를 return

 

@가 있다고 하더라도, @의 수가 value만큼 존재하지 않는다면, 당연히 s,t의 구성이 같을수가 없다

 

value 이상으로 존재해준다면, @의 수를 value만큼 줄이고, t에 해당 key의 value를 s의 key의 value만큼 넣어준다

 

from collections import Counter
 
s = Counter(input())
t = Counter(input())

for k,v in s.items():

    if t.get(k,0) == 0:

        if t.get('@',0) < v:

            no = True
            break
            
        else:
                
            t['@'] -= v
            t[k] = v

 

2) 근데 s에 존재하는 key가 t에 존재할 수 있어

 

이 때 s의 key의 value만큼 존재해야 넘어가는데, 그 만큼 존재하지 않는다면?

 

t의 @수로 바꿔서 채워넣어야지

 

구체적으로 t[k] < v이면, t의 @수를 확인해서, v-t[k]만큼 존재하지 않는다면... s,t의 구성은 같을 수 없으니 no를 return

 

그 이상 존재한다면 바꿔주면 될것

 

from collections import Counter
 
s = Counter(input())
t = Counter(input())
 
no = False
 
for k,v in s.items():

    if t.get(k,0) == 0:

        if t.get('@',0) < v:

            no = True
            break

        else:

            t['@'] -= v
            t[k] = v

    else:


        if t[k] < v:

            if t.get('@',0) == 0:

                no = True
                break

            else:

                if t['@'] < (v-t[k]):

                    no = True
                    break

                else:

                    t['@'] -= (v-t[k])
                    t[k] += (v-t[k])

 

근데 t[k] < v만 확인하고 t[k] > v는 확인안해?

 

이 경우는 s에서 @를 이용해 바꿔야겠지.. s에서 부족하다는 소리니까

 

그래서 s에서 k,v를 순회해서 t에 맞춰주었다면

 

이번에는 t에서 k,v를 순회해서 s에 똑같이 맞춰주는 작업을 수행

 

코드가 길어지니까 함수를 정의해서 s,t를 받아 no를 return해주고

 

t,s를 받아 no를 return해서.. 최종적으로 yes,no를 찾는 방식으로

 

from collections import Counter
 
s = Counter(input())
t = Counter(input())
 
no = False
 
def f(s,t,no):
 
    for k,v in s.items():
        
        if t.get(k,0) == 0:
            
            if t.get('@',0) < v:
                
                no = True
                break
            
            else:
                
                t['@'] -= v
                t[k] = v
        
        else:
            
            
            if t[k] < v:
                
                if t.get('@',0) == 0:
                    
                    no = True
                    break
                
                else:
                    
                    if t['@'] < (v-t[k]):
                        
                        no = True
                        break
                    
                    else:
                        
                        t['@'] -= (v-t[k])
                        t[k] += (v-t[k])
    
    return no
 
no = f(s,t,no)
 
if no:
    
    print('No')
 
else:
    
    no = f(t,s,no)
 
    if no:
        
        print('No')
    
    else:
    
        print('Yes')

 

 

먼저 f(s,t,no)로 이게 no가 나온다면.. f(t,s,no)는 확인할 필요도 없이 바로 No를 출력하고

 

f(s,t,no)가 yes로 나온다면.. 다음 f(t,s,no)를 확인해서 이것도 yes라면 Yes를 출력하고 no라면 No를 출력하고

 

근데 이렇게 하면... 아직 고려하지 못한 부분이

 

먼저 @는 a,t,c,o,d,e,r중 하나만 바꿀수 있다는 점이야

 

그러니까 s에서 k,v를 순회했는데 t에 k가 없어

 

그래서 t의 @를 이용해 바꿀려고 하는데 k가 a,t,c,o,d,e,r중 하나가 아니라면.. 바꿀수도 없으니까

 

바로 no를 return하자.

 

from collections import Counter
 
s = Counter(input())
t = Counter(input())
 
no = False
 
replace_list = ['a','t','c','o','d','e','r']
 
def f(s,t,no):
 
    for k,v in s.items():
        
        if t.get(k,0) == 0:
            
            if k not in replace_list:
                
                no = True
                break
            
            if t.get('@',0) < v:
                
                no = True
                break
            
            else:
                
                t['@'] -= v
                t[k] = v
        
        else:
            
            
            if t[k] < v:
                
                if t.get('@',0) == 0 or k not in replace_list:
                    
                    no = True
                    break
                
                else:
                    
                    if t['@'] < (v-t[k]):
                        
                        no = True
                        break
                    
                    else:
                        
                        t['@'] -= (v-t[k])
                        t[k] += (v-t[k])
    
    return no
 
no = f(s,t,no)
 
if no:
    
    print('No')
 
else:
    
    no = f(t,s,no)
 
    if no:
        
        print('No')
    
    else:
    
        print('Yes')

 

그리고 두번째로 놓친점은... s에서 k,v를 순회할때 k가 @일수도 있다는 점이다..

 

@는 비교 대상이 아니다.. 그래서 for문에서 continue로 넘어가주자

 

from collections import Counter
 
s = Counter(input())
t = Counter(input())
 
no = False
 
replace_list = ['a','t','c','o','d','e','r']
 
def f(s,t,no):
 
    for k,v in s.items():
        
        if k == '@':
            
            continue
        
        if t.get(k,0) == 0:
            
            if k not in replace_list:
                
                no = True
                break
            
            if t.get('@',0) < v:
                
                no = True
                break
            
            else:
                
                t['@'] -= v
                t[k] = v
        
        else:
            
            
            if t[k] < v:
                
                if t.get('@',0) == 0 or k not in replace_list:
                    
                    no = True
                    break
                
                else:
                    
                    if t['@'] < (v-t[k]):
                        
                        no = True
                        break
                    
                    else:
                        
                        t['@'] -= (v-t[k])
                        t[k] += (v-t[k])
    
    return no
 
no = f(s,t,no)
 
if no:
    
    print('No')
 
else:
    
    no = f(t,s,no)
 
    if no:
        
        print('No')
    
    else:
    
        print('Yes')

 

근데 복기해보니까 코드가 좀 지저분하다...

 

depth를 줄일수 있을것 같은데

 

from collections import Counter
 
s = Counter(input())
t = Counter(input())
 
no = False
 
replace_list = ['a','t','c','o','d','e','r']
 
def f(s,t,no):
 
    for k,v in s.items():
        
        if k == '@':
            
            continue
        
        if t.get(k,0) == 0:
            
            if t.get('@',0) < v or k not in replace_list:
                
                no = True
                break
            
            else:
                
                t['@'] -= v
                t[k] = v
        
        else:
            
            
            if t[k] < v:
                
                    
                if t['@'] < (v-t[k]) or k not in replace_list:
 
                    no = True
                    break
 
                else:
 
                    t['@'] -= (v-t[k])
                    t[k] += (v-t[k])
    
    return no
 
no = f(s,t,no)
 
if no:
    
    print('No')
 
else:
    
    no = f(t,s,no)
 
    if no:
        
        print('No')
    
    else:
    
        print('Yes')