스택1 프로그래머스 - 짝지어 제거하기 문제 이해 입력값으로 들어온 문자열 중 인접한 두 글자씩 짝지어 제거하는 문제 해당 문제를 봤을 때 그냥 계속 포문으로 반복 검사한다면 O(n^2)이 나올 수 있기 때문에 주의해야 한다. 따라서 이 문제를 더 효율적으로 풀기 위해서는 다른 방법을 생각해볼 필요가 있는데 스택을 이용하면 쉽고 빠르게 해결할 수 있다. for문으로 문자열을 이터레이션하며 스택의 top과 비교하며 다음과 같은 로직을 수행한다. 같을 경우 : 스택에 pop() 다를 경우 : 스택에 push() -> 파이썬 list에서는 append()를 이용 다음과 같이 구현할 경우 문자열 길이만큼 이터레이션 하기 때문에 O(n)으로 풀이할 수 있으며 해당 로직이 끝난 후 스택에 데이터가 남아있는지를 체크해 1, 0을 알맞게 넣어주면 된다. 해.. 2021. 9. 11. 이전 1 다음 반응형
