코딩테스트/SWEA_Java
Q. 1206. View (D3)
Ski_
2023. 5. 7. 22:03
0. 문제
D3 난이도의 문제이고, 구현 문제라고 생각된다.
빌딩들의 높이가 주어지고, 오른쪽/왼쪽 두 칸이 비어있으면 그 집은 조망권이 확보된다고 말할 때,
조망권이 확보되는 세대의 수를 구하는 문제이다.
1. 풀이
1) 모든 땅에 대해 왼쪽 2칸의 높이의 최대값 & 오른쪽 2칸 높이의 최대값을 저장한다.
2) 그리고 두 값을 현재 땅의 높이와 비교해서,
현재 땅이 양 옆 높이의 최대값보다 높은 경우 그 차이를 결과에 저장하는 방식으로 풀었다.
import java.util.Scanner;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
class Solution
{
// static Scanner scanner;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static int[] heights;
static int buildingCnt;
static void input() throws IOException
{
buildingCnt = Integer.parseInt(br.readLine());
heights = new int[buildingCnt];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < buildingCnt; i++) {
int height = Integer.parseInt(st.nextToken());
heights[i] = height;
}
}
static void pro(int tc) {
int[] leftMaxHeightBuildings = new int[buildingCnt];
int[] rightMaxHeightBuildings = new int[buildingCnt];
for (int i = 2; i < buildingCnt - 2; i++) {
leftMaxHeightBuildings[i] = Math.max(heights[i - 1], heights[i - 2]);
rightMaxHeightBuildings[i] = Math.max(heights[i + 1], heights[i + 2]);
}
int res = 0;
for (int i = 2; i < buildingCnt - 2; i++) {
int compare = Math.max(leftMaxHeightBuildings[i], rightMaxHeightBuildings[i]);
if (heights[i] > compare) {
res += heights[i] - compare;
}
}
sb.append('#').append(tc).append(' ').append(res).append('\n');
}
public static void main(String args[]) throws Exception
{
// System.setIn(new FileInputStream("res/input.txt"));
// scanner = new Scanner(System.in);
int T = 10;
for(int test_case = 1; test_case <= T; test_case++)
{
input();
pro(test_case);
}
System.out.println(sb);
}
}
2. 시간복잡도 계산
0) N의 최대값은 1000이다.
1) 빌딩의 높이 저장 - O(N)
2) 풀이 1번 - O(N)
3) 풀이 2번 - O(N)
따라서 시간복잡도는 O(3N)이고, 시간제한은 20초이므로
1초에 약 1억번 연산을 한다고 가정하면, 1초 이내에 풀 수 있다.
3. 성능 개선 방안
1) 입력값을 받으면서 양 옆의 높이의 최대값을 계산할 수 있다.
(코드가 복잡해지고, 입력과 계산 부분이 합쳐지므로 시도하지 않았다.)
2) 높이가 최대 255으로 2^9이고,int 타입의 경우 2^32로
비트마스킹을 사용하면 하나의 int 자료형에 3개의 빌딩 높이를 넣을 수 있다.
(너무 복잡해 질 것 같아서 시도하지 않았다.)
반응형