고비를 이겨내고 의자에 앉았다!
알고리즘 문제 링크
https://programmers.co.kr/learn/courses/30/lessons/12973
문제
짝지어 제거하기
문제 설명
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다.
먼저 문자열에서 같은 알파벳이 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을 반환합니다.해결코드
function solution(s)
{
// 1번 풀이 - 정확성 통과, 효율성 통과 X
// let strArr = [];
// for(let i=0; i< s.length;i++){
// if(strArr[0] === s[i]){
// strArr.shift();
// }else{
// strArr.unshift(s[i]);
// }
// }
// return strArr.length === 0 ? 1 : 0;
// 2번 풀이 - 정확성, 효율성 모두 통과
let strArr = [];
for(let i=0; i< s.length;i++){
if(strArr[strArr.length - 1] === s[i]){
strArr.pop();
}else{
strArr.push(s[i]);
}
}
return strArr.length === 0 ? 1 : 0;
}
추가설명
스택 을 활용해서 문제 해결
1번 풀이)
shift, unshift를 이용해서 스택을 구현
shift, unshift는 배열에서 앞으로 값을 추가, 맨 앞의 값을 제거하는 함수이다.
위 함수들은 앞의 값들을 추가/제거한 후에 뒤의 값들의 위치를 모두 앞으로 옮겨주는 작업을 진행하므로 속도가 느려서 효율성에서 탈락
2번 풀이) 예시를 이용한 스택 설명
push, pop을 이용해서 스택을 구현
push, pop은 배열에서 뒤로 값을 추가, 맨 뒤 값을 제거하는 함수이다.
위 함수들은 리스트에 추가하는 작업만 진행되면 끝이므로, 효율성에서도 빠름을 볼 수 있다.
잡담
이번 알고리즘은 스택을 활용하는 문제로써 아주 간단한 문제였지만, 효율성 검사에서 한 번 태클이 걸렸던 문제이다.
스택을 push / pop으로 구현하면 for loop에서 매번 스택의 길이를 구해야하는 로직이 존재하게 된다.
(맨 마지막 배열의 값을 찾아내기 위해서)
근데 스택의 길이를 구하는 로직을 아끼기 위해서, shift / unshift 으로 구현을 시도해봤다.
(앞에부터 추가/제거하기 때문에 길이를 구할 필요가 없이 index=0 으로 접근할 수 있다)
결과는 처참한 패배.. shift / unshift가 앞에부터 추가 후에 뒤에 있는 값들을 앞으로 옮겨온다는 생각을 못했었다.
역시 어떤 함수던 가져다 쓰기전에 내부 동작방식을 이해하고 써야한다는 교훈을 얻은 알고리즘이였다...
