[LeetCode] 984. String Without AAA or BBB
출처: 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
문제
두 정수 a
와 b
가 주어지면, 다음 규칙에 따라 어떤 문자열 s
를 반환하라:
s
는a + b
의 길이를 갖고, 정확히 문자'a'
가a
개, 문자'b'
가b
개로 구성되어야 한다.- 하위 문자열
aaa
는s
에 존재하면 안 된다. 그리고 - 하위 문자열
bbb
는s
에 존재하면 안 된다.
예제
Input: a = 1, b = 2
Output: "abb"
Explanation: "abb", "bab" and "bba" are all correct answers.
Input: a = 4, b = 1
Output: "aabaa"
풀이
a
와 b
를 다음 세 개의 경우로 나누고 각 케이스에서 어떤 접근 방식으로 주어진 조건에 만족하는 문자열을 만들 수 있는지 생각해보자.
a > b
a < b
a == b
a == b
의 케이스부터 살펴보면, 단순히 a
와 b
를 교차하는 방식으로 조건에 만족하는 문자열을 만들 수 있다. 예를 들어, abababa...
혹은 aabbaabb...
와 같이 동일한 개수의 a
, b
를 소모하는 방식으로 말이다.
a > b
와 a < 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
위의 예제에서 보는 것처럼 a
가 b
보다 많기 때문에 a
를 b
보다 더 많이 소모하도록 하여 a
와 b
를 점점 맞춰가는 것이다. 그렇게 하면 결국 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
를 초기화하는데, 기본적으로 a
와 b
중 더 큰 값의 문자를 먼저 소비하게 할 것이므로, 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