[C++][자료구조] 살아남은 산천어 알 세기 (스택)

<문제 설명>

 

 

그림으로 간단히 표현해봤다.

파란색 동그라미가 쳐진 공간이 산천어 알이 살아남을 수 있는 공간이다.

 

나는 stack에 알이 살아남는 공간을 넣거나 빼기로 했다.

예를 들어 height[1]~height[3] 을 보면,

index 1 -> 2로 갔을 때 stack에 1을 세 번 push해주고

다시 index 2->3으로 갔을 때 stack에서 한 번 pop해줘서

stack에 1이 두 개가 남도록 한 것이다.

 

 

 

 

*코드 참고사항

preMax = 알을 낳기 전 지나온 바닥 중 제일 높은 바닥의 높이

(ex. 현재 2위치에 있을 때 preMax는 3, 현재 5위치에 있을 때 preMax는 2)

now = 현재 위치의 바닥 높이

 

 

알이 살아남는 경우별로 조건이 있다.

 

<알이 살아남는 경우>

1. index 1~3

: 임의로 현재 3위치, now=2, preMax=height[1]=3

preMax가 now보다 높음

-> 위치2일 때 push 세 번, 위치3일 때 pop 한 번

 

** 주의

현재 바닥이 직전의 바닥보다 높지만 preMax보다는 낮은 경우이다.

현재 3위치일 때 preMax보다 낮다고 push하면 안 되고 pop을 해야 한다.

if (preMax > now && height[i-1] >= now)

위 주황색 조건을 넣은 이유이다.

 

 

2. index 3~7

: 현재 7위치, now=3, preMax=height[3]=2

preMax가 now보다 낮음

-> 위치4~6일 때 깊이만큼 push, 위치7일 때 pop할 필요 없음

 

 

 

<코드>

// 산천어 문제
#include <iostream>
#include <array>
using namespace std;
const int MAX_STACK_SIZE = 20;

class Stack {
	int data[MAX_STACK_SIZE];
	int top;

public:
	Stack() { top = -1; }
	bool isEmpty() { return top == -1; }
	bool isFull() { return top == MAX_STACK_SIZE; }
	void push(int e) {
		if (isFull()) {
			cout << "스택 포화 에러" << endl;
			exit;
		}
		else
			data[++top] = e;
	}
	int pop() {
		if (isEmpty()) {
			exit;
		}
		else
			return data[top--];
	}
	int getTop() { return top; }
};

int main() {
	int height[] = { 0,3,0,2,1,0,0,3,3,1,2 };
	Stack st;

	int preMax = 0;	// 알을 낳기 전의 제일 높은 바닥의 높이
	for (int i = 0; i < 11; i++) {
		int now = height[i];

		// 현재 바닥이 제일 높았던 바닥보다 작고, 
		// 현재 바닥이 직전의 바닥보다 작거나 같으면 push(1)
		if (preMax > now && height[i-1] >= now) {
			for (int j = 0; j < (preMax - now); j++)	// 제일 높았던 바닥-현재 바닥 만큼 push
				st.push(1);
		}

		// 직전의 바닥이 현재 바닥보다 낮으면
		if (height[i - 1] < now) {
			if (preMax > now) {				// 제일 높았던 바닥이 현재 바닥보다 높으면
				for (int j = 0; j < (preMax - now); j++)
					st.pop();				// 제일 높았던 바닥-현재 바닥 만큼 pop
			}
			preMax = now; // 구덩이 하나를 지났으므로 현재 바닥을 제일 높은 바닥으로 재설정
		}

		if (preMax < now) // 제일 처음으로 preMax를 설정하기 위해
			preMax = now;
	}
	
	cout << "살아남은 산천어 알은 " << (st.getTop()+1) * 1000 << "개이다" << endl;

	return 0;
}

 

 

실행 결과를 보자

맨 위의 그림을 보면 파란색 동그라미는 8개, 따라서 8000개가 맞다.