[백준] 12970 - AB (Java)

문제 파악

https://www.acmicpc.net/problem/12970

풀이

문제가 꽤나 간단해보인다만,, 완전탐색(재귀)로 풀면 시간초과가 발생한다. O(N^2)

잘 들여다보면 규칙을 찾을 수 있다.
A를 기준으로 뒤에 있는 B의 개수만 신경쓰면 된다. ex) AABB = [2, 2, -, -] = 4
이 규칙을 활용해 정답 문자열을 만들어 보았다.

모든 자리수를 B로 채우고, 0부터 N-1 번째 자리수를 돌며 k를 업데이트하는 방향으로 구현하면 좀 더 직관적이다.

좀 더 쉽게 이해하기 위해 n = 10, k = 20이라고 가정하여 아래 과정을 만족하고자 했다.

i [0,n) 순환 인덱스	pairCount i번째 자리수가 B->A로 바뀔때 만족하는 추가 순서쌍 수	k 남은 순서쌍 수	targetIdx	aCount	s[i]
0	9	20 (20 + 0)		0	[B,B,B,B,B,B,B,B,B,B]
	9	11 (20 - 9)		1	[A,B,B,B,B,B,B,B,B,B]
1	8	12 (11 + 1)		1	[A,B,B,B,B,B,B,B,B,B]
	8	4 (12 - 8)		2	[A,A,B,B,B,B,B,B,B,B]
2	7	6 (4 + 2)	pairCount > k targetIdx 계산 ⬇️	2	[A,A,B,B,B,B,B,B,B,B]
	-	0	3		[A,A,B,A,B,B,B,B,B,B]

[A,A,B,A,B,B,B,B,B,B]를 보면 A를 기준으로 뒤의 B 개수가 총 7, 7, 6 = 20으로 정답을 만족한다. 

가장 핵심이 되는 부분은 k가 pairCount보다 클 경우,
pairCount = k인 인덱스 위치(targetIdx)를 찾아주어야 한다는 것이다.

만일 모든 반복문을 정상 수행했다면 k가 0일 것이므로 바꿔준 s[i]를 출력해주도록 하고,
그렇지 않을 경우에는 조건을 만족하는 문자열이 없는 것이므로 -1을 출력해주면 된다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        char[] s = new char[n];
        Arrays.fill(s, 'B');

        int aCount = 0;
        for (int i = 0; i < n && k > 0; i++) {
            k += aCount;
            int pairCount = n - i - 1;
            if (pairCount <= k) {
                k -= pairCount;
                aCount++;
                s[i] = 'A';
            } else {
                int idx = n - k - 1;
                if (idx >= i && idx < n) {
                    s[idx] = 'A';
                    k = 0;
                }
            }
        }
        if (k != 0) {
            System.out.println(-1);
        } else {
            System.out.println(new String(s));
        }
    }
}