[백준 2879번 / Python] 코딩은 예쁘게

[문제]

https://www.acmicpc.net/problem/2879

2879번: 코딩은 예쁘게

[분류]

그리디로 분류돼있긴 한데 잘 모르겠음.

다른 사람들도 의견이 갈림

 

[구현 논리]

우선 양수 음수 분류. 

조금만 고민해보면 왜 분류해야 하는지 이해할 수 있음.

1) 양수일 때

모든 원소값이 0이 될때까지 리스트의 최솟값을 반복해서 빼주기

2) 음수일 때

양수로 바꿔서 처리

위를 따로 함수(재귀함수)를 만들고

for문을 통해 양수일때와 음수일때 나눠서 처리

 

[코드]

def tab(lis): 
  if len(lis) == 0: 
    return 0 

  listt = [] 

  for num in lis: 
    if num > 0: 
      listt.append(num) 
    else: 
      listt.append(-num) 
   
  newlist = [] 
  m = min(listt) 
  cnt = 0 
  cnt += m 
  for num in listt: 
    n = num - m 
    if n != 0: 
      newlist.append(n) 
    else: 
      cnt += tab(newlist) 
      del newlist[:] 
   
  if len(newlist) != 0: 
    cnt += tab(newlist) 

  return cnt 

N = int(input()) 
data1=list(map(int,input().split())) 
data2=list(map(int,input().split())) 
data = [] 

for i in range(N): 
  data.append(data2[i] - data1[i]) 

cnt = 0 
seplis = [] 
seplis.append(data[0]) 
for i in range(1, N): 
  if data[i] * data[i-1] < 0: 
    cnt += tab(seplis) 
    del seplis[:] 
    seplis.append(data[i]) 
  else: 
    seplis.append(data[i]) 

cnt += tab(seplis) 

print(cnt)

 

<복잡도 분석>

tab(lis) 시간복잡도 : O(len(lis)) , 호출 횟수 : O(len(lis))

인데, 서로 종속관계이므로 한번에 고려하여 분석해야함.

tab(lis) 총 시간복잡도(재귀호출까지 다 마쳤을 때) : O(len(lis))

∴ 총 시간복잡도 O(N)

 

<고수의 코드>

import sys;input=lambda:sys.stdin.readline().strip() 
n=int(input()) 
p=list(map(int,input().split())) 
t=list(map(int,input().split())) 
ans=abs(p[0]-t[0]) 
for i in range(1,n): 
    bef=p[i-1]-t[i-1] 
    now=p[i]-t[i] 
    if bef*now>=0: 
        if abs(bef)<abs(now):ans+=abs(now)-abs(bef) 
    else:ans+=abs(now) 
print(ans)

 

메모리도 최소이고, 시간복잡도도 O(N)이며 코드도 매우 간결하고 가독성있음.

배우자 ... 이런 코드 쓸 수 있을 때까지 노력하자 ..

화이팅