[자료구조] 연결리스트의 활용(1) : 위치 변환

N (2 ≤ N ≤ 100) 개의 정수로 이루어진 수열 X를 “위치 바꿈 정보”에 의해 변 환한 최종 결과를 출력하는 프로그램을 작성하시오. 위치 바꿈 방식은 다음과 같다. 예를 들어, 10 개 정수의 수열 X와 위치 바꿈 정보가 다음과 같이 주어졌을 때,

◦ 위치 바꿈 정보: 3--> 8-->0-->9-->3

- 위치 바꿈 정보를 구성하는 수의 범위는 0~N-1이다.

- 주어지는 위치 바꿈 정보에서 처음과 마지막 위치는 항상 동일하고, 그 외에는 동일한 위치는 없다고 가정하라.

 

◦ 위 순서 바꿈 정보에 의해, 수열 X에서
3번 위치의 정수 ‘12’는 8번 위치로 이동,
8번 위치의 정수 ‘91’은 0번 위치로 이동,
0번 위치의 정수 ‘3’은 9번 위치로 이동,
9번 위치의 정수 ‘10'은 3번 위치로 이동시킨다..

 

◦ 위 변환 규칙에 의해 만들어지는 최종 수열은 다음과 같다.

위치 0 1 2 3 4 5 6 7 8 9

값 91 81 9 10 0 -9 36 33 12 3

 

변환된 수열은 한 줄에 출력하되, 줄의 맨 앞에 공백을 하나 출력한다.

 

10 ↦ 입력 수열의 길이 (N) 3 81 9 12 0 –9 36 33 91 10 ↦ 수열 X 5 ↦ 순서 바꿈 정보의 길이 3 8 0 9 3 ↦순서바꿈정보

□91 81 9 10 0 –9 36 33 12 3 ↦ 변환 수열

6 0 20 40 30 10 50 4 1 2 4 1

□0 10 20 30 40 50

알고리즘

10 ↦ 입력 수열의 길이 (N) 3 81 9 12 0 –9 36 33 91 10 ↦ 수열 X 5 ↦ 순서 바꿈 정보의 길이 3 8 0 9 3 ↦순서 바꿈 정보

□91 81 9 10 0 –9 36 33 12 3 ↦ 변환 수열

1. 저장할 데이터 값을 저장할 정수형 변수와 data 값을 불러와 저장할 노드의 위치를 저장할 구조체 포인터 next를 선언한다.

2. 입력 수열의 길이를 입력받고 입력 수열의 길이만큼 구조체를 동적 할당한다.

3. 수열 X를 동적 할당한 구조체에 순서대로 입력한다. 이때 구조체의 멤버인 pre_data값에 data를 저장한다.

data	현재 저장값
pre_data	이전 저장값

4. 순서 바꿈 정보의 길이와 순서 바꿈 정보를 입력받는다.(해당 배열은 동적 할당을 사용하지 않았다.)

5. 순서 바꿈 정보의 길이만큼, 순서 바꿈 정보 배열 값을 인자로 하여 값 변경 알고리즘을 사용한다.

(편의를 위해 로직에 따른 출력을 넣었다.)

구조체에 값을 저장할 변수를 두 개 만든 이유는 "위치를 바꿔야"하기 때문이다.

이후 코드를 보면 이해할 수 있는데, 현재 순서 바꿈 정보가 가리키는 노드의 값을 다음 순서 바꿈 정보가 가리키는 노드의 값으로 바꿔야 한다.

즉 현재 순서 바꿈 정보가 가리키는 노드의 next값을 다음 순서 바꿈 정보가 가리키는 노드의 위치로 변경한 후, 다음 순서 바꿈 정보가 가리키는 노드의 data 값에 현재 순서 바꿈 정보가 가리키는 노드의 pre_data값을 저장한다. 이때 pre_data가 없다면 2번째 이상의 반복에서 이미 변경된 값을 저장하게 되므로, 두 개의 data(변경 가능 데이터, 변경 불가능 데이터)를 저장할 변수가 필요하다.

6. 결과값을 출력한다.

정답 코드

#include  <stdio.h>
#include  <string.h>
#include  <stdlib.h>
struct list{
    int data;
    int pre_data;
    struct list *next;
};
int main(){
    int N,rev_arr[101],rev_cnt;
    scanf("%d",&N);
    struct list *system = NULL;
    system = (struct list*)malloc(sizeof(struct list)*N);
    for(int i=0;i<N;i++){
        scanf("%d",&system[i].data);
        system[i].pre_data = system[i].data;
    }
    scanf("%d",&rev_cnt);
    for(int j=0;j<rev_cnt;j++)scanf("%d",&rev_arr[j]);
    //3 8 0 9 3
    for(int j=0;j<rev_cnt-1;j++){
    	/*값 변경 알고리즘*/
        system[rev_arr[j]].next = &system[rev_arr[j+1]];
        printf("changing...\n");
        printf("%d -> %d\n",system[rev_arr[j]].next->data,system[rev_arr[j]].pre_data);
        system[rev_arr[j]].next->data = system[rev_arr[j]].pre_data;
    }
    for(int i=0;i<N;i++)printf("%d ",system[i].data);
}