[백준 C, C++] 2161번 - 카드1(링크드 리스트)

2161번 - 카드1

 

2161번 문제

 

<코드 작성>

1. 구조체 Node 선언 (입력받은 데이터: data, 노드 사이를 연결: next)
2. 구조체 포인터 변수 선언(head, tail, cur, newNode)
3. 동적 할당을 통해 노드 생성
4. 노드에 데이터를 저장 (첫 번째 담긴 데이터일 경우 다음 연결은 NULL)
5. if-else문을 사용하여 head가 NULL일 경우에는 newNode를 head에 저장하고, 아닐 경우 tail의 next노드에 newNode를 저장
6. 주어진 데이터를 노드에 저장하고 모두 연결이 끝났다면 문제의 조건에 맞게 코드를 생성(while문 참고)

 

[C언어]

#include <stdio.h>
#include <stdlib.h>

typedef struct _node {
	int data;
	struct _node* next;
} Node;

int main() {
	int N;
	scanf("%d", &N);

	Node* head = NULL;
	Node* tail = NULL;
	Node* cur = NULL;
	Node* newNode = NULL;

	for (int i = 1; i <= N; i++) {
		newNode = (Node*)malloc(sizeof(Node));
		newNode->data = i;
		newNode->next = NULL;

		if (head == NULL) head = newNode;
		else tail->next = newNode;

		tail = newNode;
	}

	if (head == NULL) return 0;
	else {
		cur = head;
		printf("%d ", cur->data);

		while (cur->next != NULL) {
			tail->next = cur->next;
			cur = cur->next->next;
			tail = tail->next;
			printf("%d ", cur->data);

			if (tail->data == tail->next->data) break;
		}
	}
	return 0;
}

 

 

[C++]

#include <iostream>
using namespace std;

typedef struct _node {
	int data;
	struct _node* next;
} Node;

int main() {
	int N;
	cin >> N;

	Node* head = NULL;
	Node* tail = NULL;
	Node* cur = NULL;
	Node* newNode = NULL;
	
	for (int i = 1; i <= N; i++) {
		newNode = new Node[sizeof(Node)];
		newNode->data = i; 
		newNode->next = NULL;

		if (head == NULL) head = newNode;
		else tail->next = newNode;

		tail = newNode;
	}

	if (head == NULL) return 0;
	else {
		cur = head;
		cout << cur->data << " ";

		while (cur->next != NULL) {
			tail->next = cur->next;
			cur = cur->next->next;
			tail = tail->next;
			cout << cur->data << " ";

			if (tail->data == tail->next->data) break;
		}
	}
 
	delete[]newNode;
	return 0;
}

 

이 문제를 풀 때 가장 중요한 부분은 while문에 구현된 코드라고 생각합니다. 

한 장의 카드를 놓고, 그다음 카드를 맨 뒤로 보내는 과정만 차근차근 생각해서 구현한다면 쉽게 풀 수 있을 것 같습니다. 

while문의 탈출 조건 코드를 작성하기 전, 코드를 실행했을 때 tail의 데이터만 무한 반복되어 출력되었습니다. 그래서 while문의 탈출 조건으로 if문을 사용하여 tail노드와 tail의 다음 노드가 값이 같을 때 종료하도록 구현하였습니다. 

 

감사합니다!

2022.01.28