Luhn

지침

숫자가 주어지면 룬 공식에 따라 그 숫자가 유효한지 판별해요.

룬 알고리즘은 신용카드 번호나 캐나다 사회보험 번호처럼 다양한 식별 번호를 검증하는 데 사용하는 간단한 체크섬 공식이에요.

해야 할 일은 주어진 문자열이 유효한지 확인하는 거예요.

숫자 검증

길이가 1 이하인 문자열은 유효하지 않아요. 입력에는 공백이 들어갈 수 있지만, 검사하기 전에 공백을 제거해야 해요. 그 외의 숫자가 아닌 문자는 모두 허용되지 않아요.

예시 1: 유효한 신용카드 번호

4539 3195 0343 6467

룬 알고리즘의 첫 번째 단계는 오른쪽부터 시작해서 두 번째 자리마다 숫자를 두 배로 만드는 거예요. 두 배로 만들 자리는 다음과 같아요.

4539 3195 0343 6467
↑ ↑  ↑ ↑  ↑ ↑  ↑ ↑  (double these)

두 배로 만든 값이 9보다 크면 그 결과에서 9를 빼요. 두 배로 만든 결과는 다음과 같아요.

8569 6195 0383 3437

그다음 모든 자릿수를 더해요.

8+5+6+9+6+1+9+5+0+3+8+3+3+4+3+7 = 80

합이 10으로 나누어떨어지면 그 숫자는 유효해요. 이 숫자는 유효해요!

예시 2: 유효하지 않은 신용카드 번호

8273 1232 7352 0569

오른쪽부터 시작해서 두 번째 자리마다 숫자를 두 배로 만들어요.

7253 2262 5312 0539

자릿수를 모두 더해요.

7+2+5+3+2+2+6+2+5+3+1+2+0+5+3+9 = 57

57은 10으로 나누어떨어지지 않으므로 이 숫자는 유효하지 않아요.

---

출처

Wikipedia의 Luhn 알고리즘