짝지어 제거하기
문제 설명
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.
예를 들어, 문자열 S = baabaa 라면
b aa baa → bb aa → aa →
의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.
제한사항
- 문자열의 길이 : 1,000,000이하의 자연수
- 문자열은 모두 소문자로 이루어져 있습니다.
입출력 예
| s | result |
|---|---|
| baabaa | 1 |
| cdcd | 0 |
입출력 예 설명
- 입출력 예 #1
- 위의 예시와 같습니다.
- 입출력 예 #2
- 문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.
나의 풀이 (효율성 통과 X)
-
for 문을 돌려 str[i]와 str[i+1]이 같다면 str의 i부터 2개까지 삭제한다.
-
i를 -1로 돌린다. (if 문이 끝나면 i++가 되어 i=0 부터 다시 시작된다.)
-
str이 다 지워졌다면 1을 return 아니라면 0을 return 한다.
function solution(n) {
const str = s.split('');
for(let i=0; i<str.length; i++) {
if(str[i] === str[i+1]) {
str.splice(i, 2);
i=-1;
}
}
return str.length === 0 ? 1 : 0
}
}나의 풀이
-
빈 배열과 s를 배열로 만들어서 변수로 저장한다.
-
for 문을 돌려 stack의 마지막 원소와 sArray[i]가 같다면 stack의 마지막 원소를 지운다.
-
그게 아니라면 stack에 sArray[i]를 넣어준다.
-
맨 처음에는 stack가 무조건 빈 배열이기 때문에 sArray[i]를 추가하는 것이기 때문에 결국 sArray[i]와 sArray[i-1]을 비교하는 것이다. 이 말은 문자열 [i]와 [i-1] 즉 연속된 것을 비교한다는 뜻이다.
-
4번에서 설명한 이유 때문에 모든 문자가 지워지면 stack은 결국 처음과 같은 빈 배열이 되기 때문에 stack의 길이가 0이라면 1 아니라면 0을 return 한다.
function solution(s) {
const sArray = s.split('');
const stack = [];
for (let i = sArray.length - 1; i >= 0; i--)
if (sArray[i] === stack.at(-1)) stack.pop();
else stack.push(sArray[i]);
return stack.length === 0 ? 1 : 0;
}배운점
스택과 큐의 개념을 알았더라면 충분히 풀 수 있는 문제였다. 레벨 1까지는 알고리즘의 문제풀이 방식에 대해 그렇게 고민해보지 않았다면 레벨 2부터는 알고리즘 문제풀이 방식에 대해 먼저 공부하는 것이 좋겠다.
또한 stack.at(-1) 처럼 배열의 원소에 접근하는 메서드를 알았다. at메서드는 결국 아래와 같다.
const stack = [1,2,3,4,5];
stack[-1]; // undefiend
stack[stack.length - 1]; // 5
stack.at(-1); // 5느낀점
Lv2를 풀면서 문제를 풀었어도 점점 효율성 테스트에서 통과하지 못하게 된다. 반복문을 사용할 때 시간복잡도를 최대한 줄이고 필요없는 처리를 최소화 할 수 있는 코드를 구현하기 위해 노력해야겠다.
