백준1009 - 분산처리 JS

https://www.acmicpc.net/problem/1009

해당 문제는 백준에서 제시하는 난이도에 비해, 정답률이 낮은 문제라 포스팅하기로 했다.

 

문제는 컴퓨터 10대가 순차적으로 데이터를 처리한다고 하고 a^b 의 데이터가 주어졌다고 한다면,

마지막 데이터를 처리할 컴퓨터가 무엇인지 묻는다.

즉, a^b의 1의 자리 수를 묻는 문제로, 6^2 라는 데이터가 주어졌다면, 6 (36의 1의 자리 수)를 출력하면 된다.

 

하지만, 지수인 b의 최댓값이 100만이기 때문에 전체 수를 구한 뒤 1의 자리를 파악하는 것은 시간초과가 우려되고,

단순히 a의 1의 자리가 제곱될 때 어떤 규칙성을 가지고 있는지 파악하면 메모리와 시간을 아끼면서 풀이가 가능하다.

 

예를 들어, a가 각각 2 | 12 가 주어졌다고 했을 때, 지수가 변하는 과정에서의 1의 자릿수를 보면

아래와 같이 [2, 4, 8, 6, 2, 4, 8, 6 ...] 순으로 반복성을 가지며 변화하는데 

이는 2든, 12든 1의 자리수가 동일하면 어떤 수를 제곱하더라도 1의 자리수 또한 동일하다는 것을 확인할 수 있다.

지수	1	2	3	4	5
2	2	4	8	16	32...
12	12	144	1728	20736	248832...

 

따라서 다음과 같이 배열의 각 인덱스에 맞게, 1의 자릿수의 변홧값을 갖는 2차원 배열을 만들 수 있다.

  const table = Array.from({length : 10}, ()=> [])
  table[0] = [10] // => 1의 자리수가 0인 경우 10
  for(let i = 1 ; i < table.length ; i ++) {
    let j = 1
    while (true) {
    // 1의 자릿수만 검증 / 추가한다
      const temp = String(Math.pow(i, j ++)).split('').at(-1)
      if(!table[i].includes(+temp)) table[i].push(+temp)
      else break
    }
  }
 
// 위 코드로 만들어지는 table
[
  [ 10 ],         [ 1 ],
  [ 2, 4, 8, 6 ], [ 3, 9, 7, 1 ],
  [ 4, 6 ],       [ 5 ],
  [ 6 ],          [ 7, 9, 3, 1 ],
  [ 8, 4, 2, 6 ], [ 9, 1 ]
]
//

예를 들어, 12^5 의 데이터가 주어졌다고 한다면, (a = 12, b = 5)

table[2] = [2,4,8,6] 이므로, b 와 전체 배열 길이의 나머지 값으로 답을 구할 수 있다.

table[2][(5-1)%table[2].length] => 2

 

전체 소스 코드

const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
  .toString().trim().split('\n')

function solution(data) {
  data.shift()

  // 테이블
  const table = Array.from({length : 10}, ()=> [])
  table[0] = [10]
  for(let i = 1 ; i < table.length ; i ++) {
    let j = 1
    while (true) {
      const temp = String(Math.pow(i, j ++)).split('').at(-1)
      if(!table[i].includes(+temp)) table[i].push(+temp)
      else break
    }
  }

  const result = data.map(el => {
    const [a, b] = el.split(' ')
    // last = a의 1의 자리수
    const last = a.split('').at(-1)
    return table[last][(b-1)%table[last].length]
  })

  console.log(result.join('\n'))
}

solution(input)