[백준] 1009: 분산 처리 - Swift

노션에서 보기

문제

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

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

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

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

 

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

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

 

---

재용이..?

 

뭔가 문제가 장황한데 결국 요약하면

a^b개의 태스크를 10대의 컴퓨터가 번갈아 수행한다고 할 때, 마지막 태스크를 수행하는 건 몇 번 컴퓨터인지 구하는 문제이다.

 

b의 최댓값이 꽤 크므로 제곱값을 모두 구하두록 두고싶지 않다는 생각이 제일 먼저 들었다.

다행히도 어떤 수를 거듭제곱하면 1의 자리수는 반복될 수밖에 없다.

 

예컨대 9를 거듭제곱하면 9 -> 81 -> 729 -> 6561-> 59049 -> ......1 -> .......9 로, [9,1]의 패턴이 생긴다.

3은 [3, 9, 7, 1], 6은 [6] 등 패턴의 길이는 다르지만 패턴이 생기는건 매한가지!

 

마침 컴퓨터는 10대이므로 a^b가 가지는 1의 자리수가 곧 마지막으로 일하는 컴퓨터가 된다.

그러니 먼저 1의 자리 패턴을 구하고, b를 패턴으로 나눈 나머지를 구한 뒤

그 나머지에 해당하는 패턴의 1의 자리를 불러오기만 하면 끝!

풀이

 

먼저, 실행 파트는 다음과 같다.

실행되어야 하는 카운트를 읽고, 카운트만큼 입력을 읽어서 lastComputer 함수의 리턴을 출력한다.

let tryCount = Int(readLine()!)!

for _ in 1...tryCount {
   let arr = readLine()!.split(separator: " ").map{ Int($0)! }
   print(lastComputer(a: arr[0], b: arr[1]))
}

 

그리고 함수를 살펴보면 다음과 같다.

func lastComputer(a: Int, b: Int) -> Int {
  //1️⃣
   var pattern = [a%10]
   var numNow = a

    //2️⃣
   for _ in 1...b {
       numNow *= a
       let remainder = numNow%10
       if remainder == pattern[0] {
           break
       } else {
           pattern.append(remainder)
       }
   }

    //3️⃣
   let count = pattern.count
   var i = b % count
   i += i == 0 ? count-1 : -1

  //4️⃣
   return pattern[i] == 0 ? 10 : pattern[i]
}

 

먼저, 패턴을 시작하는 시작값을 구하여 패턴 배열에 넣는다.

뒤이어 나올 루프에서 break를 쉽게 지정하기 위해 초기에 지정했다.

무의식 중에 a가 1의 자리 수라고 생각하고 시작해버려서 처음엔 %10을 빼놓고 a만 넣었는데,

a는 100까지 될 수 있으므로 10으로 나눈 나머지를 넣어주어야 했다.

//1️⃣
   var pattern = [a%10]
   var numNow = a

 

그리고 a를 거듭제곱하여 10으로 나눈 나머지를 구한 뒤

앞에서 구한 시작값과 일치하지 않는다면 패턴에 집어 넣고,

일치한다면 패턴이 완성된 것이므로 break

//2️⃣
   for _ in 1...b {
       numNow *= a
       let remainder = numNow%10
       if remainder == pattern[0] {
           break
       } else {
           pattern.append(remainder)
       }
   }

 

그 다음엔 b번 제곱했을 때 1의자리가 패턴의 어느 위치에 있는지 구해준다.

인덱스는 0부터 시작하기 때문에 기본적으로 -1을 해주고,

만약 b%count가 0이 나올 경우 패턴의 맨 마지막에서 끝나는 것이므로 i에 count-1을 넣어 준다.

    //3️⃣
   let count = pattern.count
   var i = b % count
   i += i == 0 ? count-1 : -1

 

또한, pattern[i]의 값이 0이면 10번째 컴퓨터로 끝난다는 뜻이므로 0 대신 10을 리턴해준다.

 //4️⃣
   return pattern[i] == 0 ? 10 : pattern[i]

 

끝!