๐Ÿ™„ ๋ฐฑ์ค€ 11497 : ํ†ต๋‚˜๋ฌด ๊ฑด๋„ˆ๋›ฐ๊ธฐ

11497: ํ†ต๋‚˜๋ฌด ๊ฑด๋„ˆ๋›ฐ๊ธฐ

Greedy ๋ฌธ์ œ์ด๋‹ค.

์ด๋ฒˆ ๋ฌธ์ œ ์—ญ์‹œ ๊ฐ„๋‹จํ–ˆ๋‹ค.


๐Ÿ“Œ Try 1

from collections import deque

N = int(input())
for _ in range(N):
  num = int(input())
  inputArr = list(map(int, input().split()))
  inputArr.sort()
  sortedArr = deque()
  
  while inputArr:
      sortedArr.appendleft(inputArr.pop())
      if inputArr:
        sortedArr.append(inputArr.pop())

  _max = 0
  for i in range(num - 1):
    n = abs(sortedArr[i+1] - sortedArr[i])
    _max = max(_max, n)
  
  print(_max)

์ž…๋ ฅ ๋ฐ›๋Š” ์ˆ˜๋“ค์„ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌํ•˜๊ณ ,
deque์˜ append์™€ appendleft ๋ฉ”์†Œ๋“œ๋ฅผ ์ด์šฉํ•ด์„œ ์–‘์˜†์œผ๋กœ pushํ–ˆ๋‹ค.

๊ทผ๋ฐ ์ฝ”๋“œ๊ฐ€ ์ข€ ๋”๋Ÿฌ์›Œ์„œ ๊นจ๋—ํ•˜๊ฒŒ ์ •๋ฆฌํ•  ํ•„์š”๊ฐ€ ์žˆ์–ด๋ณด์ธ๋‹ค.


๐ŸŽฏ ๋‹ค๋ฅธ ๋ถ„ ์ฝ”๋“œ

T = int(input())

for i in range(T):
    N = int(input())
    trees = list(map(int, input().split()))
    trees.sort()
    result = 0
    for j in range(2, N):
        result = max(result, abs(trees[j] - trees[j - 2]))
    print(result)

๋‚˜๋ž‘ ๊ฐ™์€ ์ ‘๊ทผ์ด์ง€๋งŒ, ์ฝ”๋“œ๊ฐ€ ์ฐจ์›์ด ๋‹ค๋ฅด๋‹ค..

๋‚œ ์ž…๋ ฅ ๋ฐ›์€ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ •๋ ฌํ•ด์„œ ๋ฉ”๋ชจ๋ฆฌ ๋‚ญ๋น„์™€ ์‹œ๊ฐ„ ๋‚ญ๋น„๋ฅผ ํ–ˆ์ง€๋งŒ,
์ด๋ถ„์€ ์ •๋ ฌํ•˜์ง€ ์•Š๊ณ  index๋งŒ ์กฐ์ ˆํ•ด์„œ ์ฒ˜๋ฆฌํ–ˆ๋‹ค.. ์™€,,,


๐ŸŽ Reference

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ