[python] 백준 2529 - 부등호

출처 : 백준, https://www.acmicpc.net/problem/2529

2529번: 부등호

 

 

풀이

 

def drawLine(ineq_arr, target_arr):
  n = len(ineq_arr)
  
  if ineq_arr[n-1] == '>':
    target_arr[n] = 'B'
  else:
    target_arr[n] = 'R'

  prev = ''

  for i in range(n):
    if prev != ineq_arr[i]:
      if ineq_arr[i] == '<': # ><
        target_arr[i] = 'B'
      else:
        target_arr[i] = 'R'

    prev = ineq_arr[i]

def setNumber(target_arr, min_max):
  if min_max == 'max':
    num_set = [str(i) for i in range(9, 9-n-1, -1)]
    startLine = 'B'
    stopLine = 'R'
  else:
    num_set = [str(i) for i in range(n+1)]
    startLine = 'R'
    stopLine = 'B'

  i = n
  while num_set and i >= 0:
    if target_arr[i] == startLine:
      target_arr[i] = num_set.pop()
      
      index = i + 1
      while -1 < index <= n :
        if target_arr[index] == stopLine:
          target_arr[index] = num_set.pop()
          break
          
        target_arr[index] = num_set.pop()
        index += 1
      
      index = i - 1
      while -1 < index <= n and target_arr[index] != stopLine:
        target_arr[index] = num_set.pop()
        index -= 1

    i -= 1

  if num_set:
    target_arr[0] = num_set.pop()

  print(''.join(target_arr))


if __name__ == '__main__':
  n = int(input())
  ineq_arr = input().split()
  min_arr = [0] * (n+1)
  max_arr = [0] * (n+1)

  drawLine(ineq_arr, max_arr)
  drawLine(ineq_arr, min_arr)
  setNumber(max_arr, 'max')
  setNumber(min_arr, 'min')

 

완전 생각한데로 작성한 코드인데,

 

><와 같이 주위에서 가장 작은 부분에는 파란선을, <>와 같이 주위에서 가장 큰 부분은 빨간선을 그어준다.

(양 끝도 구분해서 표시)

 

 

가장 큰 수의 경우

 

 

1. 오른쪽에서 올라오면서

2. 파란선에서 시작해서 작은 수부터 소모하며 숫자를 적는다.

3. 파란선에서 오른쪽으로 이동하며 배치한다. 빨간선에 닿으면 닿은 자리까지 숫자 배치

4. 다시 파란선에서 왼쪽으로 이동하며 숫자를 배치한다. 빨간선에 닿으면 닿기 전까지만 배치

5. 남은 자리 채워준다.

 

가장 작은 수의 경우

 

 

1. 오른쪽으로 올라오면서 

2. 빨간선에서 시작해서 큰 수부터 소모하며 숫자를 적는다.

3. 빨간선에서 오른쪽으로 이동하며 배치한다 파란선에 닿으면 닿은 자리까지 숫자 배치

4. 다시 빨간선에서 왼쪽으로 이동하며 숫자를 배치한다. 파란선에 닿으면 닿기 전까지만 배치

5. 남은 자리 채워준다.

 

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

계속 교체하는 풀이

 

def setNumber(ineq_arr, num_arr):
  while True:
    count = 0
    for index in range(n):
      if ineq_arr[index] == '<':
        if num_arr[index] > num_arr[index + 1]:
          count += 1
          num_arr[index], num_arr[index + 1] = num_arr[index + 1], num_arr[index]
      else:
        if num_arr[index] < num_arr[index + 1]:
          count += 1
          num_arr[index], num_arr[index + 1] = num_arr[index + 1], num_arr[index]

    if count == 0:
      return

if __name__ == '__main__':
  n = int(input())
  ineq_arr = input().split()
  
  min_arr = [str(i) for i in range(n+1)]
  max_arr = [str(i) for i in range(9, 9-n-1, -1)]

  setNumber(ineq_arr, min_arr)
  setNumber(ineq_arr, max_arr)

  print(''.join(max_arr))
  print(''.join(min_arr))

 

가장 작은 경우와 가장 큰 경우를 세팅해놓고, 부등호에 맞을 때까지 계속 교체하는 풀이이다.

들으면 무식해보이는데 걸리는 시간은 위 풀이보다 이게 더 짧다.

 

 

고찰

 

사람들 똑똑하다.