< 문제 >
< 입출력 >
< 풀이 >
1. 첫번째 시도
| 글자 수 | 가능한 B의 최대 개수 | 가능한 C의 최대 개수 |
| 1 | 1 | 1 |
| 2 | 1 | 1 |
| 3 | 2 | 1 |
| 4 | 2 | 2 |
| 5 | 3 | 2 |
| 6 | 3 | 2 |
| 7 | 4 | 3 |
| 8 | 4 | 3 |
글자 수와 관련하여, B와 C의 최대 개수보다 크면 -1을 리턴하려 했으나, 만약 글자 수가 7개이고, B가 4개, C가 3개이면 최대 개수 조건은 만족하지만, B_B와 C_ _C 조건을 맞출 수 없으므로 다른 조건을 생각해봐야 한다.
2. 두번째 시도
위의 조건을 맞출 수 없는 경우를 생각해보니, B와 C의 최대 개수가 같이 변하는 6k + 1 (k는 정수)일 때, 최대 개수가 B와 C가 같은 경우이다. 또한, C가 2개 이상일 때, A는 C-1개 이상 있어야 한다.
3. 세번째 시도
미리 result 배열을 만들어 놓고, 생각하니 B와 C 위치를
놓을때 생각할게 너무 많아졌다.
import sys
input = sys.stdin.readline
arr = list(input().rstrip())
countA = arr.count('A')
countB = arr.count('B')
countC = arr.count('C')
length = len(arr)
checkedA = False
checkedB = False
checkedC = False
def task():
global checkedA
global checkedB
global checkedC
if (length+1)//2 < countB:
return -1
if (length+2)//3 < countC:
return -1
if length % 6 ==1 and (length+1)/2 == countB and (length+2)/3 == countC:
return -1
if countC > 1 and countC-1 > countA:
return -1
result = [0 for _ in range(length)]
if (length+1)/2 == countB:
checkedB = True
for j in range(0, length +1, 2):
result[j] = 'B'
if (length + 2) / 3 == countC:
if countC <= countB:
return -1
checkedC = True
for j in range(0, length + 1, 3):
result[j] = 'C'
if checkedB == False and checkedC==True:
checkedB = True
cnt = 0
i = 0
while cnt < countB:
if result[i] == 0:
result[i] = 'B'
i += 2
cnt += 1
else:
i += 1
if checkedC==False and checkedB==True:
checkedC = True
cnt = 0
i = 0
while cnt < countC:
if result[i] == 0:
result[i] = 'C'
i += 3
cnt += 1
else:
i += 1
if checkedA == False and checkedB == True and checkedC == True:
for k in range(length):
if result[k]==0:
result[k] = 'A'
ans = ''
for i in result:
ans += i
return ans
print(task())
4. 네번째 시도
B와 C개수에 따른 위치 관계는 없을까 고민해보았으나, 이것도 너무 복잡하다.
그냥 쉽게 A, B, C 뒤에 올 수 있는 것들을 생각해보자
A -> AA, AB, AC (단, AC의 경우 A 앞이 C인지 확인)
B -> BA, BC (단, BC의 경우 B앞이 C인지 확인)
C -> CA, CB
되는 것만 큐에 놓고, 돌렸을 때 없으면 -1을 출력해보자!
import sys
from collections import deque
input = sys.stdin.readline
arr = list(input().rstrip())
countA = arr.count('A')
countB = arr.count('B')
countC = arr.count('C')
length = len(arr)
nextA = ['A','B','C'] # A 다음에 올 수 있는 문자
nextB = ['A','C']
nextC = ['A','B']
result = []
q = deque()
def task():
q.append(('A',1,0,0,-100,1,'A')) # 마지막 문자와 A,B,C,모든 문자의 개수, 지금까지의 문장
q.append(('B',0,1,0,-100,1,'B')) # 마지막 문자와 A,B,C,모든 문자의 개수, 지금까지의 문장
q.append(('C',0,0,1,-100,1,'C')) # 마지막 문자와 A,B,C,모든 문자의 개수, 지금까지의 문장
while q:
x,A,B,C,lastC,total,real = q.popleft()
if A <= countA and B<=countB and C<=countC and total<= length:
if A == countA and B == countB and C == countC and total == length:
print(real)
exit()
if x == 'A':
for i in range(3):
if nextA[i] == 'A' and A<countA:
q.append(('A', A+1, B, C, lastC, total + 1, real + 'A'))
if nextA[i] == 'B' and B<countB:
q.append(('B', A, B+1, C, lastC, total + 1, real + 'B'))
if nextA[i] == 'C' and C<countC and lastC != total -1:
q.append(('C', A, B, C+1, total + 1, total+1, real + 'C'))
if x=='B':
for i in range(2):
if nextB[i] == 'A' and A<countA:
q.append(('A', A + 1, B, C, lastC, total + 1, real + 'A'))
if nextB[i] == 'C' and C<countC and lastC != total -1:
q.append(('C', A, B, C + 1, total + 1, total + 1, real + 'C'))
if x=='C':
for i in range(2):
if nextC[i] == 'A' and A<countA:
q.append(('A',A+1, B, C, lastC, total+1, real + 'A'))
if nextC[i] == 'B' and B<countB:
q.append(('B', A, B+1, C, lastC, total+1, real + 'B'))
print(-1)
task()
입출력은 잘나오나, 메모리 초과가 나온다.....
댓글