개요

백준 2841번: 외계인의 기타 연주

• 입력
  첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000)

  다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수는 줄의 번호이고 두 번째 정수는 그 줄에서 눌러야 하는 프렛의 번호이다. 입력으로 주어진 음의 순서대로 기타를 연주해야 한다.

• 출력
  첫째 줄에 멜로디를 연주하는데 필요한 최소 손가락 움직임을 출력한다.

접근방법

1. 각 음악안에 프렛이 있어서 음악갯수만큼 스택을 생성해야하고, 한 스택안에 그 음악에 해당하는 프렛들 넣기로 생각했다.
2. 음악수인 6개의 스택을 생성 후, 각 음악의 프렛을 스택의 top과 비교하여
   스택의 top이 이번 프렛보다 더 작을때까지 손가락 움직이는수+1을 하고 pop()을 한다.
3. 스택의 top보다 이번 프렛이 크다면 손가락 움직인 수 +1하고 push()해준다.

여섯 개의 함수를 이용한 코드

#include<iostream>
#include<stack>

using namespace std;
int N = 0,P=0,Ans=0;
stack<int> First;
stack<int> Second;
stack<int> Third;
stack<int> Fourth;
stack<int> Fifth;
stack<int> Sixth;



//첫번재 음 프렛 관리
void FirstString(int fret) {
	if (First.empty()) {
		First.push(fret);
		Ans++;
	}
	else {
		//1번 노래 스택이 비어있지않고, 프렛 스택의 top이 이번에 누를 프렛보다 작을때까지 pop
		while (!First.empty() && First.top()>fret) {
			First.pop();
			//손가락 떼었으므로 답 ++
			Ans++;

		}
		//만약 같은 프렛이 있다면 스택 변동 x, 손가락 이동횟수 변동x
		if (!First.empty() && fret == First.top()) {
			return;
		}
		//스택이 비었거나 스택의 top이 작다면 이번값 push
		else {
			First.push(fret);
			Ans++;
			return;
		}
	}
}
//두번째 음 프렛 관리
void SecondString(int fret) {
	if (Second.empty()) {
		Second.push(fret);
		Ans++;
	}
	else {
		//2번 노래 스택이 비어있지않고, 프렛 스택의 top이 이번에 누를 프렛보다 작을때까지 pop
		while (!Second.empty() && Second.top() > fret) {
			Second.pop();
			//손가락 떼었으므로 답 ++
			Ans++;

		}
		//만약 같은 프렛이 있다면 스택 변동 x, 손가락 이동횟수 변동x
		if (!Second.empty() && fret == Second.top()) {
			return;
		}
		//스택이 비었거나 스택의 top이 작다면 이번값 push
		else {
			Second.push(fret);
			Ans++;
			return;
		}
	}
}
//세번째 음 프렛 관리
void ThirdString(int fret) {
	if (Third.empty()) {
		Third.push(fret);
		Ans++;
	}
	else {
		//3번 노래 스택이 비어있지않고, 프렛 스택의 top이 이번에 누를 프렛보다 작을때까지 pop
		while (!Third.empty() && Third.top() > fret) {
			Third.pop();
			//손가락 떼었으므로 답 ++
			Ans++;

		}
		//만약 같은 프렛이 있다면 스택 변동 x, 손가락 이동횟수 변동x
		if (!Third.empty() && fret == Third.top()) {
			return;
		}
		//스택이 비었거나 스택의 top이 작다면 이번값 push
		else {
			Third.push(fret);
			Ans++;
			return;
		}
	}
}
//네번재 음 프렛관리
void FourthString(int fret) {
	if (Fourth.empty()) {
		Fourth.push(fret);
		Ans++;
	}
	else {
		//4번 노래 스택이 비어있지않고, 프렛 스택의 top이 이번에 누를 프렛보다 작을때까지 pop
		while (!Fourth.empty() && Fourth.top() > fret) {
			Fourth.pop();
			//손가락 떼었으므로 답 ++
			Ans++;

		}
		//만약 같은 프렛이 있다면 스택 변동 x, 손가락 이동횟수 변동x
		if (!Fourth.empty() && fret == Fourth.top()) {
			return;
		}
		//스택이 비었거나 스택의 top이 작다면 이번값 push
		else {
			Fourth.push(fret);
			Ans++;
			return;
		}
	}
}
//다섯번째 음 프렛 관리
void FifthString(int fret) {
	if (Fifth.empty()) {
		Fifth.push(fret);
		Ans++;
	}
	else {
		//5번 노래 스택이 비어있지않고, 프렛 스택의 top이 이번에 누를 프렛보다 작을때까지 pop
		while (!Fifth.empty() && Fifth.top() > fret) {
			Fifth.pop();
			//손가락 떼었으므로 답 ++
			Ans++;

		}
		//만약 같은 프렛이 있다면 스택 변동 x, 손가락 이동횟수 변동x
		if (!Fifth.empty() && fret == Fifth.top()) {
			return;
		}
		//스택이 비었거나 스택의 top이 작다면 이번값 push
		else {
			Fifth.push(fret);
			Ans++;
			return;
		}

	}
}
//여섯번째 음 프렛 관리
void SixthString(int fret) {
	if (Sixth.empty()) {
		Sixth.push(fret);
		Ans++;

	}
	else {
		//6번 노래 스택이 비어있지않고, 프렛 스택의 top이 이번에 누를 프렛보다 작을때까지 pop
		while (!Sixth.empty() && Sixth.top() > fret) {
			Sixth.pop();
			//손가락 떼었으므로 답 ++
			Ans++;

		}
		//만약 같은 프렛이 있다면 스택 변동 x, 손가락 이동횟수 변동x
		if (!Sixth.empty() && fret == Sixth.top()) {
			return;
		}
		//스택이 비었거나 스택의 top이 작다면 이번값 push
		else {
			Sixth.push(fret);
			Ans++;
			return;
		}
	}
}


void input() {
	int string = 0, fret = 0;
	cin >> N >> P;
	for (int i = 0; i < N; i++) {
		cin >> string >> fret;
		switch (string) {
		case 1:
			FirstString(fret);
			break;
		case 2:
			SecondString(fret);
			break;
		case 3:
			ThirdString(fret);
			break;
		case 4:
			FourthString(fret);
			break;
		case 5:
			FifthString(fret);
			break;
		case 6:
			SixthString(fret);
			break;

		}
	}
	cout << Ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	input();
}

한 함수에 짠 코드

#include<iostream>
#include<stack>

using namespace std;
int N = 0,P=0,Ans=0;
stack<int> First;
stack<int> Second;
stack<int> Third;
stack<int> Fourth;
stack<int> Fifth;
stack<int> Sixth;
//각 함수에서 어떤스택인지 판별한 후 해당 스택 받아오는 스택포인터
stack<int>* S;

void String(int string, int fret) {
	//몇번째 스택인지에 따라 스택포인터 S에 해당 포인터 넣어줌
	switch (string) {
	case 1:
		S = &First;
		break;
	case 2:
		S = &Second;
		break;
	case 3:
		S = &Third;
		break;
	case 4:
		S = &Fourth;
		break;
	case 5:
		S = &Fifth;
		break;
	case 6:
		S = &Sixth;
		break;
	}
    //만약 해당 음의 스택 비어있다면 바로 push하고 손가락 움직임 +1
	if (S->empty()) {
		S->push(fret);
		Ans++;

	}
	else {
		//6번 노래 스택이 비어있지않고, 프렛 스택의 top이 이번에 누를 프렛보다 작을때까지 pop
		while (!S->empty() && S->top() > fret) {
			S->pop();
			//손가락 떼었으므로 답 ++
			Ans++;

		}
		//만약 같은 프렛이 있다면 스택 변동 x, 손가락 이동횟수 변동x
		if (!S->empty() && fret == S->top()) {
			return;
		}
		//스택이 비었거나 스택의 top이 작다면 이번값 push
		else {
			S->push(fret);
			Ans++;
			return;
		}
	}
	
}


void input() {
	int string = 0, fret = 0;
	cin >> N >> P;
	for (int i = 0; i < N; i++) {
		cin >> string >> fret;
		String(string, fret);
	}
	cout << Ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	input();
}

생각

사실 firstString함수부터 sixthstring 함수까지 내부 구조가 동일한데 스택만 달라서
똑같은걸 6번 복사하니 현타가 왔다.

따라서, 한 함수에 stack< int > 새로 생성 후 이 스택에 기존 스택 복사하여 구현하고자 했다.
하지만 포인터로 짰어야했는데 그냥 임시 스택 stack< int >tmp를 생성해 스택들을 대입하고
s를 통해 처리하니 기존 스택들에 변화가 없어서 좀 헤매다가 포인터를 떠올렸다.