swift ) 백준 2981 검문 - 시간초과 극복!!!!!!!!!!!!!!!!!!!

 

두 가지 방법으로 코드를 작성해보았음

사실 처음 생각한 게 이번에도!!!!!!! 시간초과가 떠서.. 

다른 로직을 생각해야만 했음..

 

1. 몫과 나머지가 같은 경우를 비교하는 방식

 

생각할 필요도 없다. 똥이다.

 

 

 

2. 최대공약수(gcd)를 이용해보자.

사실 이건 알고리즘 분류에 '유클리드 호제법'이라고 힌트가 주어져있어서... 생각한 거지

그냥은 생각하기 어려웠을 듯............ 쌩으로 맞춘 사람들...... 똑똑하다........

 

주어진 값을 같은 값 M으로 나누었을 때 나머지 r이 같은 경우를 일반항으로 만들어본다면

a = 주어진 값, M = 몫, r = 나머지 라고 할 때

a1 = Mx1 + r, a2 = Mx2 + r, ...

==> a1 - a2 = M*(x1-x2) 가 되어 r을 소거할 수 있다.

어차피 M을 출력해야 하는 문제이기 때문에 r의 값이 몇인지는 필요없으며,

여기서 주어진 값들의 차이 간에는 공약수 M이 있다는 것을 알 수 있다.

무슨 말이냐면..

a1-a2 = M * (x1-x2)

a2-a3 = M * (x2-x3)

a3-a4 = M * (x3-x4) ....................... 이렇게

입력받은 값들의 차이값은 M과 어떤 수(값은 중요하지않음)의 곱이 되며, 모두 M이라는 공통인수를 갖는다는 것!

M으로 가능한 값의 최대값이 각 차이값들 간의 최대공약수가 될 것이며,

이 수의 약수들이 모두 M의 자리에 들어갈 수 있기 때문에 이 수들이 구하고자 하는 답이 될 것이다.

다만 주어지는 값이 100개까지 될 수 있기 때문에 여러 값의 차이를 모두 비교하는 부분을 고려해서 작성했다.

또한, 가장 중요한 망할놈의 시간초과!!!!!!!를 해결하기 위해

에라토스테네스의 체를 살ㄹ짝 가미하여 코드를 작성해보았음

 

// 2981 검문 -2

let num = Int(readLine()!)!
var arr : [Int] = []

for _ in 1...num {
	arr.append(Int(readLine()!)!)
}
arr.sort()
var gcd = arr[1]-arr[0]

for i in 1..<arr.count-1 {
	gcd = getGcd(gcd, arr[i+1]-arr[i])
} // gcd 구하기

// 시간초과를 극복하기 위해....... 에라스토테네스의 체
var n = Int(Float(gcd).squareRoot())
var resultSet : Set<Int> = []
var result : [Int] = []
for j in 1...n {
	if gcd%j == 0 {
		resultSet.insert(j)
		resultSet.insert(gcd/j)
	}
} // gcd 약수 출력
result = Array(resultSet)
result.sort()
result.removeFirst()

print(result.map{String($0)}.joined(separator: " "))

func getGcd(_ a:Int, _ b:Int) -> Int {
	return a%b==0 ? b : getGcd(b, a%b)
}

 

 

드디어!!!!!!!!!!!!!!!

해결!!!!!!!!

 

 

다른 언어들은 gcd 약수를 출력하는 부분에서 에라토스......선생님을 안 쓰고 아래와 같이만 작성해도 시간초과 안뜸

하지만 스위프트는 시간초과됨

분하다.....

 

아래는 시간초과를 만들었던 gcd 출력부분....

다른 언어들은 for문으로 똑같이 쓰고도 전부 정답이던데... 왜..... ㅜㅜ

// 시간초과 맞기 딱 좋은 출력부분 코드.. 왜 스위프트만?

for i in 2...gcd {
	if gcd%i == 0 {
		print(i, terminator: " ")
	}
}
print("")

 

 

백선생님 스위프트에 조금만 관대함을...

강하게 키워주셔서 감사합니다..?