본문 바로가기
Algorithms/이코테

[Greedy] 이코테 - 곱하기 혹은 더하기(py)

by hi-rachel 2023. 7. 11.

문제

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요. 단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.

예를 들어 02984라는 문자열이 주어지면, 만들어질 수 있는 가장 큰 수는 ((((0+2)x9)x8)x4) = 576입니다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.

 

입력 조건

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

출력 조건

  • 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력합니다.
입력 예시 출력 예시
02984 576
567 210

풀이

아이디어

  • 두 수 중 하나라도 0 혹은 1인 경우, 곱하기보다는 더하기를 수행하는 것이 효율적이다. 다시 말해 두 수에 대하여 연산을 수행할 때, 두 수 중에서 하나라도 1 이하인 경우에는 더하며, 두 수가 모두 2이상인 경우에는 곱하면 된다.

- 내 풀이

# 문자열 입력받아 한 글자씩 숫자로 저장하기
s = list(input())
result = 1

# 숫자가 0, 1이 아니면 X 연산 실행 (0, 1이면 + 연산이 더 큰 값이 될 수 있기 때문)
# (단, 첫번째 경우에는 0이면 초기값 1로, 0이 아니면 첫번째값 그대로 설정해준다)
# else: + 연산 실행
for i, v in enumerate(s):
  i = int(i)
  v = int(v)
  if i == 0:
    if v != 0:
        result = v
    continue
  if v != 0 and v != 1:
    result *= v
  else:
    result += v

print(result)

 

- 답안

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)

 

내 풀이와 달리 바로 첫 번째 문자를 result에 대입시켜주고, range(1, len(data))로 두 번째 문자부터 num으로 설정해

num <= 1 or result <= 1

로 첫 번째 혹은 두 번째 수가 0이나 1일 때 조건을 설정해주었다.

 

풀이 아이디어는 비슷했지만 표현 방식이 달랐다. 답안처럼 바로 result에 첫 번째 문자를 넣어주고 두번째 문자와 함께 0, 1이 해당하지 않는지 파악하는 방식이 더 직관적이고 간단하다. 또한 굳이 list로 받아주지 않아도 문자열 순회 가능하다.

 


 

출처: 나동빈, 「이것이 취업을 위한 코딩테스트다 with 파이썬」, 한빛미디어, p.312