키로커_스택_백준_5397

-문제-

 

-문제 접근-

 

문제에서 강산이가 입력한 키에 일반 문자, 백스페이스, <, >를 순서대로 처리하여 최종 문자열을 복원을 해야 되는 문제입니다. 

 

-문자열 접근-

이 문제를 처음 접근할 때 가장 단순한 방법인 일반 문자열을 떠올릴것 입니다.

하지만 일반 문자열을 사용하게 되면 중간에 문자를 삽입하거나 삭제하게 되면 모든 문자들을 이동시켜야 하므로 최악의경우 O(n)의 시간복잡도를 가질 수 있기 때문에 매우 비효율적입니다.

 

-두 개의 스택 사용-

문제에서 커서의 위치를 중점으로 두 스택으로 좌 우를 관리하면 커서의 이동은 스택 간의 이동으로 구현이 됩니다.

push와 pop의 연산은 O(1)이므로 총 시간 복잡도가 입력 키의 개수를 L이라면 O(L)을 가지게 되므로 효율적입니다.

 

• 문자열 총 시간 복잡도: 입력 키의 개수를 L이라고 가정하면, 각 키 입력마다 최악 O(L)의 연산이 일어날 수 있으므로, 최악의 경우 O(L²)의 시간 복잡도를 가짐.
• 스택 총 시간 복잡도: 입력 키의 개수를 L이라고 하면, 각 키 입력을 상수 시간에 처리할 수 있으므로 전체 연산은 O(L)

-전체 코드-

 

-코드 설명-

 

입력받는 T만큼 연산이 수행 되어야 하므로 while(T--)로 루프문을 생성합니다.

• 왼쪽 스택(left): 현재 커서의 왼쪽에 있는 문자들을 저장합니다.
• 오른쪽 스택(right): 현재 커서의 오른쪽에 있는 문자들을 저장합니다.

각 키 입력 시,

• 일반 문자: 왼쪽 스택에 push하여 추가 
• 백스페이스('-'): 왼쪽 스택에서 pop 
• 왼쪽 화살표('<'): 왼쪽 스택의 top을 꺼내 오른쪽 스택으로 이동
• 오른쪽 화살표('>'): 오른쪽 스택의 top을 꺼내 왼쪽 스택으로 이동 

for(char ch : key): 문자열 key에 포함된 각 문자를 차례대로 변수 ch에 할당하면서 반복합니다.

 

push_back: 컨테이너의 끝에 새 원소를 추가합니다.

 

 

스택은 선입 선출이므로 left 스택에서는 문자열로 받아서 reverse를 하여 원래 순서를 복원해야 합니다.

반면 right 스택은 pop을 해서 결과 문자열에 이어 붙여 넣으면 됩니다.

 

 

 

 

 

-END-