[TIS] stack - 짝 지어 제거하기 피드백

https://school.programmers.co.kr/learn/courses/30/lessons/12973

프로그래머스

 

stack 연습문제였는데

 

15분 정도 생각하고 15분정도 코드 구현했음 

 

의사코드작성

// 짝을 지어서 제거 
// 2개붙어있는 짝 문자열을 제거
// 제거이후에 다시붙임 이런식으로 모든 문자열을 제거한다면 
// 짝지어 제거하기 종료  

// 1. 짝지어 진걸 찾아서 해당문자열에서 제거하자 
// 이중반복문 쓰면 안돼 시간복잡도가 n 이 너무 커 100만
// 한번에 해야함

// 2. 짝지어졌다는 조건을 걸어서 
// 3. 조건에 부합하면 shift 로 제거하고
// 4. 부합하지 않으면 뒤로 보내자

// 그럼 한큐에 끝낼수 있음

// 아 이게 한번만 돌긴하는데 
// 배열 앞에서 빼는거라 O(1)
//앞에서 뺴고나서 전체 하나씩 움직여야해서 시간복잡도 영향 주네  n 이 너무 클경우

 

n = 백만이라 시간복잡도를 고려해야 하는 문제 

O(n2) 으로 풀면 시간 초과로 fail .. 

 

이중 반복문을 피할려고 

맨앞에서 부터 한글자씩 검사해서 짝지어진 조건이면 

검사한것과 바로 뒤문자 shift() 로 날리기

아니면 shift and push 로 회전시켜서 뒤로 보내기 

 

=> 결과 == fail .. shift 함수 자체가 

배열 전체 인덱스를 앞으로 한칸씩 땡겨야 함으로 

N 이 0(N)인데 이걸 모든 인덱스 마다 했으니 O(n2) .... 이걸 깜빡함..

 

sol ) 

shift 안쓰고 stack 배열에  push 함수로 차례대로 하나씩 넣으면서짝지어 지는 조건이면 pop() 아니면 계속 쌓아 ! 

 

결국 남아있다면 짝이 안지어졌다는것 !

 

code !