[SWEA] 17938. 문자열 세 개

[SWEA] 17938. 문자열 세 개

 

문제 링크

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

 

문제 요약

LCS(Longest Common Subsequence) 값이 주어진 세 문자열 AAA, BBB, CCC를 생성하는 문제다.

 

문제 풀이

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // 테스트 케이스 수

        for (int t = 1; t <= T; t++) {
            int X = sc.nextInt(); // LCS(A, B)
            int Y = sc.nextInt(); // LCS(B, C)
            int Z = sc.nextInt(); // LCS(C, A)

            // A, B, C를 구성
            StringBuilder A = new StringBuilder();
            StringBuilder B = new StringBuilder();
            StringBuilder C = new StringBuilder();

            // A는 X개의 '1'로 구성
            for (int i = 0; i < X; i++) A.append('1');
            while (A.length() < Math.max(X, Y) + Z) A.append('0'); // 길이 맞추기

            // B는 Y개의 '1'을 포함하며 A와 일부 겹침
            for (int i = 0; i < Y; i++) B.append('1');
            while (B.length() < A.length()) B.append('0');

            // C는 Z개의 '1'을 포함하며 B와 일부 겹침
            for (int i = 0; i < Z; i++) C.append('1');
            while (C.length() < A.length()) C.append('0');

            // 출력
            System.out.printf("#%d %s %s %s\n", t, A, B, C);
        }

        sc.close();
    }
}

 

핵심 로직

문자열의 기본 구성

• AAA는 XXX개의 '1'로 구성
• BBB는 YYY개의 '1'로 구성
• CCC는 ZZZ개의 '1'로 구성

 

공통 부분 보장

• AAA, BBB, CCC는 동일한 길이로 맞추면서 공통되는 '1'의 부분을 조정하여 LCSLCSLCS를 만족한다.

 

길이 확장

• 필요 시 '0'으로 채워 길이를 확장하여 XXX, YYY, ZZZ가 동시에 만족되도록 설계한다.