[연결리스트] 원소의 삭제와 추가

이번에는 과제로 나왔던 연결리스트 문제를 풀어보려고 한다.

문제는 다음과 같다.

 

영희는 민수에게 일련의 숫자를 불러달라는 부탁을 했다.

하지만 민수는 영희를 괴롭히고 싶어 순순히 숫자를 불러주지 않고

N개의 3가지 명령을 통해 일련의 숫자를 알 수 있게 하려고 한다.

민수가 사용할 세 가지 작업은 아래와 같다.

 

insert a b : a번위치에 b을 삽입한다.

delete a : a번째 위치의 숫자를 제거한다.

show : 현재 구성되어있는 숫자들을 보여준다.

 

영희는 할 일이 많아서 민수의 괴롭힘을 받아줄 수 가없다.

영희를 도와줄 프로그램을 작성하자.

 

입력

첫 번째 줄에 명령의 개수 n(1≤n≤30)이 주어지고, 2번째 줄부터 n개의 줄에 민수의 명령 이 입력으로 주어진다.

insert 명령의 경우 insert a b, delete 명령의 경우 delete a, show 명령의 경우 show 형태로 주어진다.

a는 100을 넘지 않는 자연수이며, b는 100,000을 초과하지 않는 자연수 이다.

출력 show 명령이 입력 될 때마다 숫자 현황을 보여주고, n개의 명령 수행 후 최종 형태를 출력 한다.

 

주의사항

show명령 수행시 숫자들은 띄어쓰기로 구분되어 출력한다.

ex) 2 3 4 5

각 명령을 출력 후 줄바꿈을 수행한다.

수업시간에 배운 연결리스트를 직접 구현하여 코드를 작성한다.

STL이나 기타 다른 방법을 사용하면 점수는 없다.

insert의 경우 삽입하는 위치가 현재 리스트의 마지막 위치 보다 초과하는 경우는 없다.

delete의 경우 삭제하는 위치가 현재 리스트의 범위를 초과하는 경우는 없다.

원소의 위치는 첫 번째 원소부터 1, 두 번째 원소는 2 ... 로 주어진다.

 

[예시1]

입력

6

insert 1 5

show

insert 2 3

insert 3 4

show

insert 2 1

 

출력

5

5 3 4

5 1 3 4 // (최종 출력)

 

HINT : 2번자리에 1이 삽입되면서 뒤의 숫자들이 한자리씩 밀려난다.

 

[예시2]

입력

6

insert 1 1

insert 2 2

insert 3 3

show

delete 2

show

출력 1 2 3

1 3 //  (최종 출력)

HINT : 2번위치 삭제로 뒤의 숫자들이 앞으로 이동한다.

 

문제가 매우 길다.

vector를 이용해서 풀었다면 매우 쉬운 문제였겠지만, STL이나 다른 방법을 사용하면 점수를 주지 않으므로 연결 리스트로 풀어보도록 하자.

 

해설은 이쪽으로

--> https://onutoa111.tistory.com/20