[그리디] 02 곱하기 혹은 더하기

02 곱하기 혹은 더하기

그리디란?

• 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘이다.
• 정확한 답을 도출하지 못할 수도 있지만 코딩테스트에서는 대부분 ‘최적의 해’를 찾는 문제가 출제되므로 그리디 알고리즘의 정당성을 고민하면서 문제 해결 방안을 떠올려야한다.
• 다양한 그리디 알고리즘
  • 다익스트라 최단 경로 알고리즘
    • 암기가 필요한 알고리즘이다. 팀 노트 필요!
    • 특정 노드까지의 최단 거리 계산한 다음 메모리에 저장하고 나중에 필요할 때 다시 꺼내 본다는 점에서 다이나믹 프로그래밍으로 분류하기도 한다.
  • 크루스칼 알고리즘
    • 우선순위 큐 (최소 힙, 최대 힙)
    • 여러 개의 값들 중 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

---

문제

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

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

입력 조건

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

출력 조건

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

입력 예시

02984

출력 예시

567

---

사고 과정

• 합이 선행되어야 더 큰 수를 곱할 수 있다 ⇒ 정렬
• 가장 큰 수를 구하는 것이므로 큰 수를 x를 하면 가장 큰 수가 나온다.
• 단, 0과 1이 나오면 더해준다. 또한 이전 합이 0 또는 1이어도 더해준다.

---

풀이

나의 코드

# 02 곱하기 혹은 더하기.py

# 문자열 입력받고 정수형 리스트로 만들기
s = list(map(int, input()))  # ['0', '2', '9', '8', '4']

result = 0  # 연산 결과

# 합을 먼저해야 큰 곱셈 연산을 할 수 있다.
s.sort()

# 0 또는 1이 나오거나 이전 결과가 0 또는 1이면 더하고, 그렇지 않으면 곱한다.
for i in s:
	# if i in [0, 1] or result in [0, 1]:
  if i <= 1 or result <= 1:
    result += i
  else:
    result *= i

print(result)

---

💡사고 과정 흐름을 공식화하자

• list(’문자열’) ⇒ 문자열을 문자 리스트로 쪼갤 수 있다.
• 연산을 통해 가장 큰 수를 만들기

  • 합이 선행되어야 이후에 큰 곱셈 연산을 할 수 있다 ⇒ 정렬

      s.sort()
    

      s.sort()
    

  • 0 또는 1이 나오거나 이전 결과가 0 또는 1이면 더하고, 그렇지 않으면 곱한다.