SW Expert Academy 의 1206번 문제입니다. 건물이 옆으로 밀집한 공간에서 각 층마다 조망권을 확보해야 합니다. 이 때 조망권은, 각 층에서 최소한 두 칸 이내에는 다른 건물이 없어야 보장된다고 말합니다. (즉, 양 옆에 두 칸 이상의 공백이 존재해야 한다는 말)
- 난이도 : 1
문제 조건
가로 길이는 1000 이하로 주어진다.
각 건물의 높이는 최대 255이다.
맨 왼쪽 두 칸과 맨 오른쪽 두 칸은 건물을 짓지 않는다.
위의 상황은 가로 길이가 7칸이고, 건물이 3개 쌓여진 상황입니다. 파란색으로 칠해진 칸만이 양 옆에 최소 2칸 이내에 건물이 없으므로, 조망권이 확보되었다고 할 수 있습니다. 나머지 칸들은 모두 조망권이 확보되지 못한 상황입니다.
Input
첫 줄에는 테스트 케이스의 가로 길이가 주어지고, 그 다음줄부터 건물들의 높이가 주어집니다.
Output
테스트 케이스 번호별로 조망권이 확보된 칸의 갯수를 출력합니다.
처음에 생각한 아이디어
아직 연습이 덜해서 그런지 처음에는 “위 그림을 2차원 배열처럼 생각해서 풀어보자” 였습니다. 즉,
- 가로 1000열, 세로 255행 2차원 배열을 만들고 모든 칸을 0으로 초기화 한다.
- i번째 열에 세워지는 ‘0번째 행’부터 ‘건물 높이-1번째 행’까지 1을 저장한다. (예: 5번째 열에 높이 80의 건물이 세워지면, arr(5)(0)~arr(5)(79) 를 모두 1로 채운다)
- 그런 식으로 2차원 평면상에 건물의 모양처럼 만든다. 0이면 칸이 없는 것이고, 1이면 칸이 존재하는 것이다.
이런 식으로 가로 1000열, 세로 255행 칸에 건물을 채워넣고 문제를 풀었습니다. 그리고 각 열의 각 층마다 계속 반복문을 돌아, 그 층의 양 옆을 조사했습니다.
다만, 모든 열마다 반복을 한다면 조금 낭비일 것 같다는 생각이 들었습니다. 그래서 바로 옆의 빌딩보다 높이가 작다면 볼 것도 없이 조망권이 확보되지 못하므로 조건문을 넣어 넘어가도록 했습니다.
<1> 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
using namespace std;
int main(void)
{
int test_case, test_num;
int T;
int arr[255][1000];
int* check;
int val = 0;
int count = 0;
for (test_case = 1; test_case <= 10; ++test_case)
{
cin >> test_num;
check = new int[test_num];
for (int i = 0; i < 255; i++) {
for (int j = 0; j < 1000; j++) {
arr[i][j] = 0;
}
}
//i는 열, j는 행
for (int i = 0; i < test_num; i++) {
cin >> val;
if (val == 0) {
/* 아무것도 하지 않는다. */
check[i] = 0;
}
else if (val != 0) {
check[i] = val; // i번째 열의 건물 높이를 저장한다.
for (int j = 0; j < val ; j++) {
arr[j][i] = 1;
}
}
}
// 배열을 0 또는 1로 다 채웠으면, 이제 열마다 돌아가면서 확인한다.
for (int i = 0; i < test_num; i++) {
if (check[i] > check[i+1] && check[i] != 0){
for (int j = 0; j < check[i]; j++) {
if (arr[j][i - 1] == 0 && arr[j][i - 2] == 0
&& arr[j][i + 1] == 0 && arr[j][i + 2] == 0)
{
/* 조망권 확보*/
count++;
}
}
}
}
cout << "#" << test_case << " " << count << endl;
count = 0;
delete[] check;
check = NULL;
}
return 0;
}
하지만 이와 같이 소스코드를 제출했을 때 저의 코드 실행시간은 30ms 나 되었는데, SW아카데미에 C++로 제출하신 많은 분들은 10ms 안팎의 실행시간을 보였습니다.
원인을 생각해 보았을 때, 제 코드가 이차원 배열을 사용했기 때문에 그런 것으로 생각했습니다. 같은 문제를 불필요하게 이차원 배열을 이용해서 구현했기 때문에 실행 시간이 늘어난 것이었습니다.
다시 생각한 아이디어 : 굳이 2차원 평면을 생각하지 말자
굳이 모든 건물들을 세워놓은 다음에 풀지 않아도 되는 문제였습니다. 즉, 이차원 공간이 필요한 것이 아니라 건물의 ‘높이’ 비교만 하면 되는 문제입니다.
어차피 내 옆, 내 옆옆의 건물이 나보다 높다면 내 건물은 조망권이 확보되지 못합니다.
그러므로 불필요한 케이스는 바로 넘어가게 하고, 조망권이 확보될 수 있는 경우만 생각합니다.
내 양 옆 두 칸 이내의 건물들이 나보다 높이가 낮을 때, 그 때만 보면 됩니다.
길이가 1000인 일차원 배열을 선언해 놓고, 인풋값을 받는다. 이 배열에는 i번째 열에 세워지는 건물의 높이가 저장될 것이다.
i번째 열에 세워지는 건물 양 옆 두 칸 내의 건물들의 높이를 나와 비교해서, 모두 작을 경우에만 조망권을 조사한다.
왼쪽 두 칸, 왼쪽 한 칸, 오른쪽 한 칸, 오른쪽 두 칸 이내의 건물들과 높이 비교를 한다. 가장 높이 차가 적게 나는 경우가, 내 건물의 조망권이 확보된 층 개수와 같다.
<2> 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
using namespace std;
int main(void)
{
int test_case, test_num;
int T;
int* check;
int min, L2, L1, R1, R2;
int count;
for (test_case = 1; test_case <= 10; ++test_case)
{
int arr[1001];
cin >> test_num;
for(int i = 0; i<test_num; i++){
cin >> arr[i];
}
count = 0;
for(int j = 2; j < test_num - 2; j++){
if( arr[j] - arr[j-2] <= 0 || arr[j] - arr[j-1] <= 0 || arr[j] - arr[j+1] <=0 || arr[j] - arr[j+2] <=0 ){
continue;
}
min = 99999;
L2 = arr[j] - arr[j-2];
L1 = arr[j] - arr[j-1];
R1 = arr[j] - arr[j+1];
R2 = arr[j] - arr[j+2];
if(L2 < min)
min = L2;
if(L1 < min)
min = L1;
if(R1 < min)
min = R1;
if(R2 < min)
min = R2;
count += min;
}
cout << "#" << test_case << " " << count << endl;
}
return 0;//정상종료시 반드시 0을 리턴해야합니다.
}
이렇게 하니 실행시간이 확연히 차이가 났습니다. 처음 경우보다 약 20ms 정도 줄어든 9ms가 나왔습니다.
하지만 좀 더 줄이고 싶었습니다. 5~7ms가 나온 사용자도 있었기 때문입니다. 나중에 알고리즘 테스트에서는 실행 시간을 단축시키는 최적화 작업도 중요하다고 합니다.
고수준 입출력 방식과 저수준 입출력 방식
그래서 조사해 보니, cin과 cout 와 같은 고수준 입/출력 방식들은 실행 속도가 느려질 수 있는 요인이라고 합니다.
따라서 C언어에서 흔히 사용하는 stdio.h 의 scanf, printf 함수를 택했습니다. 이들은 cin, cout보다 저수준 입출력 방식입니다.
cin, cout 대신 scanf, printf로 바꾸기만 하였는데 실행 속도가 2ms 줄어든 7ms로 바뀌게 되었습니다.