✅ list

문제

링크

풀이

1. 문제 접근

'<' : 왼쪽으로 커서 이동
'>' : 오른쪽으로 커서 이동
'-' : 문자 제거
이외 문자 : 문자 입력

2. 자료구조 선택과 그 이유

지금 떠오르는 자료구조는 queue, stack, list 정도가 있다.
근데 queue, stack은 커서를 왼쪽으로 이동할때마다 이미 입력한 문자들을 빼서 다른 곳에 저장을 해두고 이동이 끝나면 다시 넣어줘야 하는 번거로움이 있다.
문자열의 최대길이가 1,000,000로 굉장히 기므로 시간 제한의 가능성이 있다.

queue, stack 보다 삽입 및 삭제가 자유로운 list가 더 유리할 것 같다.

3. 문제 해결 로직 (풀이법)

간단히 '<' 나 '>' 가 나오면 iterator을 이동시켜주고 '-' 가 나오면 erase로 삭제시켜주면된다.
이외 문자들은 insert로 추가

의사코드

cin >> T
while(T--){
	cin >> str
    list<char> ans
    
    list<char>::iterator cur = ans.end() // 커서의 초기 위치
    
    for(i : 0 ~ str.length - 1){
    	if(str[i] == '<'){
        	if(cur == ans.begin()) continue // 커서가 맨 앞에 위치할 경우에는 왼쪽으로 이동 불가능
            cur--;
        }
    	else if(str[i] == '>'){
        	if(cur == ans.end()) continue // 커서가 맨 뒤에 위치할 경우에는 왼쪽으로 이동 불가능
            cur++;
        }
        else if(str[i] == '-'){
        	if(cur == ans.begin()) continue // 커서가 맨 앞에 위치할 경우에는 왼쪽 문자 삭제 불가능
            cur--
            cur = ans.erase(cur)
        }
        else{
        	ans.insert(cur, str[i])
        }
    }

}

cout << ans

4. 시간 복잡도 분석

O(N)

5. 문제에서 중요한 부분

삽입, 삭제가 빈번하게 일어나는 문제이므로 list가 유리하다는 것을 아는것이 중요한 문제