이것이 코딩 테스트다

책으로 그리디 알고리즘 학습 후 백준 문제를 풀어보기로 하였다.

그리디 알고리즘

백준 1541번

import sys

expression = [num for num in sys.stdin.readline().rstrip('\n')]
li = []

if len(expression) == 1:
    print(int(expression[0]))
else:
    # replacing string for int
    while expression:
        j = 0
        term = 0
        while True:
            i = expression.pop()
            if i == '+' or i == '-':
                li.append(term)
                li.append(i)
                break
            term += pow(10, j) * int(i)
            j += 1
            if len(expression) == 0:
                li.append(term)
                break
    li.reverse()

    # input parenthesis
    newli = []
    data = 0
    for i in range(0, len(li), 2):
        data += li[i]
        if i >= len(li) - 1:
            newli.append(data)
            break
        if li[i + 1] == '-':
            newli.append(data)
            data = 0

    result = newli[0]
    for i in range(1, len(newli)):
        result -= newli[i]

    print(result)

그리고 공개된 좋은 답안

e = [sum(map(int, x.split('+'))) for x in input().split('-')]
print(e[0]-sum(e[1:]))

결과

현타가 오지 않을 수가 없었다. 문제를 푸는 것도 중요하지만 좋은 답안에서 활용한 파이썬 툴을 최대한 활용해야겠다.
우선 반복자 활용을 잘 못하는 것 같아서 이를 머리 속에 새겨 놓으려 한다.

백준 1789

import sys

n = int(sys.stdin.readline().rstrip('\n'))

li = []
i = 0

while True:
    i += 1
    tmp = (i*(i+1)/2)
    if tmp > n:
        print(i-1)
        break
    elif tmp == n:
        print(i)
        break

print(int(((int(input())*8+1)**.5-1)/2))

결과

비교적 쉬운 문제였으나, 점진적으로 올라가면서 반복하는 방법 외에 간단하게 근의 공식으로 풀 수 있던 상황임에도, 코딩스럽게 인위적으로 푸는 것에 치우쳐져서 다소 아쉬운 풀이를 했다.

백준 16953번

n, m = input().split()
n = int(n)
odd = ['3', '5', '7', '9']

cnt = 0
while True:
    if int(m) == n:
        print(cnt+1)
        break
    elif m[len(m)-1] in odd or int(m) < n:
        print(-1)
        break
    elif m[len(m)-1] == '1':
        m = int(m)
        m = (m-1)//10
        m = str(m)
        cnt += 1
    else:
        m = int(m)
        m //= 2
        m = str(m)
        cnt += 1

결과

len(m)-1 대신에 -1을 쓸 것, odd list를 만들기 보다는 else로 처리할 것.

구현

알고리즘을 소스코드로 구현하는 과정

데이터의 개수와 구현하려는 코드의 big-o complexity를 비교하여 요구하는 실행 시간을 맞춘다.