다음에 등장하는 연속된 수의 집합은 루트의 자식을 나타냅니다. 이 집합에 포함되는 수의 첫 번째 수는 항상 루트 노드+1보다 큽니다.
그다음부터는 모든 연속된 수의 집합은 아직 자식이 없는 노드의 자식이 됩니다. 그러한 노드가 여러 가지인 경우에는 가장 작은 수를 가지는 노드의 자식이 됩니다.
집합은 수가 연속하지 않는 곳에서 구분됩니다.
예를 들어서, 1 3 4 5 8 9 11 이라는 증가 수열이 주어지면, 집합은 1 | 3 4 5 | 8 9 | 11 같은 식으로 구분되고, 루트는 1이 되며, 자식은 3 4 5가 됩니다. 그리고 8 9는 3의 자식이, 11은 4의 자식이 됩니다.
두 노드의 부모가 다르지만, 두 부모가 형제일 때, 두 노드를 사촌이라고 합니다.
특정한 노드 번호가 주어졌을 때, 그 노드의 사촌의 수를 구하는 프로그램을 작성하세요.
입력 형식
첫 번째 줄에 노드의 수n과 사촌을 구해야 하는 노드의 번호k가 주어집니다.
두 번째 줄에 총n개의 수열의 원소가 주어지며, 모든 수는 1보다 크거나 같고, 1,000,000보다 작거나 같습니다.
입력으로 주어지는 수열은 항상 증가하며k는 항상 수열에 포함되어있는 수입니다.
1 ≤n≤ 1,000
1 ≤k≤ 1,000,000
출력 형식
첫 번째 줄에k의 사촌의 수를 출력합니다.
입출력 예제
예제1
입력:
10 15 1 3 4 5 8 9 15 30 31 32
출력:
5
포인트는 부모의 노드 번호는 다르지만 부모의 부모 노드 번호가 동일하면 서로 사촌이다.
1. 규칙에 맞추어 노드별 부모 노드의 번호를 결정한다
-> 연속되는거
2. 사촌의 정의를 잘 내린다.
1, 3, 4, 5, 8, 9, 15, 30, 31, 32 노드들은
0, 0, 1, 1, 1, 2, 2, 3, 4, 4, 4 부모 노드 index 번호로 매핑된다.
import sys
if __name__=="__main__":
# 변수 선언 및 입력:
n, k = tuple(map(int, input().split()))
par = [0] * (n + 1)
ans = 0
target_node_index = 0
nodes = [0] + list(map(int, input().split()))
for index in range(1, n + 1):
if nodes[index] == k:
target_node_index = index
# n개의 원소를 바탕으로 트리를 만들어줍니다.
parent_node = 0
for index in range(2, n + 1):
if nodes[index] > nodes[index-1] + 1:
parent_node += 1
par[index] = parent_node
for cur_node in range(1, n + 1):
# cur_node의 부모의 부모 노드가 존재하지 않는 경우에는 패스
if not par[par[cur_node]] or not par[par[target_node_index]]:
continue
# 부모 노드는 다르면서 and 부모의 부모 노드가 같은 경우를 찾습니다.
if par[cur_node] != par[target_node_index] and par[par[cur_node]] == par[par[target_node_index]]:
ans += 1 # 해당 노드들은 사촌이 됩니다.
# 사촌 노드의 개수를 출력합니다.
print(ans)
