[백준/C++] 수 이어 쓰기 2 - 1790번

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

1790번: 수 이어 쓰기 2

 

문제 자체는 되게 간단하다.

N과 K를 입력받아

1~N까지 숫자를 나열한 후 K번째 문자열을 찾기

 

첫번째 풀이 - 실패 (메모리 초과)

#include <bits/stdc++.h>
using namespace std;

string s = "";

int WriteNum(int start, int end, int targetNum) {
	while (start <= end) {
		// 숫자를 문자로 변환 후 삽입
		s += to_string(start);
		start++;
	}
	if (s.size() < targetNum)
		return -1;
	else
		return s[targetNum - 1] - '0';
}

int main() {
	int n, k; cin >> n >> k;

	cout << WriteNum(1, n, k);
}

단순히 현재 숫자를 모두 문자로 변환 후 String type 변수 s에 쭉 나열하고 K번째 숫자를 찾는 것

풀면서도 될리가 없다고 생각했다

 

두 번째 풀이 - 성공

#include <bits/stdc++.h>
using namespace std;

int WriteNum(int start, int end, int targetNum) {
	// string에 저장없이 쭉 쓰다가 k번째 자리가 나오면 그거 출력하고 그냥 끝내기
	int nowNumLen = 0;
	int ans = -1;
	while (start <= end) {
		string nowNumStr = to_string(start);

		nowNumLen += nowNumStr.size();
		if (nowNumLen >= targetNum) {
			int tmp = nowNumLen - nowNumStr.size();
			ans = nowNumStr[targetNum - tmp - 1] - '0';

			break;
		}
		start++;
	}
	return ans;
}

int main() {
	int n, k; cin >> n >> k;
    
	cout << WriteNum(1, n, k);
}

- 풀이 -

메모리 초과를 피하기 위해 string에 저장하지 않고 해당 숫자의 길이만 nowNumLen 변수에 누적시켜준다.

계속 더해주다가 nowNumLen이 K를 넘어서는 순간의 숫자가 바로 우리가 찾는 숫자이다.

K번째 자리에 해당하는 숫자를 알아냈다면 그 숫자 중 무엇인가를 알아내야 하는데 나는 어이없게도 여기서 많이 헤맸다.

 

우선 [전체 길이 - 현재 숫자의 길이] 를 해주면 이 전 숫자까지의 길이가 나온다. 편의상 prevLen이라고 하겠다.

k - prevLen을 해주면 현재 숫자의 몇번째에 K번째 값이 있는지 알 수 있다.

추가로 1부터 N까지 돌며 길이를 더해도 K를 넘을 수 없다면 -1을 출력해준다. (ans = -1)

배열은 0부터 시작하니 - 1을 해주고 문자를 숫자로 나타내기 위해 0의 아스키코드를 빼주면 정답이 나온다.