[SWEA 1206] View — Java 배열 탐색과 조망권 계산

1. 문제 개요

• 문제: SWEA 1206 — View
• 난이도: D3
• 언어: Java
• 알고리즘: 구현, 배열 탐색
• 핵심 자료구조: 1차원 배열 (int[])
• 시간 복잡도: O(N)
• 공간 복잡도: O(N)

문제 요약

일렬로 배치된 건물들의 높이가 주어질 때, 각 건물에서 양쪽 2칸 이내에 있는 건물보다 높은 층의 세대만 조망권을 확보할 수 있다.

모든 건물에서 조망권을 확보한 세대 수의 합을 계산하는 문제다.

핵심 조건

1. 건물 높이는 최대 255이다.
2. 건물의 높이가 0이면 건물이 없는 위치다.
3. 맨 왼쪽 2칸과 맨 오른쪽 2칸에는 건물이 없다.
4. 각 건물은 양옆 2칸씩 총 4개 건물과 비교한다.
5. 테스트케이스는 총 10개로 고정되어 있다.

---

2. 문제 해결 아이디어

2.1. 최초 접근 — 2차원 배열

처음에는 건물의 높이를 실제 격자 형태로 표현하려고 했다.

int[][] matrix = new int[256][building];

• 행: 건물의 높이
• 열: 건물의 위치
• 값: 건물이 존재하면 1, 존재하지 않으면 0

예를 들어 건물 높이가 다음과 같다면,

0 0 3 2 1

격자는 아래와 같이 표현할 수 있다.

높이
3 | 0 0 1 0 0
2 | 0 0 1 1 0
1 | 0 0 1 1 1
 +-----------
   0 1 2 3 4  건물 위치

그러나 이 문제는 건물의 높이만 비교하면 되므로 2차원 격자를 구성할 필요가 없다.

 

개선 방향: 2차원 배열 대신 각 건물의 높이를 1차원 배열에 저장한다.

int[] heights = new int[n];

이렇게 하면 불필요한 격자 생성 및 탐색을 생략할 수 있다.

2.2. 개선 접근 — 1차원 배열

현재 건물 i를 기준으로 다음 4개의 건물을 비교한다.

인덱스:     i-2   i-1    i    i+1   i+2
건물 높이:   30    50   100    70    40
                       ↑
                    기준 건물

조망권 확보 여부는 기준 건물과 주변 4개 건물의 최대 높이를 비교하여 판단한다.

조망권 확보 조건

기준 건물 높이 > 주변 4개 건물의 최대 높이

주변 건물 중 하나라도 기준 건물과 높이가 같거나 더 높으면 조망권 확보 세대 수는 0이다.

조망권을 확보했다면 다음과 같이 계산한다.

조망권 확보 세대 수 = 기준 건물 높이 - 주변 최대 높이

예시에서는 다음과 같다.

기준 건물 높이 = 100
주변 최대 높이 = 70

조망권 확보 세대 수 = 100 - 70 = 30

주의: 주변 4개 건물과의 높이 차이를 각각 더하는 것이 아니라, 주변에서 가장 높은 건물과의 차이만 계산한다.

---

3. Java 최종 풀이

import java.io.*;
import java.util.StringTokenizer;

class Solution {
  public static void main(String[] args) throws IOException {

      BufferedReader br = new BufferedReader(
          new InputStreamReader(System.in)
      );

      // 테스트케이스 10개 고정
      for (int tc = 1; tc <= 10; tc++) {

          // 건물 개수
          int n = Integer.parseInt(br.readLine());

          // 건물 높이 저장
          int[] heights = new int[n];

          StringTokenizer st = new StringTokenizer(br.readLine());

          for (int i = 0; i < n; i++) {
              heights[i] = Integer.parseInt(st.nextToken());
          }

          // 조망권 확보 세대 수
          int ans = 0;

          // 양 끝 2칸 제외
          for (int i = 2; i < n - 2; i++) {

              // 주변 4개 건물의 최대 높이
              int max = Math.max(
                  Math.max(heights[i - 2], heights[i - 1]),
                  Math.max(heights[i + 1], heights[i + 2])
              );

              // 기준 건물이 가장 높은 경우
              if (heights[i] > max) {
                  ans += heights[i] - max;
              }
          }

          System.out.println("#" + tc + " " + ans);
      }
  }
}

---

4. 헷갈렸던 포인트 정리

Q1. 2차원 배열로 건물 높이를 표현해야 하는가?

필요하지 않다.

건물의 높이를 이용한 비교만 수행하므로 1차원 배열로 충분하다.

int[] heights = new int[n];

2차원 배열을 사용하면 높이와 위치를 모두 표현할 수 있지만, 이 문제에서는 추가적인 공간과 연산이 발생한다.

판단 기준: 문제에서 실제 격자의 각 칸을 탐색해야 하는지, 아니면 행이나 열의 대표값만 필요한지 구분한다.

 

Q2. 2차원 배열 인덱스는 어떻게 사용하는가?

int[][] matrix = new int[256][building];

• matrix.length: 행 개수인 256
• matrix[0].length: 첫 번째 행의 열 개수인 building
• matrix[r][c]: r번째 행, c번째 열

 

초기 구현에서 다음과 같이 작성했다.

matrix[building][k] = 1;

이는 건물 개수를 행 인덱스로, 높이를 열 인덱스로 사용한 오류다.

 

건물을 아래에서 위로 채우려면 다음과 같이 작성할 수 있다.

for (int j = 0; j < building; j++) {
  int height = Integer.parseInt(st.nextToken());

  for (int k = 1; k <= height; k++) {
      matrix[256 - k][j] = 1;
  }
}

여기서 j는 건물 위치, k는 현재 채우는 높이를 의미한다.

 

Q3. 왜 반복문을 i = 2부터 시작하는가?

현재 건물을 기준으로 i-2, i-1, i+1, i+2에 접근해야 하기 때문이다.

for (int i = 2; i < n - 2; i++)

• 시작 인덱스: 2
• 마지막 인덱스: n - 3
• 종료 조건: i < n - 2

예를 들어 n = 10이라면 탐색 대상은 인덱스 2 ~ 7이다.

i = 0부터 시작하면 heights[-2]처럼 존재하지 않는 인덱스에 접근하여 ArrayIndexOutOfBoundsException이 발생한다.

 

Q4. 주변 건물 중 하나라도 더 높으면 탈락인가?

그렇다. 정확하게는 기준 건물 이상인 높이가 하나라도 있으면 해당 건물의 조망권 확보 세대 수는 0이다.

if (heights[i] > max) {
  ans += heights[i] - max;
}

기준 건물과 주변 최대 높이가 같아도 조망권이 확보되지 않는다.

 

Q5. 왜 Math.max()를 중첩해서 사용하는가?

Math.max()는 두 값 중 큰 값을 반환한다.

Math.max(10, 20); // 20

4개의 값 중 최댓값을 구하려면 중첩 호출할 수 있다.

int max = Math.max(
  Math.max(a, b),
  Math.max(c, d)
);

이 문제에서는 기준 건물을 제외한 양옆 4개 건물의 최대 높이를 구하는 데 사용한다.

 

Q6. Math.max()로 조건문을 대체할 수 있는가?

가능하다.

기존 코드:

if (heights[i] > max) {
  ans += heights[i] - max;
}

간소화한 코드:

ans += Math.max(0, heights[i] - max);

높이 차이가 음수 또는 0이면 0을 더하고, 양수라면 해당 차이를 더한다.

 

Q7. heights.length와 n은 같은가?

이 코드에서는 같다.

int[] heights = new int[n];

배열을 n 크기로 생성했으므로 다음 두 값은 동일하다.

heights.length == n

따라서 아래 반복문은 같은 의미다.

for (int i = 2; i < heights.length - 2; i++)

for (int i = 2; i < n - 2; i++)

Q8. 테스트케이스를 1개만 실행하면 왜 오답인가?

SWEA 1206번은 테스트케이스가 10개 고정이다.

로컬 디버깅 과정에서 다음과 같이 설정했다.

for (int tc = 0; tc < 1; tc++)

이는 첫 번째 테스트케이스만 처리한다.

 

실제 제출 시에는 반드시 10개를 모두 처리해야 한다.

for (int tc = 1; tc <= 10; tc++)

 

또한 테스트케이스 개수를 별도로 입력받지 않는다.

// SWEA 1206에서는 사용하지 않음
int T = Integer.parseInt(br.readLine());

각 테스트케이스의 첫 줄은 테스트케이스 개수가 아니라 건물 개수다.

Q9. NumberFormatException은 왜 발생했는가?

다음 코드에서 발생했다.

int n = Integer.parseInt(br.readLine());

이 코드는 한 줄 전체를 정수 하나로 변환한다.

 

그런데 아래와 같이 여러 정수를 한 줄에 입력했다.

0 0 254 185 76 227 84 175 0 0

공백으로 구분된 문자열 전체를 정수 하나로 변환할 수 없으므로 NumberFormatException이 발생한다.

 

올바른 입력은 다음과 같다.

10
0 0 254 185 76 227 84 175 0 0

첫 번째 줄은 건물 개수, 두 번째 줄은 각 건물의 높이다.

---

5. Java 필수 문법 정리

5.1. BufferedReader — 빠른 입력

BufferedReader br = new BufferedReader(
  new InputStreamReader(System.in)
);

Scanner 대신 사용할 수 있는 버퍼 기반 입력 방식이다.

 

String line = br.readLine();

readLine()은 한 줄을 문자열로 반환한다.

5.2. Integer.parseInt() — 문자열을 정수로 변환

int n = Integer.parseInt(br.readLine());

br.readLine()의 반환형은 String이므로 정수 연산이 필요하다면 형변환이 필요하다.

 

5.3. StringTokenizer — 공백 기준 입력 분리

StringTokenizer st = new StringTokenizer(br.readLine());

공백으로 구분된 여러 값을 하나씩 읽는다.

int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());

• nextToken(): 다음 토큰을 문자열로 반환
• countTokens(): 남아 있는 토큰 개수
• hasMoreTokens(): 다음 토큰 존재 여부

5.4. 1차원 배열 생성과 접근

int[] arr = new int[10];

arr[0] = 100;
arr[1] = 200;

int size = arr.length;

Java 배열의 인덱스는 0부터 시작한다.

5.5. 2차원 배열 출력 — 디버깅

static void printMatrix(int[][] arr) {
  for (int r = 0; r < arr.length; r++) {
      for (int c = 0; c < arr[r].length; c++) {
          System.out.print(arr[r][c] + " ");
      }
      System.out.println();
  }
}

 

간단히 전체 구조를 확인하려면 다음 방법도 사용할 수 있다.

System.out.println(Arrays.deepToString(arr));

이때 java.util.Arrays를 import해야 한다.

디버깅 출력은 제출 전에 제거해야 한다.

---

6. 로컬 컴파일 및 테스트 명령어

VS Code 터미널에서 Solution.java가 위치한 디렉터리를 기준으로 실행한다.

목적	명령어
Java 컴파일	javac Solution.java
프로그램 실행	java Solution
컴파일 후 실행	javac Solution.java && java Solution
파일 입력 실행	java Solution < input.txt
컴파일 + 파일 입력	javac Solution.java && java Solution < input.txt
결과 저장	java Solution < input.txt > output.txt
정답 비교	diff -u answer.txt output.txt

input.txt 사용 시 주의사항

SWEA에서 제공하는 input.txt는 로컬 테스트용 파일이다.

Java 코드에서 직접 파일을 읽을 필요 없이 입력 리다이렉션을 활용한다.

javac Solution.java && java Solution < input.txt

SWEA 제출 시에는 System.in을 사용하는 Java 코드를 그대로 제출한다.

또한 소스코드를 수정한 뒤에는 반드시 다시 컴파일해야 변경 사항이 적용된다.

---

7. 복잡도 분석

시간 복잡도 — O(N)

건물 높이를 입력받아 배열에 저장하는 과정은 O(N)이다.

이후 각 건물을 순회하면서 주변 4개 건물의 높이를 비교하는 과정도 O(N)이다.

따라서 테스트케이스 하나의 전체 시간 복잡도는 O(N)이다.

공간 복잡도 — O(N)

건물 N개의 높이를 저장하기 위해 길이 N인 정수 배열을 사용한다.

int[] heights = new int[n];

추가적인 격자나 배열은 생성하지 않으므로 공간 복잡도는 O(N)이다.

---

8. 최종 암기 코드

// 주변 2칸씩 비교
for (int i = 2; i < n - 2; i++) {

  int max = Math.max(
      Math.max(arr[i - 2], arr[i - 1]),
      Math.max(arr[i + 1], arr[i + 2])
  );

  ans += Math.max(0, arr[i] - max);
}

접근 포인트 요약

1. 현재 건물 기준 양옆 2칸씩 총 4개 건물을 비교한다.
2. 주변 건물의 최대 높이를 구한다.
3. 현재 건물이 더 높을 때만 차이만큼 조망권을 확보한다.
4. 배열 인덱스 범위를 고려하여 i = 2부터 i < n - 2까지 탐색한다.
5. 문제에서 테스트케이스 개수가 고정되어 있는지 확인한다.

핵심 교훈
2차원 공간을 다루는 문제라도 반드시 2차원 배열이 필요한 것은 아니다.
실제로 필요한 정보가 건물별 높이뿐이라면 1차원 배열로 단순화할 수 있다.