프로그래머스 - 짝지어 제거하기

 

문제

 

풀이

풀고자 했던 의도는 입력받은 문자열을 배열로 변환한 뒤 해당 배열을 순회하면서 배열의 idx번째 값과 idx+1 값을 비교해서 같다면 splice(idx, 2)로 제거한 뒤 idx값을 0으로 초기화 하려고 했다.

하지만 예상치 못한 문제가 있었는데, 그것은 코드는 제대로 작동 할지라도 비교할 배열 인덱스를 0으로 초기화하는 덕에 최악의 경우 O(n^2)의 시간복잡도를 가지게 된다는 것이었다.

그로 인해 몇 가지의 테스트 케이스와 효율성테스트에서 모두 시간 초과가 난 모습

 

다른 풀이방법을 모색하던 도중 stack 방식으로 풀면 O(n)의 시간복잡도로 해결할 수 있다는 힌트를 얻어 다시 풀어보았다.

입력받은 문자열을 splitedString 배열로 변환하고, 새로운 빈 answer 배열에다가 하나씩 push하면서 splitedString배열의 요소와 answer배열의 마지막 요소와 비교하여 다르다면 계속 push, 같다면 answer배열의 마지막 요소를 pop 하는 stack 방식으로 구현했고 효율성 부분에서도 통과할 수 있었다.