알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 11. 그리디 - Q2. 곱하기 혹은 더하기

  • 0
  • 0
0
0

1. 곱하기 혹은 더하기

  • 난이도
  • 풀이 시간
    • 30분
  • 시간 제한
    • 1초
  • 메모리 제한
    • 128 MB
  • 출처
    • Facebook 인터뷰

A. 문제

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

a. 예를 들면.

S = 02984 이면
만들 수 있는 가장 큰 수는 ((((0 + 2) * 9) * 8) * 4) = 576

b. 입력 조건
  • 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어진다
    • 1 <= S <= 20
    • 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다.
c. 출력 조건
  • 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력한다.
d. 테스트 케이스
  • 입력 예시

    
    02984
    
    
    
    567
    
    
  • 출력 예시

    
    576
    
    
    
    210
    
    

B. 내 답안


s = input()  
answer = 1  
for i in s:  
    if int(i) == 0:  
        answer += int(i)  
    else:  
        answer *= int(i)  
  
print(answer)  
  
# 5분 / non-pass

a. 회고

풀이

  • 현재 숫자가 0일 때, 곱하기를 하면 전체 수가 0이되기 때문에 더하기 연산을 해야 한다.

반성

  • 문제에 제시된 예제에 0이 있다고 0만 고려했다.
  • 사실 1이 들어오면 곱하는 것보다 더하는게 값이 늘어나는 방법일텐데..

결론

  • 문제에서 겉으로 나타나있지 않은 조건을 잘 찾을 수 있도록 연습을 많이 하자.

C. 문제 해설

특정한 두 수에 대하여 연산을 수행할 때, 대부분은 '+'보다는 'x'가 더 값을 크게 만든다. 하지만 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기를 수행하는 것이 효율적이다.

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

현재까지의 계산 결과를 result에 담은 상태로, 매 숫자에 대하여 연산을 수행하면 된다. 그래서 result가 1 이하이거나, 현재 처리하고 있는 숫자가 1 이하라면 더하기 연산을 수행하고, 그렇지 않은 경우 곱하기 연산을 수행하면 된다.

a. 책 답안

python-for-coding-test/2.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.