c언어 23309번 철도 공사 (백준)

 

#include <stdio.h>

int main(void)
{
	int n, m, tmp1, tmp2, first=0, before=0, p=0;
	
	scanf("%d %d", &n, &m);
	//연결리스트를 위한 배열
	int prev[1000001]={};
	int next[1000001]={};
	
    //처음 값 (나중에 마지막값과 연결시켜주기 위해서 따로 저장함
	n--;
	scanf("%d", &first);
	before = first;
	
    //두번째부터 
	while(n--) {
		scanf("%d", &tmp1);
        //서로 연결
		prev[tmp1]=before; 
		next[before]=tmp1;
        
		before = tmp1;
	}
	
    //마지막값과 처음값 연결
	next[before] = first;
	prev[first] = before;
	
    //입력을 받기위한 배열
	char c[2] = {};
	
    //쿼리 처리
	while(m--) {
		scanf(" %c%c", &c[0], &c[1]);
		scanf("%d", &tmp1);
		if(c[0] == 'B') {
			scanf("%d", &tmp2);
			if(c[1] == 'N') { 
				p = next[tmp1]; //입력된 곳의 오른 쪽 역
				printf("%d\n", p); 
				prev[p] = tmp2; //오른쪽 역의 왼쪽을 새로운 역으로
				next[tmp1] = tmp2; //기존역의 오른쪽을 새로운 역으로
				prev[tmp2] = tmp1; //새로운 역의 왼쪽을 기존역으로
				next[tmp2] = p; //새로운 역의 오른쪽을 기존역의 오른쪽 역으로
			}
			else {
				p = prev[tmp1]; //입력된 곳의 왼쪽 역
				printf("%d\n", p);
				next[p] = tmp2; //왼쪽 역의 오른쪽을 새로운 역으로
				prev[tmp1] = tmp2; //기존역의 왼쪽을 새로운 역으로
				prev[tmp2] = p; //새로운 역의 왼쪽을 왼쪽역으로
				next[tmp2] = tmp1; //새로운 역의 오른쪽을 기존역으로
			}
		}
		else {
			if(c[1] == 'N') {
				p = next[tmp1]; //입력된 곳의 오른쪽 역
				printf("%d\n", p);
                
                //입력된 곳의 오른쪽역의 오른쪽 역과, 입력된 곳을 연결
				next[tmp1] = next[p]; 
				prev[next[p]] = tmp1; 
			}
			else {
				p = prev[tmp1];
				printf("%d\n", p);
                
                //입력된 곳의 왼쪽역의 왼쪽 역과, 입력된 곳을 연결
				prev[tmp1] = prev[p];
				next[prev[p]] = tmp1;
			}
		}
	}
}

 

풀이 : 연결 리스트

 

시간초과를 피하기 위해서 STL list가 아닌

배열을 이용한 연결리스트를 이용했습니다

 

특정 요소에 접근할 때

std::find()는 O(1)보다 더욱 오래 걸리나

배열을 이용하게 되면, 특정 원소에 대해서 O(1)로 접근할 수 있습니다.

 

https://www.acmicpc.net/problem/23309

23309번: 철도 공사