def bubble():
for i in range(N-1):
if S[i]>S[i+1]:
S[i],S[i+1] = S[i+1],S[i]
return
return True
def ABC():
for i in range(K):
if bubble():
return -1
return "".join(S)
N,K = map(int,input().split())
S = ["C"]*(N//3)+["B"]*((N-N//3)//2)+["A"]*(N-N//3-(N-N//3)//2)
print(ABC())아이디어를 떠올리기 약간 어려웠던 문제.
버블 소트에 관한 문제를 풀었던 것이 아이디어를 떠올리는데 도움을 주었다.
알고리즘을 설명하면,
일단 순서쌍의 최대 갯수는 A,B,C가 N/3씩 순서대로 나열될 때이다. 예를 들어 N=6인 경우 순서쌍이 최대로 존재하는 문자열은 AABBCC일 때이다. 따라서 이때를 기준으로 잡고, 내림차순으로 배열한다. (즉, 초기 문자열은 CCBBAA)
그리고 순서쌍의 개수는 버블 소트를 한번 실행할 때마다 1씩 커진다. 위의 CCBBAA에서 CBCBAA로 바꾸면 순서쌍의 개수는 0에서 1이 된다. 따라서 순서쌍의 개수가 K가 될 때까지 버블 소트를 실행해주면 정답 문자열이 나온다.
만약 버블소트를 할 수 없으면 -1을 출력한다.
다른 풀이를 보니 DP로 푼 풀이가 많아보였다. 하지만 내 풀이가 시간적인 측면에서든 코드길이 측면에서든 더 나은 풀이라고 생각한다. (여담으로 이 풀이는 숏코딩 순위 3위와 파이썬 기준 성능 1위를 기록했다)
