[백준] 1449. 수리공 항승

링크

Python Tip!

• map(int, input().split())을 통해 int 변환을 한 줄로 깔끔히 처리 해줄 수 있다. 이를 이용해 list로 바로 만들어 줄수도 있음.

• print('f{variable}') 구문을 통해 JS의 백틱과 같은 효과를 줄 수 있다.

Greedy 문제로, 풀이1은 처음 풀이 시에 길이를 일일이 계산 해 주느라 복잡하게 짰다. 풀이2는 풀이 영상 참고하여 작성했다. 최대 입력 길이인 1001에 해당하는 값을 미리 만들어놓고 반복해 O(N)의 시간복잡도를 가진다. 1억 이상의 입력 길이 시에는 다른 방식을 택하는 게 좋을 듯하다.

풀이 1

K, L = map(int, input().split())
holes = list(map(int, input().split()))
holes.sort()

stack = [] # 구멍 stack
n = 0 # 테이프 갯수
need = 0 # 현재 이어지는 길이
start = holes[0]
for i in holes:
  print(f'start = {start}, i = {i}, 길이 = {L}')
  if stack:
    if start + L > i and start - L < i:
      stack.append(i)
      need += 1
    else:
      stack.clear()
      stack.append(i)
      start = i
      need = 1
      n += 1
  else:
    stack.append(i)
    start = i
    need += 1
  
  if need == L:
    stack.clear()
    need = 0;
    n += 1
  
if stack: 
  n += 1
print(n)

풀이 2

K, L = map(int, input().split())

coord = [False] * 1001
for i in map(int, input().split()):
  coord[i] = True

ans = 0   
x = 0
while x < 1001:
  if coord[x]:
    ans += 1
    x += L
  else:
    x += 1