[백준] 2841 외계인의 기타 연주 c++ 구현

 

목차

 

 

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

2841번: 외계인의 기타 연주

문제

 

문제 구현 방향

스택에 대해서 공부하는 겸 스택을 구현하고 약간 변형하여 문제를 풀어보았다. 

 

 

 

스택 구조 설명

List* ListInit():

스택의 초기화를 해준다.

 

bool ListisEmpty():

스택이 비어있으면 true를 반환해준다.

 

void ListPush(int data, int* fingercount):

기존 스택 형태에 fingercount라는 변수만 추가해준 형태이다.

스택에 값이 추가되면 fingerpoint가 1증가한다.

 

int ListPop(int *fingercount):

기존 스택 형태에 fingercount라는 변수만 추가해준 형태이다.

스택에 값이 삭제되면 fingerpoint가 1증가한다.

 

int Listpeek():

스택의 가장 머리에 있는 값을 참조해 준다.

 

 

 

 

 

스택 구현 시 주의할 점

스택은 비교적 간단하게 구현 할 수 있다.

데이터 추가 시: 머리에 추가를 한다.

데이터 삭제 시: 머리부터 삭제해 준다.

데이터 참조 시: 머리부터 참조해 준다.

예외처리: 머리가 NULL값인지에 따라 해주면 된다.

 

스택은 'HEAD'가 핵심이다.

 

 

 

 

문제 풀이

문제 이해가 정말 중요하다. 

9가 어떻게 나오는 지 설명하면 다음과 같다.

1 5 -> 1번 줄의 5번 프렛 눌러준다 = 1회

 

2 3 -> 2번 줄의 3번 프렛 눌러준다 = 2회

 

2 5 ->  2번 줄의 5번 프렛 눌러준다 =  3회

 

2 7 ->  2번 줄의 7번 프렛 눌러준다 =  4회

 

2 4 ->  2번 줄의 4번 프렛

  - 4보다 높은 프렛이 눌려 있기 때문에  7, 5번을 떼고 4번을 눌러준다 = 4 + 2 + 1 = 7회

 

1 5 ->  1번 줄의 5번 프렛은 이미 눌려져 있기 때문에 그대로 나둔다 = 7 + 0 = 7회

 

1 3 -> 1번 줄의 3번 프렛

- 3보다 높은 프렛이 눌려 있기 때문에  5번 떼고, 3번을  눌러둔다 = 7 + 1 + 1 = 9회

 

음배열로 만들어 준뒤 각 음을 인덱스로 해 주고 각 배열에 프렛을 넣어주면 된다.

기존 프렛이 새로운 프렛보다 클 때만 조심하면 되는데 나는 스택에 있는 프렛의 머리가 작거나 같아질 때까지 pop을 한후

프렛을 넣어주는 방식으로 구현했다. 

 

코드 구현

#pragma warning(disable: 4996)
#include <iostream>
#include<string>
#include <cassert>

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


class Stack {

private:
	struct List {
		Node* head;
		int count;
	};
	List* list;

public:
	Stack() {
		list = ListInit(); //생성자로 초기화                 아래부터 코드를 보면 암묵적으로 this생략가능
	}

	List* ListInit() {
		List* newlist = new List;
		newlist->head = nullptr;
		newlist->count = 0;
		return newlist;
	}

	bool ListisEmpty() {
		if (this->list->head == nullptr) {
			return true;
		}
		else
			return false;
	}
	void ListPush(int data, int* fingercount) {
		Node* newNode = new Node;
		newNode->data = data;
		if (this->list->head == nullptr) {
			this->list->head = newNode;
			this->list->head->next = nullptr;
		}
		else {
			newNode->next = this->list->head;
			this->list->head = newNode;
		}
		(this->list->count)++;
		(*fingercount)++;  // 기존 스택과 다른 부분

	}
	int ListPop(int *fingercount) {
		assert(this->ListisEmpty() == false);

		Node* delnode = this->list->head;
		int deldata = delnode->data;
		this->list->head = this->list->head->next;
		delete delnode;
		(this->list->count)--;
		(*fingercount)++;  //기존 스택과 다른 부분
		return deldata;

	}

	int Listpeek() {
		/*assert(this->ListisEmpty() == false);*/
		if (this->ListisEmpty()) {
			return 0;
		}
		else
		    return this->list->head->data;

	}

	/*void LClear() {
		while (this->ListisEmpty() == false) {
			this->ListPop();
		}
	}*/
	~Stack() {
		delete this->list->head;
		delete this->list;
	}
};



int main() {
	using namespace std;
	Stack* listpret = new Stack[500010];
	int N, K, i, sound, pret;
	int fingercount = 0;

	scanf("%d %d", &N, &K);
	for (i = 0; i < N; i++) {
		scanf("%d %d", &sound, &pret);
		if (listpret[sound].ListisEmpty()) { //스택이 비었다면 그냥 추가해 준다.
			listpret[sound].ListPush(pret, &fingercount);

		}
		else {
			if (listpret[sound].Listpeek() < pret) {  //기존 pret 이 새 pret보다 작을 경우 그냥 추가해주면 된다
				listpret[sound].ListPush(pret, &fingercount);
			}
			else if (listpret[sound].Listpeek() == pret) {  //같을 경우에는 아무것도 하지 않는다.
				;
			}
			else {
				while (listpret[sound].ListisEmpty() == false) { // 기존 pret 이 새 pret보다 클 경우
					listpret[sound].ListPop(&fingercount);
					if (listpret[sound].Listpeek() == pret) {  //기존 pret의 머리가 더 작아 질때 까지 반복한다.
						break;      //같아지면 아무것도 하지않고 break한다.
					}
					if (listpret[sound].Listpeek() < pret) {  //작아지면 추가한다.
						listpret[sound].ListPush(pret, &fingercount);
						break;
					}
				}
			}
		}
	}

	cout << fingercount << endl;

}

 

 

다음은 큐로 찾아오겠습니다..