🤔 문제 분석
정말 야마가 돌아버릴 뻔한 그리디 문제이다.
길이가 N인 A와 B로 이루어진 문자열이 있다.
이때 i<j의 관계를 갖는 인덱스 i, j가 존재하고,
S[i] == 'A', S[j] == 'B' 라면 쌍을 이룬다고 한다.
이 쌍의 개수가 K개인 문자열을 찾아야 한다.
✅ 문제 풀이
우선 길이가 N인 A와 B로 이루어진 문자열을 생각해보자.
N이 최대 50까지 가능한데, 2^50개의 문자열이 존재할 것이기 때문에,
모든 문자열을 탐색해보는 것은 퍼포먼스 측면에서 비효율적이다.
그럼 일단은 적당한 N을 가진 문자열을 살펴보자.
N = 8 이라면,
AAAABBBB, ABBBBBBB, ABABABAB 등 굉장히 많은 문자열이 존재한다.
여기서 A=4개, B=4개인 예시를 다시 보자.
AAAABBBB는 쌍 16개를 이루고 있다.
A=4개 B=4개인 상황에서 이것보다 더 많은 쌍을 이룰 수 있을까?
아니다. A가 앞쪽으로 몰아지는 것이 무조건 쌍이 더 많다.
B 앞쪽에 A가 몇개 있느냐에 따라서 쌍이 결정되기 때문이다.
결국 A와 B의 개수가 정해지는 동시에 이룰 수 있는 쌍의 최대 개수도 결정된다.
그럼 다시 A=4개 B=4개인 예시로 돌아가보자.
AAAABBBB일 때, 쌍 16개가 가능하다.
AAABABBB일 때, 쌍 15개가 가능하다.
AAABBABB일 때, 쌍 14개가 가능하다.
AAABBBAB일 때, 쌍 13개가 가능하다.
AAABBBBA일 때, 쌍 12개가 가능하다.
...
BBBABAAA일 때, 쌍 1개가 가능하다.
BBBBAAAA일 때, 쌍 0개가 가능하다.
이렇게 A를 B 뒤로 조금씩 밀어낼 수록 가능한 쌍의 개수가 점진적으로 줄어든다.
그렇다면 2^50개를 모두 확인하는 접근 방식 대신, 위와 같은 규칙에 맞게 문제에 접근하면 될 듯하다.
A의 개수*B의 개수가 K개 이상이라면, 답을 찾을 가능성이 존재한다.
우선 입력을 받자.
val (N, K) = readLine().split(" ").map(String::toInt)이제 A와 B의 개수를 조정하며 쌍을 찾아나갈 것이다. for문을 작성한다.
for (a in 0..N) { // A개수
val b = N - i // B개수
...
}A와 B의 개수가 설정되면 최대값은 정해진다. 그게 K와 같은지 일단은 확인해보자.
...
if (a * b == K) { // 같다면 더이상 진행 안 해도 됨
print("A".repeat(a) + "B".repeat(b))
return
}
...아직 같진 않고 쌍의 최대값이 K 이상이라면 탐색을 시작한다.
A를 하나씩 오른쪽으로 보내볼 것이다.
다시 AAAABBBB의 예시로 돌아가보자.
A 한개를 우측으로 한칸씩 움직인다면,
쌍의 개수는 16, ... , 12 로 줄어든다.
즉 쌍의 개수의 범위는 12이상 16미만 이고,
이어서 다음 A를 우측으로 한칸씩 움직인다면,
쌍의 개수는 12, ..., 8 로 줄어든다.
이때 쌍의 범위는 8이상 12미만 이다.
...
if (a * b >= K) {
// 우측으로 보낼 A개수
for (k in 1..a) {
val minVal = (a - k) * j // 목표로 하는 k개만큼의 A를 최우측으로 보냈을 때의 쌍의 개수
val maxVal = (a - k + 1) * j // 목표로 하는 (k-1)개만큼의 A를 최우측으로 보냈을 때의 쌍의 개수
...
}
}
...위 패턴을 활용하여 범위를 바꿔보다가 이 범위 내에 K가 존재한다면,
해당 범위에서 A를 몇번 밀어내면 되는지 maxVal과 K를 통해 구하고,
그에 맞는 문자열을 출력해내면 된다.
...
if (a * b >= K) {
// 우측으로 보낼 A개수
for (k in 1..a) {
val minVal = (a - k) * j
val maxVal = (a - k + 1) * j
// 이 범위 내에 K가 존재한다면
if (K in minVal until maxVal) {
// 이때가 문자열을 찾는 시점이다.
val cnt = maxVal - K
...
}
}
}
...포착한 올바른 문자열을 출력해내면 정답이고,
못 찾고 for문을 벗어나면 -1을 출력한다.
...
if (a * b >= K) {
for (k in 1..a) {
val minVal = (a - k) * j
val maxVal = (a - k + 1) * j
if (K in minVal until maxVal) {
val cnt = maxVal - K
print(
"A".repeat(a - k) + // 안 밀리고 고정되어 있을 A들
"B".repeat(cnt) + // A가 좌측으로 밀어낸 B의 개수
"A" + // 우측으로 이동중인 A
"B".repeat(j - (k - 1) - cnt) + // 아직 안 밀린 B
"A".repeat(k - 1) // 이미 최우측에 대기중인 A들
)
return
}
}
}
...
print(-1)