[Algorithm][Sort] 1206. [S/W 문제해결 기본] 1일차 - View

순서

I. 문제

II. 접근

III. 구현

문제출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV134DPqAA8CFAYh&categoryId=AV134DPqAA8CFAYh&categoryType=CODE&problemTitle=1206&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

 

---

** Sort로 풀진 않았는데 정확히 어떤 유형인지 잘 모르겠다..

I. 문제

요약>> 건물높이가 쭉 주어지는데 양옆 2칸씩에 다른 집이 없다면 조망권 +1

[제약 사항]

가로 길이는 항상 1000이하로 주어진다.

맨 왼쪽 두 칸과 맨 오른쪽 두 칸에는 건물이 지어지지 않는다. (예시에서 빨간색 땅 부분)

각 빌딩의 높이는 최대 255이다.

입력형식 입력 파일의 첫 번째 줄에는 테스트케이스의 길이가 주어진다. 그 바로 다음 줄에 테스트 케이스가 주어진다. 총 10개의 테스트케이스가 주어진다.	출력형식 #부호와 함께 테스트 케이스의 번호를 출력하고 공백 문자 후 테스트 케이스의 조망권이 확보된 세대의 수를 출력한다.
10 0 0 225 214 82 73 241 179 0 0 1000 0 0 215 200 255 32 124.....  ...	#1 73 #2 .... #3 .... ..... #10 ....

 

---

II. 접근

전형적인 스택문제일까 정렬문제일까 탐색문제일까 고민했지만
그냥 양옆 +-2 만큼 높이를 확인하면 되지 않을까 하는 생각...

i-2 ~ i+2 사이에 높이 확인해서 나를 제외한 가장 높은 빌딩만큼 빼주면 된다.

 

---

1. 입력

int 형의 List[1000] 에 각 빌딩의 높이를 담으면 된다.

 

2. 문제 풀이

II. 접근의 생각대로

List의 Index를 넘어가며 i-2 ~ i+2만큼 확인
1. i(내 현위치) 가 i-2 ~ i+2 중에서 최대가 아닐때 : 조망권 0
2. i(내 현위치) 가 i-2 ~ i+2 중에서 최대일 때 : 조망권 += 내 높이 - 나를 제외한 최고 빌딩의 높이

 

3. 구현

<hide/>
#include <stdio.h>
#include <cstring>
#include <iostream>

constexpr int len_empty{ 2 };
using namespace std;

const int T{ 10 }; // 테케 10개 고정
int buildings_count{ 0 };
int Buildings[1000]{ 0, }; // 빌딩 높이 가지고 있는 배열
int ans{ 0 }; // 조망권 획득 정답

void input() {
	buildings_count = 0;
	memset(Buildings, 0, sizeof(Buildings));
	ans = 0;
	std::cin >> buildings_count;
	
	for (int i = 0; i < buildings_count; i++) {
		std::cin >> Buildings[i];
	}
}

// 최대높이 구하는 함수 따로 만듦
int findMax(int ref) {
	int max_height{ 0 };
    // 내 양옆 2개씩 확인한다.
	for (int i = ref - 2; i <= ref + 2; i++) {
        // 자신이라면 넘어가고
		if (i == ref) {
			continue;
		}
        // 나머지 4개 중 최대높이 구함
		if (Buildings[i] >= max_height) {
			max_height = Buildings[i];
		}
	}
	return max_height;
}

// 정답 찾는 함수
void findView() {
	int max_height{ 0 };
	for (int i = len_empty; i < buildings_count- len_empty; i++) {
        // list 쭉 확인하며 양옆 2개에 대해 최댓값 구함
		max_height = findMax(i);
        // 내가 가장 큰 빌딩일 때
		if (Buildings[i] > max_height) {
			ans += Buildings[i] - max_height; // 조망권 획득
		} else {
			continue; // 아닌경우 : 조망권 없음
		}
	}

	return;
}


int main() {
	for (int t = 0; t < T; t++) {
		ans = 0;
		input();
		findView();
		printf("#%d %d\n", t + 1, ans);
	}
	return 0;
}

 

다른방법은 뭐가 있을까,,