[SWEA/C++] 암호문3(1230번)

1. 문제 개요

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14zIwqAHwCFAYD&categoryId=AV14zIwqAHwCFAYD&categoryType=CODE&problemTitle=1230&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

※ 본 문제는 SW Expert 아카데미의 문제이므로 무단으로 복제 X

1-1. 설명

0 ~ 999999 사이 수를 나열해 만든 암호문이 있다. 암호문을 수정해야 할 일이 발생헀는데, 이 암호문은 특수 제작된 처리기로만 수정이 가능하다. 다음과 같이 3개의 기능을 제공한다

 

 - I x, y, s : 앞에서부터 x의 위치 바로 다음에 y개의 숫자를 삽입한다. s는 덧붙일 숫자들이다.

 - D x, y : 앞에서부터 x의 위치 바로 다음부터 y개의 숫자를 삭제한다

 - A y, s : 암호문의 맨 뒤에 y개의 숫자를 덧붙인다. s는 덧붙일 숫자들이다.

 

위의 규칙에 알맞게 작성된 명령어를 나열하여 만든 문자열이 주어졌을 때, 암호문을 수정하고 수정된 결과의 처음 10개 숫자를 출력하는 프로그램을 작성한다.

1-2. 제한 사항

 - 첫째 줄에는 원본 암호문의 길이인 N 주어짐.  N은 2000이상 4000이하의 정수

 - 두번째 줄은 원본 암호문 주어짐

 - 세번째 줄에는 명령어의 개수 M이 주어짐. M은 250이상 500이하의 정수

 - 네번째 줄에는 위와같은 명령어들이 주어짐

 - 총 10개의 테스트 케이스가 주어짐

---

2. 구현

2-1. 풀이

연결 리스트를 생성하여 원본 암호문을 저장하고, 주어진 명령어에 따라 연결리스트 삽입, 삭제 등 여러 기능을 구현하여 실행되게끔 하였다. 연결리스트를 직접 구현해 코드가 조금 길어졌다. 

2-2. 코드

#include<iostream>

using namespace std;
#define MAX_NODE 500000

void addNodeToTail(int data);
void init();
void insertNode(int x, int s);
void deleteNode(int x, int y);


struct Node { // 연결 리스트의 노드
	int data;
	Node* next;
};

Node node[MAX_NODE];
int nodeCnt;
Node* head;

Node* getNode(int data) { // 연결리스트 정적 할당
	node[nodeCnt].data = data;
	node[nodeCnt].next = nullptr;
	return &node[nodeCnt++];
}

int getList(int output[MAX_NODE]) // 지금까지 연결된 리스트 저장
{
	Node* prevNode = head->next;
	int count = 0;
	while (prevNode->next != nullptr) {
		output[count] = prevNode->data;
		prevNode = prevNode->next;
		count += 1;
	}
	output[count] = prevNode->data;
	count += 1;
	return count;
}

int output[MAX_NODE] = {0};

int main(int argc, char** argv)
{
	int test_case;
	int T = 10, N, M, pw;
    
	for(test_case = 1; test_case <= T; ++test_case)
	{
        cin >> N;
		init();
		for (int i = 0; i < N; i++) {
			cin >> pw;
			addNodeToTail(pw); // 암호문 연결리스트에 저장
		}
		cin >> M;
		char inputChar;
		for (int i = 0; i < M; i++) { // 명령어 개수만큼 반복
			cin >> inputChar;
			int x, y, s;
			if (inputChar == 'I') { // 삽입일 때 
				cin >> x >> y;
				for (int j = 0; j < y; j++) {
					cin >> s;
					insertNode(x + j, s);
				}
			}
			else if (inputChar == 'D') { // 삭제일 때
				cin >> x >> y;
				deleteNode(x, y);
			}
			
			else if (inputChar == 'A') { // 추가일 때
				cin >> y;
				for (int j = 0; j < y; j++) {
					cin >> s;
					addNodeToTail(s);
				}
			}
		}
		cout << "#" << test_case << " ";
		int count = getList(output);
		for (int i = 0; i < 10; i++) { // 한 케이스당 10개씩 출력
			cout << output[i] << " ";
		}
		cout << "\n";

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}


void init()
{
	head = new Node();
	head->next = nullptr;
}

void addNodeToTail(int data) // 연결리스트 끝부분에 노드 추가
{
	Node* node = getNode(data);
	Node* prevNode = head;
	while (prevNode->next != nullptr) {
		prevNode = prevNode->next;
	}
	node->next = prevNode->next;
	prevNode->next = node;

}

void insertNode(int x, int s) { // 노드 삽입
	Node* node = getNode(s);
	Node* prevNode = head;
	for (int i = 0; i < x; i++) {
		prevNode = prevNode->next;
	}
	node->next = prevNode->next;
	prevNode->next = node;
}

void deleteNode(int x, int y) { // 노드 삭제
	for (int i = 0; i < y; i++) {
		Node* prevNode = head;
		for (int j = 0; j < x; j++) {
			prevNode = prevNode->next;
		}
		prevNode->next = prevNode->next->next;
	}
}