[백준] 6198 옥상 정원 꾸미기 c++ 구현

 

목차

 

 

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

6198번: 옥상 정원 꾸미기

문제

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 구현 방향

c++에 있는 스택 라이브러리를 이용하여 가독성 있게 구현 해 보았다.

 

 

 

 

 

 

문제 풀이 시 주의점

정수의 범위가 매우 크기 때문에 long long int로 풀어줘야 한다. 안 그러면 방법이 맞았는데도 

맞았는데도 헤매는 참사가 일어난다.

 

얼핏 간단해보여 이중 순회로 풀게 되면 빅오 표기법으로 n^2이 나오게 되어 시간초과를 하게 된다.

 따라서 스택을 이용해서 풀게 되면 스택의 연산은 상수 시간이 걸리기 때문에 빅오 표기법으로 n 시간이 걸리게 된다.

(골드 문제인 이유가 있다..)

 

아래는 잘못된 풀이법이다..(브론즈 정도의 문제였다면 맞았을지도..?)

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


int main() {
	using namespace std;

	long long int num, floor, i, j, count =0;
	
	scanf("%lld", &num);

	long long int* arr = new long long int[800001];
	for (i = 0; i < num; i++) {
		scanf("%d", &floor);
		arr[i] = floor;
	}
	for (i = 0; i < num; i++) {
		for (j = i + 1; j < num; j++) {
			if (arr[i] > arr[j]) {
				count++;
			}
			else {
				break;
			}
		}
	}
	cout << count;

}

 

 

문제 풀이

약간의 아이디어가 필요하다.

스택을 만들 때 크기순으로 스택이 만들어지게끔 한다.

 

구성

counttypes =>  볼 수 있는 층이 증가될 층수의 종류

 

count =>  볼 수 있는 층의 총합

 

()안의 수 => 볼 수 있는 층의 개수

( 괄호안의 수가 0일 경우는 스택에 값이 안들어 와 증가할지 모르기 때문에 counttypes에서 제외해야 함)

 

설명

10 -> 10(0)

빈 스택이므로 그냥 스택에 추가 ( counttypes = 0, count = 0)

 

3 -> 3(0) 10(1)

1.스택에 값 추가

2. counttypes의 증가  (10층)

3. count 갱신

( counttypes = 1, count = 1)

 

7 -> 7(0) 10(3)   

1. 스택top보다 크므로 큰 top이 나올때까지 pop

2. countypes의 재설정 (10층)  ( counttypes = 1)

3. 스택에 값 추가

4. count 갱신 (count = 1 + 1 = 2)

 

4 -> 4(0) 7(1) 10(1)

1.스택에 값 추가

2. counttypes의 증가 (10층, 7층)

3. count 갱신

( counttypes = 2, count = 2+2 = 4)

 

12 ->  12(0)

1. 스택top보다 크므로 큰 top이 나올때까지 pop

2. countypes의 재설정 (층 없음 = 0)  ( counttypes = 0 )

3. 스택에 값 추가

4. count 갱신 (count = 4 +0 = 4)

 

2 -> 2(0) 12(1)

1.스택에 값 추가

2. counttypes의 증가 (12층)

3. count 갱신

( counttypes = 1, count = 4+1 = 5)

 

 

 

 

코드구현

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

int main() {
	using namespace std;
	stack<long long int> Building; //  long long int로 해주어야 함!
	long long int num, floor, i, j, count =0, counttypes = 0;
	scanf("%lld", &num);

	for (i = 0; i < num; i++) {
		scanf("%d", &floor);
		if (Building.empty()) {  // 처음 시작 시 비어있으므로 그냥 넣어준다,
			Building.push(floor);
		}
		else {
			if (Building.top() > floor) {  // 스택의 top이 새로운 층보다 클 경우
				Building.push(floor);     //  새로운 층을 넣어주고  counttypes를 늘려준다.  
				counttypes++;    
				count += counttypes;   //카운트에 합산한다.
			}
			else {

				while (true) {  // 스택의 top이 새로운 층보다 작을 경우
					Building.pop();   
					if (Building.empty())      //비어있을 경우 멈추어야지 오류가 안남
						break;
					if (Building.top() > floor) {   //스택의 top이 새로운 층보다 클 경우 멈춘다.
						break;
					}
				}
				counttypes = Building.size();  //counttypes를 스택size로 초기화해준다.
				Building.push(floor);    //새로운 층을 넣어주고 카운트에 합산한다.
				count += counttypes;

			}
		}

	}
	cout << count;

}

 

스택을 잘 활용하면 시간을 단축할 수 있다는 것을 보여준 문제였다!