[백준 9489번] 2xn 타일링

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

9489번: 사촌

 

접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

증가하는 정수 수열을 이용해서 트리를 만든다.

• 첫 번째 정수는 트리의 루트 노드이다.
• 다음에 등장하는 연속된 수의 집합은 루트의 자식을 나타낸다. 이 집합에 포함되는 수의 첫 번째 수는 항상 루트 노드+1보다 크다.
• 그 다음부터는 모든 연속된 수의 집합은 아직 자식이 없는 노드의 자식이 된다. 그러한 노드가 여러 가지 인 경우에는 가장 작은 수를 가지는 노드의 자식이 된다.
• 집합은 수가 연속하지 않는 곳에서 구분된다.

두 노드의 부모는 다르지만, 두 부모가 형제(sibling)일 때 두 노드를 사촌이라고 한다.

수열 특정 노드 번호 k가 주어졌을 때, k의 사촌의 수를 구하는 프로그램을 작성하시오.

 

2. 나의 방식대로 문제를 재정의 하자.

수열이 주어지는데, 연속된 숫자는 같은 부모를 가지는 규칙을 가진다.

예를들어, 1 3 4 5 8 9 15 30 31 32이 주어졌을 때,

1

3 4 5

8 9

15

30 31 32

이렇게 같은 부모를 가진 하나의 집합이라고 생각할 수 있다.

이때, 조부모는 같지만, 부모가 다른 노드들을 사촌이라고 할 수 있다.

 

 

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

Integer[] parent를 생성하여, 각 노드가 어떤 집합에 속하는지 번호를 저장한다.

예를들어 위의 예시에서는 아래 표와 같은 parent 값을 가진다.

노드	집합
1	0
3 4 5	1
8 9	2
15	3
30 31 32	4

집합의 값은 노드의 index값과 같으므로, 같은 조부모를 가지고 다른 부모를 가진 노드를 구하기 위해서는

if (parent[i] != parent[kIndex] && parent[parent[i]] == parent[parent[kIndex]]) {
	result++;
}

다음과 같은 연산을 수행한다.

 

 

4. 어떻게 계산할 것인가?

1) 입력

BufferedReader

StringTokenizer

 

2) 시간 복잡도 계산

O(n)

 

 

5. 주의할 점은 무엇인가?

조부모를 구하는 연산에서 루트가 부모일 경우같은 특수한 경우 고려하기

 

 

6. 풀이 과정

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

public class q9489 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    while (true) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      Integer n = Integer.parseInt(st.nextToken()); // 노드 갯수
      Integer k = Integer.parseInt(st.nextToken()); // 계산할 K

      if (n == 0 && k == 0) {
        break;
      }

      Integer kIndex = 0;
      Integer[] parent = new Integer[n + 1];
      Integer[] ary = new Integer[n + 1];
      parent[0] = -1;
      ary[0] = -1;

      st = new StringTokenizer(br.readLine());
      for (int i = 1; i <= n; i++) {
        ary[i] = Integer.parseInt(st.nextToken());
        if (ary[i].equals(k)) {
          kIndex = i;
        }
      }

      Integer parents = -1;
      for (int i = 1; i <= n; i++) {
        if (ary[i] - ary[i - 1] > 1) { // 사촌
          parent[i] = ++parents;
        } else { // 형제
          parent[i] = parents;
        }
      }

      Integer result = 0;

      for (int i = 1; i <= n; i++) {
        if (parent[i] != parent[kIndex] && parent[parent[i]] == parent[parent[kIndex]]) {
          result++;
        }
      }

      System.out.println(result);
    }
    

    br.close();
  }

}

 

 

7. 개선점