백준 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)

출력

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

예제 입력 1 복사

5
1 6
3 7
6 2
7 100
9 635

예제 출력 1 복사

1
7
6
1
9

문제 접근 기록

1. 입출력 이해의 중요성..

일단 처음 제출 부터 문제 입력 설명를 잘안보고 해서 완전히 다른방향으로 코드를 짜고있엇다.제출 결과가 틀렸다고 나오길래 입출력 예제를 봤는데 입력 에는 6 가지 입력이 있는데 출력은 왜 5개 결과 값밖에 안나와 있는거지? 라는 생각이들었고 아!~ 입력 하나만 들어오면 그냥 무시하는거구나~ 라는 무자비한 소설을 쓰고 있었다. 그렇게 의미없는 삽질을 한 30분 정도 하고 입력 설명을 자세히 보고 생각이라는 것을 했다. 아.. 자신이 한심해지는 기분을 느꼈다. 처음의 5 는 N 번을 반복 해서 입력이 들어간다는 뜻이였고 그다음부터 숫자 와 숫자 사이에 공백 하나를두고 값이 들어오는뜻이였다.. 이렇게 보니까 입출력 예제가 너무 잘 이해가 됬고 다음 삽질을 시작하기로 했다.

2. 사용자 입력 받기의 난관.

Swift 공부를 시작한지 1달정도 된것 같다. 사용자 입력 받는 연습을 조금 해봤지만 readLine() 만 쓸줄알았지 여기서 사용자 입력을 처리해서 바로 배열의 요소하나하나를 .map을 써서 Casting 하여 저장할수 있을지는 생각도 못했다(역시 아는것만큼 보이는것같다)... 원래는 저번에 써봤던 .components(seperatedBy:" ") 를 써서 들어오는 값을 공백 기준으로 글자하나하나를 배열에 저장하려고 했는데 검색을 하던 와중에 split(seperator:" ") 도 쓸수 있다는 것을 보고 그차이점을 찾아 봤는데 이곳 이 설명을 잘해줘서 이번에는 split 을 .map과 아래와 같이 써보았다.

let iternationNum = readLine()!.split(seperate:" ").map{(Double($0)} 

3. 생각 할것도 없이 modulo 연산자 를 사용해서 풀면 되겠거니 생각하고 문제를 풀었다.

이제 드디어 문제를 푸는 전략을 생각해보았다. 일단 입력 값이 a^b 으로 데이터의 개수를 정하고 데이터의 개수 하나하나마다 1 ~ 10 번째 컴퓨터까지 처리가 되니까 총 데이터의 개수를 10 으로 나눈 나머지가 가 마지막 컴퓨터의 번호와 같을 것이다 라는 생각을 하고 문제를 풀었다. 하지만 overflow 가 7^100, 9^635, 에서 발생했다. 여기서 적어도 modulo 를 사용해서 푸는 문제라는 것을 확신했고 어떻게 큰수를 처리해줄까? 라는 생각을 하게되었고 이것은 더욱더 큰 삽질의 시작이였다.

4. 더욱더 큰 삽질의 시작.

수학 문제를 찾아보기 시작했다. remainder therom, remainder congruence 등등.. 이것들을 이해 하고 코드로 풀어보려고 한 4시간 정도 쓴것같다. 결과는 처참했고, remainder congurence 방법을 사용해서 거의? 문제를 푼듯했으나 나누는 값이 10 이고, 밑 값이 2 일때 이 두값의 나머지가 1이 될때가 없었다. 내가 작성한 코드는 이 두값을 나누고 1이 된 지수를 입력값으로 들어온 지수와 나눠서 나머지가 0이면 나머지는 1 이라는 공식을 썼지만.. 2 mod 10 일떄 나머지 값이 1이 될때가 없음을 뒤늦게 깨닫고 뇌가 무자비하게 멈춰버렸다.

5. 다른방향.

하지만 이과정을 통해서 나는 모든 제곱값의 1의 자리가 일정한 패턴을 갖는다는것을 볼수있었고, 인터넷에 문제에 대해서 검색을 하던중, 이러한 패턴을 사용해서 문제를 푼 해답을 볼수있었다. 결국엔 답을 보는구나 라는 생각을 했는데, 잘 이해해서 내것으로 만들어 보자는 마음으로 코드를 다시 작성하기 시작했다. 아래의 1 ~ 10 까지의 제곱값 테이블을 보고 2,3,5,9 가 지수의 값이 4번 증가하면 1 의자리의 값이 다시 원래값으로 돌아온다는 패턴을 과, 4,5,7,8 은 두번에 걸쳐, 6 에 1의 자리 값은 항상 같다는 것을 확인했다. 그리고 4를 maxCycle 이라는 변수에 지정해 주었고 이값을 입력 값으로 들어온 지수 값과 나누어서 나온 나머지를 새로운 지수 값으로 여겼다. 여기서 나온 나머지는 0~9 사이 의 값이 기 때문에 overflow 걱정은 한시름 놓았다. 이제 이값을 지수로 사용해서 원래처럼 10으로 나누어서 나온 나머지가 컴퓨터의 마지막 번호 일것이라고 생각하고 나온 입출력 예제를 돌려서 확인을 해보니 맞는것을 확인하고 제출을 했는데...

6. 끝난줄 알았지?

끝난게 아니였다. 일단 4의 패턴을 나누고 그 나머지 값을 새로운 지수의 값으로 쓰는 방식은 맞는 것같은데.. 문제가 생겨버렸다. 나눈값의 나머지가 0일경우에 2^0 = 2, 3^0 = 3 와 나머지가 1일경우, 2^1 = 2, 3^1 = 3 의 케이스가 같아져서 밑이 3,4 일때 패턴의 순서와 어긋나기 시작하는것이였다. 그래서 아예 시작점을 +4, 즉 첫번쨰로 들어온 입력 지수값과 4 로 나눈 나머지가 0 이여도 + 4를 다시 더해주기 때문에 시작점이 2^4, 5^4 .. 부터 시작되기 때문에 문제를 해결할수 있었다. 이제 마지막으로 밑이 10 일 경우를 생각해서 마지막 나머지 값이 0 일경우에는 10의 제곱 값과 10(컴퓨터 갯수) 가 나눠지고 남은 남어지라는 의미니, 마지막 컴퓨터의 번호가 10번째라는 것을 작성해줌으로써 결국엔 정답으로 여정을 마칠수 있었다.

7. 정리.

여기서 문제의 부제가 "분산처리" 라고 했는데 일단 이 분산처리라는 뜻 을 잘모르겠다. 그렇게 때문에 내가 작성한 코드가 분산처리를 적용해서 작성한 코든지 아닌지 알수 가 없다. 또한 나는 이 한문제를 풀기 위해서 하루를 다 써버렸다. 알고리즘 문제를 처음 풀어보긴하는거지만 시간이 너무 걸려버렸다. 계속 하면 나아질것 이라는 믿음으로 나아가야지.

부끄러운 답..

//MARK: 1009 번
// Number of test cases
var n = Int(readLine()!)!

//var results = [Int]()
repeat {
    let input = readLine()!.split(separator: " ").map{Double($0)!}
    let base = input.first!
    let exponent = input.last!
    let maxCycle = 4.0
    let numberOfComputers:Double = 10

    let castedExponent = exponent.truncatingRemainder(dividingBy: maxCycle) + maxCycle
    let dataAmount = pow(base, castedExponent)
    let remainder = Int(dataAmount.truncatingRemainder(dividingBy: numberOfComputers))

    //For the case of 10's exponents
    let result = remainder > 0 ? remainder : Int(numberOfComputers)


    print(result)
    n -= 1

}while (n > 0)