[kata][python] 백준 알고리즘 1009번 문제 (분산처리)

분산처리

출처: 백준 알고리즘 1009번 문제

문제

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, … ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, …

총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)

출력

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

예제입력
    5
    1 6
    3 7
    6 2
    7 100
    9 635

예제출력
    1
    7
    6
    1
    9

내 풀이1(시간초과 및 오답)

import sys
data_cnt = int(sys.stdin.readline())
for _ in range(data_cnt):
    a, b = map(int, sys.stdin.readline().split())
    print((a ** b) % 10)

처음엔 아주 단순하게 생각했다.

a에 b를 제곱해서 10으로 나눈 나머지를 출력했다.

하지만 이 또한 에러가 있었다.

a의 b제곱이 10으로 나누어 떨어질 경우는 0을 출력하게 되는데,

문제의 조건에 의하면 10을 출력해야 한다.

내 풀이2(정답)

import sys
data_cnt = int(sys.stdin.readline())
for _ in range(data_cnt):
    a, b = map(int, sys.stdin.readline().split())
    result = [(a ** i) % 10 for i in range(1,5)][(b % 4) -1]
    print(result if result != 0 else 10)

어떤 수의 N제곱을 10으로 나누었을때의 나머지에 규칙이 있는지 찾아보았다.

즉, 어떤 수를 계속 제곱해나가면 1의자리수에 뭔가 규칙이 있지 않을까 생각했다.

그랬더니 다음과 같은 규칙이 발견되었다.

2의 제곱의 1의자리수: [2, 4, 8, 6] 계속 반복됨

3의 제곱수의 1의자리수: [3, 9, 7, 1] 계속 반복됨

4의 제곱수의 1의자리수: [4, 6, 4, 6] 계속 반복됨

5의 제곱수의 1의자리수 : [5, 5, 5, 5] 계속 반복됨

4의 경우처럼 두 개의 숫자가 반복되는 것도 있고,

5의 경우처럼 한 개의 숫자가 계속 반복되는 것도 있다.

하지만 3개의 숫자가 반복되거나, 4개 이상의 숫자가 반복되는 경우는 찾지 못했다.

따라서 우선 “어떤 수를 제곱했을때 1의 자리 숫자는 4개의 숫자 묶음 규칙이 번갈아가며 계속 반복된다”는 가설을 세웠다.

그래서 우선 a를 1부터 4까지 제곱한 수의 1의자리 숫자 리스트를 만들었다.

이해를 돕기위해 a가 8이고 b가 5라고 가정해보자.

이 경우, 8을 1부터 4까지 제곱한 수의 1의자리 집합인 [8, 4, 2, 6] 이라는 리스트를 만든것이다.

그리고 이 숫자 집합들은 8의 5제곱, 6제곱, 7제곱, 8제곱의 1의자리 숫자와도 같다.

그러므로 8의 5제곱의 1의자리를 구하기 위해서는, 5를 4로 나누었을때 나머지를 앞서 구한 리스트의 인덱스로 취해서 값을 뽑아오면 된다.

다만, 리스트 인덱스는 0부터 시작되므로, 나머지에서 1을 빼주면 된다.

5를 4로 나누었을때의 나머지는 1이고, 여기서 1을 빼면 0이다.

이 0이라는 숫자를 위에서 만든 리스트의 인덱스로 넣어주면 8을 가져오게 된다.

그래서 나온 결과 코드가 [(a ** i) % 10 for i in range(1,5)][(b % 4) -1] 이다.

이렇게 구한 값을 그대로 출력하면 되지만, 한 가지 예외가 있다.

만약 이 값이 0이라는 것은 10의 배수임을 뜻하므로 무조건 마지막 연산하는 컴퓨터는 10번 컴퓨터가 된다.

따라서 10을 출력해준다.

분석

완전 같은건 아니지만,

예전에 소수 관련 문제에서 배운 “에라토스테네스의 체” 개념이 조금 도움이 되었다.

미리 결과로 예상되는 값의 목록을 구해놓고, 거기에서 맞는 값을 가져오니 속도가 확실히 빨라졌다.

오늘 회사에서도 대용량 공간데이터를 쪼개어 밀어넣는 작업을 했었는데, 예전에 일본어데이터로 비슷한 작업을 했던 경험이 있어서 비교적 쉽게 진행할 수 있었다.

그냥 경험해봤기 때문만은 아니고, 잘 기억이 안나서 컴퓨터를 뒤져보다가 무의식중에 스티커메모에 기록해둔 것을 발견한게 큰 도움이 되었다.

아쉽게도 글로 적은 문서밖에 찾지 못했는데, 코드, 테스트코드와 함께 조금 더 제대로 정리해놨다면 훨씬 빠르게 마칠 수 있었을것이다.

꼭 알고리즘 문제풀이뿐만 아니라, 많은 것을 경험해보고 그것을 문서로 기록해두는 것은 중요한 것 같다.

가끔 귀찮아서 기록을 소홀히 하는 경향이 있는데, 한 단계 발전하기 위해서는 반드시 경험과 기록이 병행되어야한다는 것을 다시 한 번 느꼈다!

코딩장이

-장이: [접사] ‘그것과 관련된 기술을 가진 사람’의 뜻을 더하는 접미사.

Share Share