[이코테] 3. 그리디 알고리즘 - 곱하기 혹은 더하기

그리디 알고리즘 - 곱하기 혹은 더하기

문제 설명

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요.

단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정합니다.

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

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

문제 해결 아이디어

두 수 중에서 하나라도 1 이하인 경우에는 더하며, 두 수가 모두 2 이상인 경우에는 곱하면 최적의 해.

정당성 분석

대부분의 경우 '+'보다는 'x'가 더 값을 크게 만듦.
- 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행하는것이 효율적.

소스 코드

data = input()
result = int(data[0])

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

print(result)

나는 맨처음에 단순히 input만 안쓰고 list(map(int, input())) 방법으로 list 객체로 받아야하는 줄 알았다.

왜냐면 for문 돌릴때 iterable한 데이터인 list로 받아야 쓸 수 있다고 생각했기 때문이다.

하지만, input으로 담은 data가 그냥 indexing이 되네..그리고 int로 감싸서 result에 저장하네..

그리고 나는 이번에도 이해가 안되서 손으로 코드를 따라가보았다..

22.12.12 복습

x = list(map(int, input())) #for문으로 돌릴거니까 iterable하게 저장해야겠지?(list)

result = 0

for i in x:
    print(i)					# 값 확인용
    if 0 <= i <= 1:
        result += i				# 0과 1사이는 곱하기 보다는 무조건 더해야 이득이니까
        print("0~1", result)			# 값 확인용
    elif result == 0:
        result += i				# 첫 시작이 0일 경우 일단 더해~!
    else:
        result *= i				# 나머지는 곱하는게 이득!
        print("2~9", result)			# 값 확인용
print(result)

첫 번째 기억할 점.

처음 배울 때 생각했던 것 처럼 input값을 list로 받아냈다.

~~나놈.. 생각이 안 변하는구나~~

다시 한번 복습하자면,

input으로 그냥 받으면 type이 str으로 저장되고 인덱싱으로 접근 가능하다.

다만 주의할 것은

int(input())으로 받으면 인덱싱 불가능.

TypeError: 'int' object is not subscriptable 발생.

두 번째 기억할 점.

내코드 틀렸다.

input으로 10345가 주어진다면?

내 코드 : 60

정답 코드 : 80

왜 틀렸을까?

result가 1일 경우 1x3보다 1+3이 더 값이 크다.

즉, i가 1인 것만 고려하는 것이 아니라 result가 1인 것도 고려했어야했다.

~~(result가 0인 것은 고려했음.)~~

이코테 2021 시리즈 씹어먹기 by 조랭이떡

시리즈 목차

코딩테스트 출제 경향 및 알고리즘 성능 평가
파이썬 문법 부수기
그리디
구현
DFS & BFS (추후링크)
정렬 알고리즘 (추후링크)
이진 탐색 (추후링크)
다이나믹 프로그래밍 (추후링크)
최단 경로 알고리즘 (추후링크)
기타 그래프 이론 (추후링크)
코딩 테스트에서 자주 출제되는 기타 알고리즘 (추후링크)
개발형 코딩 테스트 (추후링크)