✅ list

문제

링크

풀이

1. 문제 접근

4개의 명령어 중에
이동 명령어 2개, 삽입 및 삭제 명령어 2개이다.
커서는 양방향으로 이동하고
삽입 및 삭제는 왼쪽에만 가능하다

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

배열의 인덱스에 따라 커서를 위치시키고 삽입, 삭제를 하면
배열의 특성상 삽입, 삭제 할 때마다 재배열을 해줘야 한다.
문자열의 길이는 100,000을 넘지 않지만 삽입을 할 수록 문자열은 길어지고 (명령어 최대 500,000번 가능)
그만큼 재배열하는데 시간이 많이 걸릴 것 같다.

따라서 삽입 및 삭제 시 재배열을 하지 않아도 되는 연결리스트를 통해 문제를 풀기로 했다.

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

명령어에 따른 로직을 수행한다.

의사코드

cin >> str >> N
list <- str // list에 str을 담는다
cur = list.end // 맨처음 커서의 위치는 문자열을 입력한 직후이므로 리스트의 마지막 위치

while(N){
	cin >> op
    if(op == L){
    	if(cur==list.begin)continue
        cur--
    }
    if(op == D){
    	if(cur==list.end)continue
        cur++
    }
    if(op == B){
    	if(cur==list.begin)continue
        cur--
        cur = list.erase(cur) 
    }
    if(op == P){
    	cin >> ch
        list.insert(cur, ch)
    }
}

cout << list

4. 시간 복잡도 분석

O(N)

5. 문제에서 중요한 부분

주어진 시간 제한(0.3초)이 작기 때문에 연결리스트를 사용할지 판단하는 것 자체가 중요한 문제이다.