알고리즘 문제 풀이

[LeetCode] 984. String Without AAA or BBB

_OB1N 2021. 5. 26. 11:42

출처: https://leetcode.com/problems/string-without-aaa-or-bbb/

 

String Without AAA or BBB - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

문제

두 정수 ab가 주어지면, 다음 규칙에 따라 어떤 문자열 s를 반환하라:

  • sa + b의 길이를 갖고, 정확히 문자 'a'a개, 문자 'b'b개로 구성되어야 한다.
  • 하위 문자열 aaas에 존재하면 안 된다. 그리고
  • 하위 문자열 bbbs에 존재하면 안 된다.

 

예제

Input: a = 1, b = 2
Output: "abb"

Explanation: "abb", "bab" and "bba" are all correct answers.
Input: a = 4, b = 1
Output: "aabaa"

 

풀이

ab를 다음 세 개의 경우로 나누고 각 케이스에서 어떤 접근 방식으로 주어진 조건에 만족하는 문자열을 만들 수 있는지 생각해보자.

  • a > b
  • a < b
  • a == b

 

a == b의 케이스부터 살펴보면, 단순히 ab를 교차하는 방식으로 조건에 만족하는 문자열을 만들 수 있다. 예를 들어, abababa... 혹은 aabbaabb... 와 같이 동일한 개수의 a, b를 소모하는 방식으로 말이다.

 

a > ba < b의 경우는 어떠할까. Greedy하게 접근하면 a == b 케이스로 바꿀 수 있지 않을까 라는 생각이 든다. 아래의 예를 보자.

a = 5, b = 3 라면

1) a 두개, b 한개 => ans = aab
    - 남은 a = 3, b = 2

2) a 두개, b 한개 => ans = aabaab
    - 남은 a = 1, b = 1

3) a 한개, b 한개 => ans = aabaab OR ans = aabaabba

 

위의 예제에서 보는 것처럼 ab보다 많기 때문에 ab보다 더 많이 소모하도록 하여 ab를 점점 맞춰가는 것이다. 그렇게 하면 결국 a == b가 되어 단순히 교차하는 방식으로 문제를 풀 수 있기 때문이다.

 

다음의 코드는 위 내용을 구현한 코드이다.

let s = ''
while (a > 0 || b > 0) {
    const write_a = a >= b ? true : false;

    if (s.length >= 2 && s[s.length-1] == s[s.length-2]) {
        if (s.[s.length-1] == 'a') {
            write_a = false;
        } else {
            write_a = true;
        }
    }

    if (write_a) { s += 'a'; a -= 1; }
    else { s += 'b'; b -= 1; }
}

코드를 살펴보면, write_a는 핵심은 현재 단계에서 a를 작성할지 b를 작성할지 판단하는 변수이다. 3줄에서 write_a를 초기화하는데, 기본적으로 ab 중 더 큰 값의 문자를 먼저 소비하게 할 것이므로, a가 더 크다면 true를 그렇지 않다면 false로 초기화한다.

 

5 ~ 11줄의 if구문이 연속해서 3번의 같은 문자가 나오는 것을 방지하도록 하는 부분이다. 마지막 두 개의 문자를 보고 같은 문자일 경우, Greedy하게 선택했던 write_a를 무시하고 마지막 문자와 반대되는 문자를 추가하도록 write_a를 바꿔준다.

 

13 ~ 14줄은 write_a에 따라 문자를 추가하도록 하는 코드이다.

 

Github: 984.js

 

opwe37/Algorithm-Study

Contribute to opwe37/Algorithm-Study development by creating an account on GitHub.

github.com