[백준 2879번] 코딩은 예쁘게 (Python/파이썬)

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

2879번: 코딩은 예쁘게

최소 횟수로 현재 탭 개수에서 맞춰야하는 탭 개수로 바꾸라는 그리디 알고리즘 문제이다.

그리디 알고리즘이라는게 특별한 알고리즘이 있는게 아니라 그냥 어떻게 하면 최적의 경로로 문제를 해결할까? 생각하고 구현하는 문제이다. 

방법은 간단하다. 현재 위치에서 탭을 줄여야한다면, 양옆까지 확인해서 줄여야하는 탭은 같이 줄여준다. 대신 줄이는 횟수가 다를수 있으므로 줄여야하는 탭 중에서 가장 적은 횟수를 줄이면 된다.

그리고 차이배열은 diff의 모든 원소가 0이 될때까지 위의 방법으로 탭을 줄이든 늘리든 하면 된다.이 문제를 푸는 내 백준티어는 골드4인데, 진짜 지금까지 작성했던 코드중에 제일 못짰다.(나중에 내가 이 포스팅을 돌아보면 많이 반성할듯...)코드는 다음과 같다.

 

 

import sys
input = sys.stdin.readline
num_of_lines = int(input())
now_tab = list(map(int,input().split()))
correct_tab = list(map(int,input().split()))
cnt = 0

## 얼마나 줄이고 늘려야하는지 차이 배열 생성
diff = []
for i in range(num_of_lines):
  diff.append(correct_tab[i] - now_tab[i])

## 줄이는 경우, 늘리는 경우 따로 배열 생성
check = False
pos = []
neg = []

## diff배열이 모두 0이 될때까지 계속 반복하기
while check == False:
  check_repeat = [False] * num_of_lines
  for i in range(num_of_lines):
    if check_repeat[i]:
      continue
    start = i
    if diff[i] > 0:
      while i < num_of_lines and diff[i] > 0:
        check_repeat[i] = True
        pos.append(diff[i])
        end = i
        i += 1
      tmp = min(pos)
      for j in range(start,end+1):
        diff[j] = diff[j] - tmp
      pos = []

    elif diff[i] < 0:
      while i < num_of_lines and diff[i] < 0:
        check_repeat[i] = True
        neg.append(diff[i])
        end = i
        i += 1
      tmp = abs(max(neg))
      for j in range(start,end+1):
        diff[j] = diff[j] + (tmp)
      neg = []
    else:
      continue
    cnt += tmp

  check = True
  for i in range(num_of_lines):
    if diff[i] != 0:
      check = False
print(cnt)

 

 

시간은 48ms로 파이썬 기준 꽤 빠르게 나왔지만 코드가 너무 지저분하다.

탭을 줄이는 것과 늘리는 것은 구분해야하지만 예를 들어 5 -> 2 옆에 바로 5 -> 3 이 있다면 그냥 최소 개수인 2개의 탭을 줄이는 것이 아니라 앞에 것부터 5 -> 2를 그대로 줄여서 차이를 0으로 만들어도 된다.

최소(2칸)로 줄이면 어차피 다시 반복할때 와서 한칸을 더 밀어줘야하는데, 애초부터 3칸을 줄이면 5 -> 2 다음차례가 5 -> 3인데 5 -> 3은 3칸이 줄여졌으니까 2 -> 3이 되있을 것이다. 어차피 똑같이 한칸 밀어줘야하기 때문에 줄여야하는 횟수는 똑같다. 

위의 방법처럼 하면 한번의 for문을 돌면서 다 0으로 만들수 있는데...좀더 고민해볼껄 하는 아쉬움이 남는다.