[BOJ] 백준 2036 수열의 점수 (Swift)

문제

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

2036번: 수열의 점수

풀이

• 1보다 큰 양수는 큰 양수끼리 곱하는 것이 가장 큰 값이 나올 것이다.
• 1은 더하는게 가장 큰 값이다. 1과 다른 수를 뽑아서 곱해봤자, (1 * x) = x 이기 때문
• 음수는 가장 작은 음수끼리 곱하는 것이 가장 큰 값이 나올 것임
• 0은 음수가 남았을 때, 음수랑 곱해주면 0으로 가장 큰 값이 나오게 될 것이다. 그 외에는 있으나 마나..?
• 그러므로 배열을 입력받고, 1보다큰 양수, 음수, 0 배열로 나눠주어서 계산하면 될 것이다.

소스코드

	let n = Int(readLine()!)!
	var nums: [Int] = []
	for _ in 0..<n { nums.append(Int(readLine()!)!) }
	// 1보다 큰 양수들을 오름차순으로 정렬 ex) [1, 4, 5, 6 ...]
	var positiveNums = nums.filter { $0 > 1 }.sorted(by: <)
	// 음수들을 내림차순으로 정렬 ex) [-1, -4, -5, -6 ...]
	var negativeNums = nums.filter { $0 < 0 }.sorted(by: >)
	// 0인 것의 갯수를 세어줌
	var zeros = nums.filter { $0 == 0 }
	// 1은 그냥 덧셈을 해줄 것이기 때문에 answer의 값을 초기화 할 때 사용하였음
	var answer = nums.filter { $0 == 1 }.count
	// 만약 1보다 큰 양수의 배열이 비어있지 않다면?
	while !positiveNums.isEmpty {
	// 1보다 큰 양수의 배열의 크기가 1이 아닐 때 까지, 가장 큰 값을 2개씩 뽑아서 무조건 곱해줄 것임
	// 만약 1보다 큰 양수의 배열의 요소가 1개만 남았다면 단순히 덧셈해주면 된다.
	if positiveNums.count != 1 {
	let a = positiveNums.removeLast()
	let b = positiveNums.removeLast()
	answer += a * b
	} else {
	answer += positiveNums.removeLast()
	}
	}
	// 음수의 배열이 비어있지 않다면?
	while !negativeNums.isEmpty {
	// 음수의 배열의 크기가 1이 아닐 때 까지, 가장 작은 값을 2개씩 뽑아서 무조건 곱해줄 것임
	if negativeNums.count != 1 {
	let a = negativeNums.removeLast()
	let b = negativeNums.removeLast()
	answer += a * b
	} else {
	// 음수의 배열의 요소가 1개이고, 만약 입력받은 배열 중에 0이 있다면?
	// 마지막 가장 작은 음수를 단순히 삭제해주면 된다. (0과 곱하면 되므로)
	// 하지만 입력받은 배열 중에 0이 없다면 가장 작은 음수 값을 더해주면 됨
	if zeros.isEmpty {
	answer += negativeNums.removeLast()
	} else {
	negativeNums.removeLast()
	}
	}
	}
	print(answer)

view raw 수열의 점수.swift hosted with ❤ by GitHub

후기

• 그리디 알고리즘 이라는 것을 판단하게 되면 쉽게 풀 수 있는 문제였다고 생각한다.
• 하지만 나는 최초에 0 요소를 생각하지 못해서 틀렸습니다를 받았었음..
• 다시 한 번 문제를 천천히 읽으면서 어떤 반례가 있을지 생각해보다 0의 존재를 깨닫고 풀게되었다.