wellcome_공부일기

문제3) 곱하기 혹은 더하기 본문

알고리즘/그리디 알고리즘(Greedy Algorithm)

문제3) 곱하기 혹은 더하기

ma_heroine 2021. 1. 25. 20:53

문제 3: 곱하기 혹은 더하기

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로

하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는

가장 큰 수를 구하는 프로그램을 작성하세요. 단, + 보다 x를 먼저 계산하는 일반적인 방식과는 달리,

모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.

 

예를 들어, 02984라는 문자열로 만들 수 있는 가장 큰 수는 ((((0 + 2)x 9)x 8)x 4) = 576입니다.

또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.

 

* 문제 조건

난이도:하  풀이시간:30분  시간제한:1초  기출:페이스북 인터뷰

입력조건- 첫째 줄에 여러개의 숫자로 구성된 하나의 문자열 S가 주어집니다.(1<=S의 길이 <=20)

출력조건- 첫째 줄에 만들어 질 수 있는 가장 큰 수를 출력합니다.

1) 입력예시: 02984

   출력예시: 576

2) 입력예시 567

    출력예시 210

 

 


 

내가 코드 작성 시 사용할려 했던 라이브러리 및 메소드 정리

- 문자열은 index로 assign할 수 없다.

str' object does not support item assignment

 

- 문자열 내 연산자 계산 가능 메소드

eval()
result = eval('(3+5)*7')
print(result) # 56

- 리스트 내 item들을 하나의 문자열로 만들어주는 메소드 

list = ['a', 'b', 'c'] 
print(''.join(list)) # print: abc

- 리스트에 item 추가 시, 위치 선정이 가능토록하는 메소드

# list = ['a', 'b', 'c'] 
list.insert(0, "new")
print(list) # ['new', 'a', 'b', 'c'] 

내가 작성한 코드

같은 조건을 겹쳐서 사용한 경우가 많아서 효율적으로 보이진 않는다.

s = str(input())

import time
start_time = time.time() # 측정 시작

element = []

for i in s:
    element.append(i)
    if i != s[-1]:
        element.insert(0, '(')
        if i == '0' or i == '1':
            if i != s[0]:
                element.append(')')
            element.append('+')
        else:
            if i != s[0]:
                element.append(')')
            element.append('*')
    else:
        element.append(')')

print(element)
result = ''.join(element)
print(result)
print(eval(result))

end_time = time.time() # 측정 종료
print('---- %f seconds(time) ----' % (end_time - start_time)) # 수행 시간 출력

#####################################output#######################################
# 012356
# ['(', '(', '(', '(', '(', '0', '+', '1', ')', '+', '2', ')', '*', '3', ')', '*', '5', ')', '*', '6', ')']
# (((((0+1)+2)*3)*5)*6)
# 270
# ---- 0.000195 seconds(time) ----

 


 

 

문제해결 아이디어

대부분의 경우 + 보다는 x가 더 값을 크게 만듭니다.

- 예를 들어 5 + 6 = 11이고, 5 x 6 = 30입니다.

다만 두 수 중에서 하나라도 '0' 혹은 '1'경우, 곱하기보다는 더하기를 수행하는 것이 효율적입니다.

따라서 두 수에 대하여 연산을 수행할 때, 두 수 중에서 하나라도 1이하인 경우에는 더하며,

두 수가 모두 2 이상인 경우에는 곱하면 정답입니다.

 

 

나동빈님 코드

나는 정말 길게 작성했는데, 스트링을 정수형으로 바꿔서 바로바로 계산을 실행해주는 걸 기억해야겠다. 

data = input()

# 첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)):
    # 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
    num = int(data[i])
    if num <= 1 or result <= 1:
        result += num
    else: result *= num

print(result)

 

 

 

 

 

Comments