[코드트리] 배열에서 자리 바꾸기 C++

문제

https://www.codetree.ai/missions/8/problems/switch-position-in-array?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 쪼개기

주어진 것

길이 n짜리 배열(1~n까지의 수가 차례로 적혀 있음)

연산의 개수 q

위치를 바꿀 구간 a, b, c, d

 

목표

다음 연산을 구현하는 프로그램을 작성

• a b c d : 겹치지 않은 두 부분배열 <a, b>와 <c, d>의 위치를 서로 바꿉니다.

예를 들어, 배열 [3, 1, 4, 2, 5, 9, 6, 8, 7]에서 연산 "1 2 9 7"을 수행하면 배열은 [3, 9, 6, 8, 7, 5, 1, 4, 2]가 된다.

원래 배열에서 두 부분배열 [1, 4, 2]와 [9, 6, 8, 7]이 서로 위치를 바뀌었음

조건

이 배열에서 값이 a인 원소에서 시작해서 값이 b인 원소로 끝나는 부분배열을 <a, b>로 나타내기로 하였습니다. 예를 들어, 배열 [3, 1, 4, 2, 5, 9, 6, 8, 7]에서 <4, 6>은 부분배열 [4, 2, 5, 9, 6]을 의미

 

 

코드

어떤 노드를 어디에 넣어야 하는지 헷갈려서 해설을 보고 풀었다.

#include <iostream>
using namespace std;

const int MAX_N = 250000;
// 한 노드를 나타내는 구조체
struct Node {
    int id;
    Node *prev, *next;

    Node(int id) : id(id), prev(nullptr), next(nullptr) {}
};

Node *nodes[MAX_N] = {};

void Connect(Node *s, Node *e) {
    // s와 e를 이어줌
    if (nullptr != s) s->next = e;
    if (nullptr != e) e->prev = s;
}

void SwapRange(Node *a, Node *b, Node *c, Node *d){
    Node *after_ap=c->prev;
    Node *after_bn=d->next;

    Node *after_cp=a->prev;
    Node *after_dn=b->next;

    //b와 c가 붙어있는 경우
    if(b->next==c){
        after_ap=d;
        after_dn=a;
    }
    if(d->next==a){
        after_bn=c;
        after_cp=b;
    }

    Connect(after_ap, a);
    Connect(b, after_bn);
    Connect(after_cp, c);
    Connect(d, after_dn);
}

int main() {
    int n;
    cin >> n;
    // 노드 생성
    for(int i=1; i<=n; ++i){
        // 구조체 생성자로 Node 생성
        nodes[i]= new Node(i);
    }
    // 노드 연결
    for(int i=1; i<n; ++i){
        Connect(nodes[i], nodes[i+1]);
    }

    int q;
    cin >> q;
    // q번의 연산
    while(q--){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        // a, b, c, d 순서대로 배열에 들어가있다.
        SwapRange(nodes[a], nodes[b], nodes[c], nodes[d]);
    }


    // 1부터 거슬러올라가면서 head 찾기
    Node *cur = nodes[1];
    while(nullptr != cur->prev){
        cur=cur->prev;
    }
    // 최종 결과 출력
    while(nullptr != cur){
        cout << cur->id << " ";
        cur=cur->next;
    }
    return 0;
}