[백준] 1790.수 이어 쓰기 2 (Swift)

[백준] 1790.수 이어 쓰기 2 (Swift)

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

1790번: 수 이어 쓰기 2

풀이

입력값의 최대 크기가 1억이기 때문에 단순히 문자열을 이어붙여서 탐색하는 방법으로는 문제를 해결할 수 없습니다.

 

그래서 규칙을 찾아야 하는데, 이 문제에서 찾을 수 있는 규칙은 다음과 같습니다.

 

1자리 숫자 1~9 는 총 9개가 존재합니다.

2자리 숫자 10~99 는 총 90개가 존재합니다.

3자리 숫자 100~999 는 총 900개가 존재합니다.

4자리 숫자 1000~9999 는 총 9000개가 존재합니다.

 

위처럼 따라가다 보면 n 자리 숫자는 총 9 * 10^n 개가 존재한다는 것을 확인할 수 있습니다.

 

하지만 저희가 구하는 것은 숫자의 개수가 아닌 숫자에 포함된 문자의 개수입니다.

 

n 자리 숫자는 모두 n 자리로 이루어져 있기 때문에, 존재하는 숫자의 개수에 자릿수를 곱해주면 해당 범위에 몇개의 문자가 포함되는지 알 수 있습니다. 이는 9 * 10^n * n  으로 나타낼 수 있습니다.

 

그렇다면 1자리는 9개, 2자리는 90 * 2 개, 3자리는 900 * 3 개... 의 문자를 가지고 있다는 것을 알 수 있습니다.

 

주어진 숫자 K 가 몇번째 문자인지 찾기 위해서는 K 가 몇자리 수인지 알아야 합니다. 그리고 그보다 작은 자릿수의 경우를 모두 빼주면 범위는 확 줄어듭니다.

 

예를 들어 K 가 200 이라는 3자리 수라면, 1자리수 9개, 2자리수 90 * 2 개를 제외해 200 - ( 9 + 180) = 11 이라는 숫자가 나온다는 것을 알 수 있습니다.

 

이는 K 가 3자리수의 시작인 100 으로부터 11 번째 문자를 가리킨다는 것입니다. 

 

여기서 도출한 숫자를 원래 자릿수로 나눠줍니다. 11 의 경우 3 으로 나눠주면 3 이라는 값이 나오고, 나머지는 2 가 됩니다.

 

이는 100 보다 3만큼 큰 숫자인 103의 2번째 자릿수를 의미합니다. 그래서 정답은 0이 됩니다.

 

여기서 도출해낸 103 이라는 숫자가 첫번째 입력값인 N 보다 크다면 -1 를 출력해주면 됩니다.

코드

	import Foundation
	let input = readLine()!.split(separator: " ").map { Int(String($0))! }
	var (n, k) = (input[0], input[1])
	var counts = 9
	var digit = 1
	var minus = digit * counts
	var num = 0
	// 자리수에 따라 빼줄수 있는만큼 반복
	while k > minus {
	k -= minus
	num += counts // 몇자리수인지 걸러서 시작점 찾기
	counts *= 10 // 자리수마다 숫자의 개수
	digit += 1 // 자리수
	minus = digit * counts // 자리수마다 문자의 개수
	}
	let increase = (k - 1) / digit
	let mod = (k - 1) % digit
	num += 1 + increase
	// 해당 숫자가 입력값보다 클 시
	if num > n {
	print(-1)
	} else {
	let label = "\(num)"
	let index = label.index(label.startIndex, offsetBy: mod)
	print(label[index])
	}
	// 1자리수 9
	// 2자리수 90 * 2
	// 3자리수 900 * 3
	// 4자리수 9000 * 4
	// 5자리수 90000 * 5

view raw BOJ_2467.swift hosted with ❤ by GitHub