[백준/24729] 심각한 계단 중독입니다 (Python)

Problem : https://www.acmicpc.net/problem/24729

24729번: 심각한 계단 중독입니다

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:25:44

 

---

 

문제 설명

 

병철이는 다이어트를 위해 매일 계단을 오른다. 너무 많은 계단을 오르다 보니, 주변의 모든 사물이 계단형이 아니면 불편함을 느끼게 되었다!

그러다 보니 알고리즘 문제를 풀 때도 이런 문제나 저런 문제가 아니면 불편함을 느끼게 되었고, 이 심각한 계단 중독이 점점 악화되어가자 아예 입력 데이터가 계단이 아니면 불편함을 느끼게 되었다!

결국, 병철이는 백준을 해킹하여 모든 데이터를 계단 수로 만들려고 결심하였다.

여기서 계단 수란, 어떤 수의 앞과 뒤에 있는 수가 그 수와 1 차이가 나는 수열을 말한다. 즉, 1-2-3-4-5 같은 수열이나 1-2-3-2-3 같은 수열을 계단 수라고 한다.

하지만 병철이는 여기서 만족하지 않고, 기존 계단 수에 조건을 추가해 본인만의 계단 수를 정의하려고 한다.

병철이의 계단 수란, 기존에 계단 수의 조건을 만족하며 맨 앞의 수와 맨 뒤의 수까지 1 차이가 나는 것을 말한다. 즉, 
1-2-3-2-3-2 같은 수열이 병철이의 계단 수라고 할 수 있다.

물론 순서를 조정해서 병철이의 계단 수를 만들 수 있는 문제는 얼마 없기 때문에, 병철이는 이 조건을 만족하는 데이터만 찾으려고 한다. 어떤 데이터가 주어질 때, 이 데이터의 순서를 조정하여 병철이의 계단 수를 만들 수 있는지 알아보자.

 

입력 및 출력

 

입력

 

첫 줄에는 데이터의 크기 N이 주어진다. (1 <= N <= 50,000)

두 번째 줄에는 데이터에 포함된 값인 a_0, a_1, ... a_N-1이 주어진다. (1 <= a_i <=100,000) 

 

출력

 

병철이의 계단 수를 만들 수 있다면 1을, 없다면 -1을 출력한다.

 

입력 예시

 

4
1 2 2 1

 

출력 예시

 

1

 

 

---

 

풀이

 

우선, 전제조건상 N이 짝수일 때만 성립이 가능하다.

 

또한 이 계단수의 특징은, 회전하여도 계단수임이 성립한다. 즉 우리는 시작 숫자를 임의로 잡을 수 있다. 풀이의 편의성을 위해 min값을 시작 숫자로 잡자.

 

이제 이 계단수의 특징을 살펴보자.

• 주어진 수에는 min값과 max값이 존재하며, 이 계단수는 min값 - max값으로의 상승 구간, max값 - min+1값으로의 하강 구간이 반드시 존재해야 한다.
  • 즉 min - max 값은 최소 1개 이상, (min, max) 값은 최소 2개 이상이 필요하다.
• 그리고 남은 수는 크기가 1 차이인 pair로 나타낼 수 있어야 한다.
  • 예를 들어, (k, k-1) pair가 존재한다고 가정하자. 위에서 나타낸 필수 구간에는 min, min+1, ... , k, ... , max값이 포함된다.
  • 여기에 위 pair를 넣는다면 k, k-1, k, ..., max로 계단수의 정의를 해치지 않고 pair를 삽입할 수 있다.
  • 만약 모든 pair를 만들었을 때 남은 수가 존재한다면 불가능한 경우이다.

 

 

풀이 코드

from collections import Counter 
import sys
input = sys.stdin.readline

N = int(input())
nums = list(map(int, input().split()))

def is_enable() :
  if N % 2 :
    return False
  counter = Counter(nums)
  cnt = N
  minval = min(counter.keys())
  maxval = max(counter.keys())
  counter[minval] -= 1
  counter[maxval] -= 1
  
  for i in range(minval+1, maxval) :
    if counter[i] < 2 :
      return False
    counter[i] -= 2
  cnt -= (maxval - minval) * 2

  for i in range(minval, maxval) :
    if not counter[i] :
      continue
    if counter[i] > counter[i+1] :
      return False
    counter[i+1] -= counter[i]
    cnt -= counter[i] * 2
    counter[i] = 0
  return cnt == 0
print(1 if is_enable() else -1)

풀이 완료!