[Leetcode]984. String Without AAA or BBB

문제 요약

• 알고리즘 분류:  그리디, 정렬
• 난이도: Medium
• 문제내용:
  • .두 정수 a와 b가 주어질 때, 다음 조건을 만족하는 문자열 s를 반환하세요:
    • s의 길이는 a + b이고, 정확히 a개의 'a' 문자와 정확히 b개의 'b' 문자를 포함합니다.
    • 부분 문자열 'aaa'는 s에 나타나지 않습니다.
    • 부분 문자열 'bbb'는 s에 나타나지 않습니다.
• 사이트 주소:https://leetcode.com/problems/string-without-aaa-or-bbb/description/

문제풀이

 이번문제는 완전탐색아닌 그리디로 최적의 해로 시간복잡도가 최소화를 할 후 있다.그리디 관련 내용은 아래글로 참고 하면된다.

https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

문제 접근 방법

 그리디문제는 구현보다 아이디어가 요구하는 문제이다. 그래서 어떻게 접근 하면 좋을지 보면 된다

이 문제의 핵심은 'aaa'나 'bbb'와 같은 동일한 문자가 3개 연속으로 나오지 않도록 'a'와 'b'를 배치하는 것이다.

직관적인 방법을 생각해 보면:

1. 'a'와 'b'를 최대한 번갈아가며 배치한다
2. 개수가 차이 날 경우, 많은 문자가 연속으로 2개까지만 나오도록 배치한다

이런 아이디어를 바탕으로 다음과 같은 패턴을 사용할 수 있다.

• a > b일 때: "aab" 패턴 사용
• b > a일 때: "bba" 패턴 사용
• a = b일 때: "ab" 패턴 사용

위와 같은 내용으로 아래와 같이 구현 하면된다.

 

• 메인 로직: a와 b 모두 0보다 클 때까지 아래의 패턴을 반복 적용합니다.
  • a > b일 때: "aab" 패턴을 추가하고 a를 2 감소, b를 1 감소시킵니다.
  • b > a일 때: "bba" 패턴을 추가하고 a를 1 감소, b를 2 감소시킵니다.
  • a = b일 때: "ab" 패턴을 추가하고 a와 b를 각각 1씩 감소시킵니다.
• 남은 문자 처리: 위 과정이 끝난 후, a나 b 중 어느 하나가 0이 되었을 때, 남은 문자를 처리합니다.
  • 남은 a가 있으면 처리: a는 최대 2개만 남을 수 있습니다. (만약 3개 이상 남았다면, 위 루프에서 "aab" 패턴으로 처리되었을 것입니다.)
  • 남은 b가 있으면 처리: b 역시 최대 2개만 남을 수 있습니다.

예제

 위 설명으로 이해가 안 될수 있어서 아래와 같은 예제를 한번 보자

a = 4 , b = 2 일때

a > b이므로 "aab" 패턴 추가: s = "aab", a = 2, b = 1
a > b이므로 다시 "aab" 패턴을 추가하려 하지만, b = 1이므로 한 번만 추가할 수 있습니다.
루프를 빠져나온 후, a = 0, b = 0이 됩니다.
결과: s = "aab"

 

a = 5 , b = 3 일때

a > b이므로 "aab" 패턴 추가: s = "aab", a = 3, b = 2
a > b이므로 다시 "aab" 패턴 추가: s = "aabaab", a = 1, b = 1
a = b이므로 "ab" 패턴 추가: s = "aabaabab", a = 0, b = 0
결과: s = "aabaabab"

마무리

 위와 같이 구현 했을때 시간 복잡도는 a, b  반복에서 적어도 하나의 문자를 처리하므로 전체 반복 횟수는 O(a + b)이다.

이 문제는 문자열 패턴을 적절히 활용해 제약 조건을 만족시키는 좋은 예이다.. 'aaa'와 'bbb'를 피하기 위해 'a'와 'b'의 상대적인 개수에 따라 다른 패턴을 적용하는 그리디 접근법이 효과적이다.

 

Code

Python

class Solution:
    def strWithout3a3b(self, a: int, b: int) -> str:
        s = ""
        # a와 b 모두 0보다 클 때까지 반복
        while a > 0 and b > 0:
            # a가 b보다 많으면 "aab" 패턴 추가
            if a > b:
                s += "aab"
                a -= 2
                b -= 1
            # b가 a보다 많으면 "bba" 패턴 추가
            elif a < b:
                s += "bba"
                a -= 1
                b -= 2
            # a와 b의 개수가 같으면 "ab" 패턴 추가
            elif a == b:
                s += "ab"
                a -= 1
                b -= 1
        # 남은 a가 있으면 처리
        # a가 최대 2개만 남을 수 있음 (더 많았다면 위 루프에서 처리됨)
        if a > 0:
            s += "a" * a

        # 남은 b가 있으면 처리
        #  b가 최대 2개만 남을 수 있음 (더 많았다면 위 루프에서 처리됨)
        if b > 0:
            s += "b" * b

        return s

Java

class Solution {
    public String strWithout3a3b(int a, int b) {
        StringBuilder s = new StringBuilder();

        // a와 b 모두 0보다 클 때까지 반복
        while (a > 0 && b > 0) {
            // a가 b보다 많으면 "aab" 패턴 추가
            if (a > b) {
                s.append("aab");
                a -= 2;
                b -= 1;
            }
            // b가 a보다 많으면 "bba" 패턴 추가
            else if (a < b) {
                s.append("bba");
                a -= 1;
                b -= 2;
            }
            // a와 b의 개수가 같으면 "ab" 패턴 추가
            else if (a == b) {
                s.append("ab");
                a -= 1;
                b -= 1;
            }
        }

        // 남은 a가 있으면 처리
        // a가 최대 2개만 남을 수 있음 (더 많았다면 위 루프에서 처리됨)
        if (a > 0) {
            s.append("a".repeat(a));
        }

        // 남은 b가 있으면 처리
        // b가 최대 2개만 남을 수 있음 (더 많았다면 위 루프에서 처리됨)
        if (b > 0) {
            s.append("b".repeat(b));
        }
        
        return s.toString();
    }
}

Javascript

/**
 * @param {number} a
 * @param {number} b
 * @return {string}
 */
var strWithout3a3b = function(a, b) {
    let s = "";

    // a와 b 모두 0보다 클 때까지 반복
    while(a > 0 && b > 0) {
        // a가 b보다 많으면 "aab" 패턴 추가
        if(a > b){
            s += "aab";
            a -= 2;
            b -= 1;
        }
        // b가 a보다 많으면 "bba" 패턴 추가
        else if(a < b){
            s += "bba";
            a -= 1;
            b -= 2;
        }
        // a와 b의 개수가 같으면 "ab" 패턴 추가
        else if(a == b){
            s += "ab"
            a -= 1;
            b -= 1;
        }
    }

    // 남은 a가 있으면 처리
    // a가 최대 2개만 남을 수 있음 (더 많았다면 위 루프에서 처리됨)
    if(a > 0){
        s += "a".repeat(a);
    }

    // 남은 b가 있으면 처리
    // b가 최대 2개만 남을 수 있음 (더 많았다면 위 루프에서 처리됨)
    if( b > 0){
        s += "b".repeat(b);
    }

    return s;
};