[leetcode] 1172. Dinner Plate Stacks

문제 : https://leetcode.com/problems/dinner-plate-stacks/

---

let) capacity = 2

index	0	1	2	3
stack			4
	1		3	5

fullStack : 가득찬 스택 인덱스 (2)

blankFullStack : fullStack 사이사이의 index (0, 1, 3(3인덱스 스택이 가득찼다가 삭제된 경우))

stackMap : key - index, value - stack ({0, {1}}, {2, {4,3}}, {3, {5})

 

push

처음 push하는 경우는 0번 인덱스 stack에 push.

가득찬 스택들 중간에 빈 곳이 있는 경우(blankFullStack이 있는 경우) 빈 곳 중 가장 왼쪽에 넣어준다.

왼쪽부터 차례대로 스택들이 모두 차있는 경우 가득찬 스택 가장 큰 인덱스 + 1 위치에 push한다.

 

pop

stack들이 하나도 없는 경우 -1

stackMap이 있으면 가장 오른쪽 스택(stackMap의 가장 뒤에 있는 stack)을 pop.

후처리 : pop한 스택이 null인 경우 stackMap에서 삭제. fullStack에 포함되어 있었으면 거기서도 삭제. blankFullStack 갱신.

 

popAtStack

index에 stack이 빈 경우 -1

stackMap[index]가 있으면 해당 스택 pop.

후처리 : pop한 스택이 null인 경우 stackMap에서 삭제. fullStack에 포함되어 있었으면 거기서도 삭제. blankFullStack 갱신.

 

---

if(stackMap[index].empty()) // 없는 경우 생성된다.
    return -1;

popAtStack 함수를 처음에는 위와 같이 예외처리를 했었는데 예제를 돌려보면 런타임에러가 발생했었다.

출처 : http://www.cplusplus.com/reference/map/map/operator[]/

찾아보니 [] 오퍼레이션으로 찾으면 찾고자 할 때 요소가 없으면 defaul 값으로 생성해서 map에 넣어준다.

if(stackMap.find(index) == stackMap.end()) // find로 변경해야 한다.
    return -1;

그래서 찾고자만 하는 경우는 위와 같이 find 함수를 써야 한다.

---

blankFullStack 변수명 스마트하지는 않는 듯.

---

push 할 때, fullStack set을 항상 돌면서 빈 곳을 찾았는데 이렇게 코딩하니 TLE가 발생했다.

그래서 blankFullStack set을 추가해서 push할 곳을 바로 찾아갈 수 있게 수정했다.

그런데 set, map의 erase 함수가 key로 삭제시는 set, map의 크기라고 한다. 그래서 이 함수들이 실행되는 경우 빅오는 O(N)으로 측정하고 이 외에 push는 set의 가장 앞이므로 O(1) pop은 map의 가장 뒤이므로 O(1), popAtStack은 map.find를 호출하므로 O(logN)으로 측정했다.

요것도 TLE 걸릴 것 같았는데 안걸렸다.

토론글에 힙 사용한 경우도 있고 간단하고 좋은 소스가 있어 보이는데 보고 다시 풀어봐야겠다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1172.%20dinner-plate-stacks.cpp