ABC 301 복기.. C - AtCoder Cards (문자열 그리디 알고리즘)
1. 문제
C - AtCoder Cards
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
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')'경쟁 프로그래밍 > Atcoder' 카테고리의 다른 글
| ABC 324 - D번 복기, 순열 다루는 테크닉 - 두 문자열이 서로의 순열일려면? - (0) | 2023.10.15 |
|---|---|
| ABC 304 복기 - E good graph - union find 활용 (0) | 2023.06.04 |
| 그래프 연결요소 - union find로 찾아야하는 연결요소 문제 1 - (0) | 2023.03.14 |
| ABC 293 복기 E - Geometric Progression - 행렬곱 배우기 - (0) | 2023.03.12 |
| ABC 293 복기 - D Tying Rope - 그래프 연결요소, cycle 판단 - (0) | 2023.03.12 |
