[이코테] 그리디 기출문제 - 2. 곱하기 혹은 더하기

---

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다.

 

2023.12.06 - [Algorithm] - [이코테] 02. 그리디(Greedy) 알고리즘, 탐욕법, 욕심쟁이 알고리즘

[이코테] 02. 그리디(Greedy) 알고리즘, 탐욕법, 욕심쟁이 알고리즘

---

문제

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

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

 

입력 조건

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

출력 조건

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

 

입력 예시 1
02984

출력 예시 1
576

입력 예시 2
567

출력 예시 2
210

---

문제 분석 및 알고리즘 설계

0이 있으면, 양 옆의 수 중에서 더 큰수와 더하고, 나머지는 다 곱하기

1. S를 왼쪽부터 하나씩 확인한다.
2. 만약 0 이라면, 무시
3. 즉, 0을 제외한 모든 숫자를 곱한다.

---

나의 풀이

S = input()

result = int(S[0])
for i in S[1:]:
    i = int(i)
    if i <= 1 or result <= 1:
        result += i
    else:
        result *= i

print(result)

---

해설

일반적으로 두 수에 대한 연산을 할 때 +보다 x가 값을 더 크게 만든다.

하지만 두 수 중 하나라도 0 또는 1인 경우, 더하기를 수행하는 것이 효율적이다.

즉, 두 수에 대하여 연산을 수행할 때, 두 수중에서 하나라도 1 이하인 경우에는 더하며, 두 수가 모두 2 이상인 경우에는 곱하면 된다.

• 1에 대한 고려가 빠졌으므로, 추가한다.
• 1보다 작을 때, 최종 결과에 덧셈 연산을 수행한다.
  • result의 초기값을 1로 지정하면, 문자열의 첫 값이 1일 때 덧셈 연산이 수행되므로 오답이 나오고, 0으로 지정하면, 문자열의 첫 값이 0 또는 1이 아닐 때 곱셈 연산이 수행되므로 오답이 나온다.
  • 따라서 초기값을 문자열의 첫번째 값으로 설정하고, 문자열 순회를 2번째 값부터 시작한다.
  • 문자열의 첫번째 값이 0 또는 1일 경우를 고려하여 result <= 1일 때 덧셈 연산이 수행되도록 조건을 포함시킨다.

---