[Swift/Python] 백준 BOJ - 1744 수 묶기

Github

GitHub - jeongju9216/Algorithm: Swift/Python 알고리즘

 

문제 링크

https://www.acmicpc.net/problem/1744

 

풀이

그리디 문제로 다양한 예외가 존재했던 문제입니다.

질문 게시판의 테스트케이스 모음을 참고하며 해결했습니다. (https://bingorithm.tistory.com/3)

 

1. 자연수 배열과 음수, 0 배열을 따로 만들어 입력받습니다.
2. 자연수는 내림차순, 음수,0 배열은 오름차순으로 정렬합니다.
3. 연산 결과를 담을 배열을 정의합니다.
4. 곱 연산이 합 연산보다 큰 경우에는 곱한 결과를 배열에 저장합니다.
5. 합 연산이 큰 경우 arr[i]를 저장합니다. (합 연산을 하기 위함)
6. 마지막에 연산 결과 배열을 합해서 출력합니다.

아래는 놓치기 쉬운 케이스인 듯 합니다.

1. 양수의 덧셈이 곱셈보다 큰 케이스
2. 음수 케이스
3. 음수와 0이 존재하는 케이스

1번은 1, 1, 1, 1, 1처럼 1만 입력이 주어지는 경우입니다.

단순히 곱셈만 하도록 코드를 짰다면 위 케이스에서 실패합니다.

 

2번은 음수 케이스입니다.

-1, -2, -3, -4, -5 가 주어졌다면 25가 답이 되어야 합니다.

모든 수를 하나의 배열에 입력 받아 내림차순으로 정렬하여 처리했다면 위 케이스에서 실패합니다.

 

3번은 음수와 0이 존재하는 케이스입니다.

-3, -2, -1, 0이라면 6이 답입니다.

음수와 0이 함께했을 때 둘을 곱해서 합을 최대로 해야 합니다.

 

Swift 코드

import Foundation

let n = Int(readLine()!)!
var plus: [Int] = [], minus: [Int] = []
for _ in 0..<n {
    let input = Int(readLine()!)!
    if input > 0 {
        plus.append(input)
    } else {
        minus.append(input)
    }
}

plus.sort(by: >)
minus.sort(by: <)

var result: [Int] = []
var i = 0
while i < plus.count {
    if i == plus.count - 1 {
        result.append(plus[i])
        break
    }
    
    if plus[i] * plus[i+1] > plus[i] + plus[i+1] {
        result.append(plus[i] * plus[i+1])
        i += 2
    } else {
        result.append(plus[i])
        i += 1
    }
}

i = 0
while i < minus.count {
    if i == minus.count - 1 {
        result.append(minus[i])
        break
    }
   
    if minus[i] * minus[i+1] > minus[i] + minus[i+1] {
        result.append(minus[i] * minus[i+1])
        i += 2
    } else {
        result.append(minus[i])
        i += 1
    }
}

print(result.reduce(0, +))

Python 코드

import sys; readLine = sys.stdin.readline

n = int(readLine())
nums = [int(readLine().rstrip()) for _ in range(n)]

plus = []; minus = []
for num in nums:
  if num > 0:
    plus.append(num)
  else:
    minus.append(num)

plus.sort(reverse=True)
minus.sort()

result = []

i = 0
while i < len(plus):
  if i == len(plus) - 1:
    result.append(plus[i])
    break

  if plus[i] * plus[i+1] > plus[i] + plus[i+1]:
    result.append(plus[i] * plus[i+1])
    i += 2
  else:
    result.append(plus[i])
    i += 1

i = 0
while i < len(minus):
  if i == len(minus) - 1:
    result.append(minus[i])
    break

  if minus[i] * minus[i+1] > minus[i] + minus[i+1]:
    result.append(minus[i] * minus[i+1])
    i += 2
  else:
    result.append(minus[i])
    i += 1

print(sum(result))

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.

 

Swift, 스위프트, 파이썬, Python, 알고리즘, 백준, BOJ