그리디 - 큰 수의 법칙(Swift)

 

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

 

문제

저작권 문제가 될 수 있어 문제는 삭제합니다. 

 

풀이 코드

입력	출력
5 8 3 2 4 5 4 6	46

 

예시 1) 

let arr = [2,4,5,4,6].sorted()
let n = 5 // 배열의 크기
let m = 8 // 최대 반복 횟수
let k = 3 // 연속으로 더할수 있는 횟수

let first = arr[n - 1] // 제일 큰 수 
let second = arr[n - 2] // 그다음 큰 수 

var result = 0
var count = 0
    
for i in 1...m { 
	if count == k {
		result += second
		count = 0
	} else {
		result += first
		count += 1
	}
}
print(result) // 46

// 시간 -> 0.0010700225830078125

 

예시 2)

입력	출력
5 7 2 3 4 3 4 3	28

let arr = [3,4,3,4,3].sorted()
let n = 5 // 배열의 크기
let m = 7 // 최대 반복 횟수
let k = 2 // 연속으로 더할수 있는 횟수

let first = arr[n - 1] // 제일 큰 수 
let second = arr[n - 2] // 그다음 큰 수 

var result = 0
var count = 0
    
for i in 1...m { 
	if count == k {
		result += second
		count = 0
	} else {
		result += first
		count += 1
	}
}
print(result) // 28
// 시간 -> 0.000885009765625

 

문제 풀이

1. 배열을 오름차순으로 정렬(제일 큰 수와 그다음 큰수를 찾기 쉽게)

2. n - 1 위치에 있는 수가 제일 큰 수 , n - 2 위치에 있는 수가 그다음 큰 수 

3. m 만큼 반복하면서 제일 큰수를 result 변수에 더하면서 count도 1씩 증가시킴 
 -. 단, count가 k와 같다면 연속으로 k번 반복되었으므로 그다음 작은 수를 더해줌 

※ 예시 1, 예시 2를 위 코드로 풀었을 경우에 M = 10000으로 반복했을경우에는 1초를 넘지 않지만 100억회 반복했을 경우 10분이 지나도 안끝남 

 

m = 100억으로 했을 때 풀이 코드 

예시 1) 수열이 m과 나눴을 때 나누어 떨어질 경우 

let arr = [2,4,5,4,6].sorted()
let n = 5 // 배열 크기
let m = 8 // 더하는 횟수
let k = 3 // 연속으로 더할 수 있는 횟수

let first = arr[n - 1] // 6
let second = arr[n - 2] // 5

var result = 0
var count = 0

// m = 8일때, 반복되는 수열 [6,6,6,5],[6,6,6,5]
// 6이 더해지는 횟수 6번
let firstCount = m / (k + 1) * k
// 나누어 떨어지지 않았을 때 큰수 더해지는 횟수 0번
let secondCount = m % (k + 1)

// 최종 큰 수 더하는 횟수 6번
let sumFirst = firstCount + secondCount

// 두번째로 큰 수 더하는 횟수 2번
let sumSeconde = m - sumFirst

// 제일 큰 수 더하기
result += sumFirst * first
// 두 번째로 큰 수 더하기 
result += sumSeconde * second

print(result) // 46

 

예시 2) 수열이 m과 나눴을 때 나누어 떨어지지 않을 경우 

let arr = [2,4,5,4,6].sorted()
let n = 5 // 배열 크기
let m = 7 // 더하는 총 횟수
let k = 2 // 연속으로 더할 수 있는 횟수

let first = arr[n - 1] // 6
let second = arr[n - 2] // 5

var result = 0
var count = 0

// m = 7 일때, 반복되는 수열 [6,6,5],[6,6,5],[6]

// 6이 더해지는 횟수 4번
let firstCount = m / (k + 1) * k

// 나누어 떨어지지 않았을 때 큰수 더해지는 횟수 1번
let secondCount = m % (k + 1)

// 최종 큰 수 더하는 횟수 5번
let sumFirst = firstCount + secondCount

// 두번째로 큰 수 더하는 횟수 2번
let sumSeconde = m - sumFirst

// 제일 큰 수 더하기
result += sumFirst * first
// 두 번째로 큰 수 더하기
result += sumSeconde * second

//print(result) // 40

 

m = 100억으로 했을 때 문제 풀이

※ 예시 1) 반복되는 수열 [6,6,6,5],[6,6,6,5] 
※ 예시 2) 반복되는 수열 [6,6,5],[6,6,5],[6]

1. m / (k + 1) * k 공식을 사용하여 제일 큰 수가 더해지는 횟수를 구한다.
 -. m / (k + 1)을 계산하면 반복되는 수열의 횟수가 나온다.
   → 예시 1) 2회
   → 예시 2) 2회
-. 여기에 제일 큰 수를 연속으로 더하는 횟수를 곱해주면 6이 반복되는 전체 횟수가 나온다. 
   → 예시 1) 6회
   → 예시 2) 4회
 -. 최종적으로 (반복횟수 / (제일 큰 수 연속으로 더하는 횟수 + 두번째 큰 수 더하는 횟수) * 제일 큰 수 연속으로 더하는 횟수) 공식 완성

※ m이 (k + 1)로 나누어 떨어지지 않았을 때에 나머지 수열에서 제일 큰 수가 더해지는 횟수를 구해야한다. 
2. m % (k + 1) 공식을 사용하여 나머지 수열에서 제일 큰 수가 더해지는 횟수를 구한다.
   → 예시 1) 0회 
   → 예시 2) 1회

3. m / (k + 1) * k 공식으로 계산한 값과 m % (k + 1) 공식으로 계산한 값을 더해주면 제일 큰 수가 더해지는 횟수를 구할 수 있다.
 -. let sumFirst = firstCount + secondCount

4. 그다음 총 반복 횟수와 제일 큰 수가 더해지는 횟수를 빼면 두번째 큰 수가 더해지는 횟수를 구할 수 있다.
 -. let sumSeconde = m - sumFirst

5. 최종적으로 제일 큰 수가 더해지는 횟수 * 제일 큰 수를 계산하고, 두번째 큰 수가 더해지는 횟수 * 두번째 큰수를 더하면 최종 결과값을 구할 수 있다.
 -. 제일 큰 수 → result += sumFirst * first
 -. 두번째로 큰 수 → result += sumSeconde * second

위 코드로 m = 100억번 했을 때 
최종 결과 값은 56666666667가 나오고  시간은 0.001067042350769043가 나오며 1초를 넘지 않는다.