[이취코] 알고리즘 유형별 기출문제: 그리디 - 2. 곱하기 혹은 더하기 (Python)

2. 곱하기 혹은 더하기

문제

• 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 ‘X’ 혹은 ‘+’ 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
• 단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정함.
• 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어짐

예시

• 02984라는 문자열이 주어지면, 만들어질 수 있는 가장 큰 수는 ((((0+2)*9)8)*4)=576임
• 567이 주어지면 가능한 가장 큰 수는 567=210임

입출력 조건

• 입력: 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어짐 (1 ≤ S의 길이 ≤ 20)
• 출력: 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력함

풀이

1) 첫 번째 접근

0과 1의 경우 더하기가, 2~9는 곱하기가 더 숫자가 커지는 길임

맨 첫번째 수로 결과값 초기화

왼쪽/오른쪽 수가 0/1이면 더하기, 아닌 경우는 모두 곱하기로 처리

= 현재 수와 다음 수 중 0/1이 있는지 확인하고 있으면 현재 수+다음 수, 아니면 현재 수*다음 수

S = input()
ans = int(S[0])
for i in range(len(S)-1):
    cur = int(S[i])
    next = int(S[i+1])
    if cur == 0 or cur == 1 or next == 0 or next == 1:
        ans += next
    else:
        ans *= next
print(ans)

 

실수한 점: cur가 0이어도 직전까지 계산한 값이 0/1이 아니라면 곱하는 것이 더 커지는 길임

즉, 0/1 검사 대상이 현재 원소와 다음 원소가 아니고 누적 계산 결과와 다음 원소라는 것

또 == 0 or == 1보다는 <= 1로 쓰는 것이 더 간단함

 

2) 두 번째 접근

누적 계산 결과와 다음 원소가 ≤1인지 검사

1번째 원소부터 끝까지 검사하면 되므로 S[1:]로 슬라이싱

시간 복잡도: O(n) - for loop

공간 복잡도: O(1) - 길이가 20 이하로 정해진 문자열 S, 결과 담는 정수 변수 ans

S = input()
ans = int(S[0])
for num in S[1:]:
	num = int(num)
	if num <= 1 or ans <= 1:
		ans += num
	else:
		ans *= num
print(ans)