1
google codeJam 자격 확인 문제 중 하나는 두 개의 지정된 정수 사이에 '재활용 쌍'이 몇 개 있는지를 찾는 것이 었습니다.중첩 루프보다 빠른 알고리즘?
이것은 내 해결책 이었지만 큰 데이터 입력 집합에 대해서는 충분히 빠르지 않았습니다. @a = 10, @b = 200000과 같이 주어지면 속도가 느려집니다.
나는 내 솔루션이 O (2^n) 일 것이라고 생각한다. (아직 큰 O 분석에는 확실한 이해가 없다.) 끔찍하다. 더 빠른 알고리즘을 사용하여 두 개의 루프를 반복하는 표준 방법이 있는지 궁금합니다.
def getPairs
(@[email protected]).each do |n|
([email protected]).each do |m|
if (containsSame(n,m)) && (isMatch(@a, n, m, @b))
@recycledPairs += 1
end
end
end
end
편집 : Google CodeJam site에서 :
당신은 n에 뒤쪽에서 어떤 자리를 이동하여 m를 얻을 수 있을지는 별개의 양의 정수 (N, m)의 한 쌍의 재활용한다고 가정 해 봅시다 그들의 순서를 바꾸지 않고 전면. 예를 들어, (12345, 34512)는 12345의 끝에서부터 앞쪽으로 345를 이동하여 34512를 얻을 수 있으므로 재활용 된 쌍입니다. 재활용 된 쌍이 되려면 n과 m의 숫자가 같아야합니다. n도 m도 선행 0을 가질 수 없습니다.
"재활용 쌍"이란 무엇입니까? – Ryan
루프 및 중첩 루프는 알고리즘이 아닌 구현 아티팩트입니다. – JRL
Google codeJam 사이트에서 : 순서를 변경하지 않고 n의 뒤쪽에서 정면으로 일부 자리를 이동하여 m을 얻을 수 있다면 뚜렷한 양의 정수 (n, m) 쌍을 재활용한다고 가정 해 봅시다. 예를 들어, (12345, 34512)는 12345의 끝에서부터 앞쪽으로 345를 이동하여 34512를 얻을 수 있으므로 재활용 된 쌍입니다. 재활용 된 쌍이 되려면 n과 m의 숫자가 같아야합니다. n도 m도 선행 0을 가질 수 없습니다. – AFraser