[SW Expert] 14450. 정수 입력

 

SW Expert Academy

문제를 읽기 위해선 로그인하여 링크로 들어가셔야 합니다. 

문제를 홈페이지에 띄워 놓으시고 같이 보기를 추천드립니다.

간단한 문제설명입니다.

 

[L, R]의 범위 내에서 어떠한 수 num이 주어질 때,

num으로 시작하는 수가 [L,R]내에 있는 어떤 수의 '접두사'인지를 판단하는 문제입니다.

 

[310, 341] 이라고 가정하고 num의 입력이 3이라고 가정하겠습니다.

3으로 시작하는 수는 3, 30 ~ 39, 300 ~ 399, 3000~ 3999... 입니다.

 

즉, 310~341은 모두 3으로 시작하는 수이기 때문에 O

num의 입력이 35라고 가정했을 때,

35, 350~359, 3500 ~ 3599... 

35로 시작하는 어떤 num은 310~341에 있지 않기 때문에 X입니다.

 

예외처리를 제외하고 이를 찾는 경우를 2가지로 나누겠습니다. 모든 경우의 예외는 num이 R보다 큰 경우입니다(주어진 범위의 마지막보다 큰 숫자가 나온 경우).

 

1) L과 R의 자리수가 같은 경우    * L을 num의 자리수만큼으로 변경 후 그 사이에 num이 있는지 확인한다.   * R은 어차피 범위의 마지막이므로, 변형하지 않아도 항상 R보다는 작거나 같아야 함.

 

예시로 [515, 999]를 확인하겠습니다.

num : 2

 - L을 num의 자리수로 맞춰준다 : L(5),

 - L과 R과 NUM을 비교 : L(5) <= num (2) <= R(999) --> X

 

num : 22

 - L을 num의 자리수로 맞춰준다 : L(51),

 - L과 R과 NUM을 비교 : L(51) <= num (22) <= R(999) --> X

 

num : 50

 - L을 num의 자리수로 맞춰준다 : L(51), 

 - L과 R과 NUM을 비교 : L(51) <= num (50) <= R(999) --> X

 

num : 51

 - L을 num의 자리수로 맞춰준다 : L(51),

 - L과 R과 NUM을 비교 : L(51) <= num (51) <= R(999) --> O

 

num : 612

 - L을 num의 자리수로 맞춰준다 : L(515),

 - L과 R과 NUM을 비교 : L(515) <= num (612) <= R(999) --> O

 

 

 

자리수가 동일하기 때문에 L의 자리수만큼만 비교하면 됩니다.

적어도 L의 접두사로 시작하는 값보다는 크거나 같아야 범위 안에 들어옵니다.

 

2) 자리수가 다른 경우   * L을 num의 자리수만큼 변경 후 그 사이에 num이 있는지 확인한다.   * 이 사이에 없다면 L은 원래의 L값으로 변경   * num의 자리수를 R의 자리수랑 동일해질 때까지     1) 0~9를 붙여서 확인하고     2) 그럼에도 불구하고 범위에 없다면 num의 뒤에 0을 붙인 후 다시 확인

0~9를 붙여서 확인하는 이유는 아래와 같습니다.

접두사 num으로 시작하는 접두사중 두 번째로 작은 수는 num말고 num + '0'입니다.

15로 시작하는 num은 15, 150, 151, 152 ... 이런식이니까요!

 

예시로 [154, 3721] 확인하겠습니다.

 

num : 15

  - L을 NUM의 자리수로 맞춰준다 :  L(15),

  - L과 R과 NUM을 비교 : L(15) <=  num(15) <= R(3721) --> O

  * 실제로 1500의 숫자가 존재합니다.

 

num : 14

  - L을 NUM의 자리수로 맞춰준다 :  L(15),

  - L과 R과 NUM을 비교 : L(15) <=  num(14) <= R(3721) --> X

  - num의 자리수를 R의 자리수랑 동일해질 때까지

   1) 0 ~ 9를 붙인다.

  - L(154), R(3721), num (140~149) 비교 : X

   2) 아직 num의 자리수가 3자리임. 0을 붙인 후 다시 비교합니다

  - L(154), R(3721), num (1400~1409) 비교 : O

   * 실제로 1400~1499의 숫자가 모두 존재합니다.

 

 

문제해결방법을 고민하여 푸는 문제입니다.

생각보다 오래 걸렸고, 테스트케이스도 많은 경우를 확인하여 푸셔야 하겠습니다.. ㅜㅜ

 

코드가 좀 지저분합니다.

그러나, 실제로 작동하는 알고리즘 자체는 매우 간결합니다.

자리수의 비교만 정확하게 하고 불필요한 작업은 아예 하지 않으니 분석하시면 도움이 되실거라 생각합니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int tc;
	cin >> tc;

	for (int k = 1; k <= tc; k++)
	{
		long long int L, R, N;

		cin >> L >> R >> N;
		
		long long int num;

		string ans = "";
		for (int i = 0; i < N; i++)
		{
			cin >> num;

			string strL = to_string(L);
			string strR = to_string(R);
			string strN = to_string(num);
			string TempL = "";
			string TempR = "";
			if (R < num) ans += 'X';

			else if (strL.length() == strR.length())
			{

				for (int j = 0; j < strN.length(); j++)
				{
					TempL += strL[j];
				}

				if (TempL <= strN && strN <= strR) ans += 'O';
				else ans += 'X';
			}
			else
			{
				int idx = 0;
				for (int j = 0; j < strN.length() && j < strL.length(); j++)
				{
					TempL += strL[j];
					idx = j;
				}

				// L를 num의 자리수까지 맞추는 역할을 한다.
				string TempNum = "";
				long long int LAns = stoll(TempL); // 현재까지 L의 값
				long long int NumAns = stoll(strN); // 입력된 Num의 값

				bool flag = false;
				if (LAns <= NumAns && NumAns <= R) flag = true;

				while (strN.length() < strL.length()) // 들어온 NUM의 자리수가 L보다 클 수 있으므로 L보다 큰 수라면 이 작업을 안할 것이고, L보다 자리수가 작다면 이 작업을 할 것이다.
				{
					TempL = TempL + strL[idx++];
					LAns = stoll(TempL);
					for (int x = 0; x <= 9; x++)
					{
						char c = '0' + x;
						TempNum = strN + c;
						if (LAns <= stoll(TempNum) && stoll(TempNum) <= R)
						{
							flag = true;
							break;
						}
					}

					if (flag) break;

					strN = strN + '0';
				}

				while (strN.length() < strR.length())
				{
					for (int x = 0; x <= 9; x++)
					{
						char c = '0' + x;
						TempNum = strN + c;
						if (L <= stoll(TempNum) && stoll(TempNum) <= R)
						{
							flag = true;
							break;
						}
					}

					if (flag) break;

					strN = strN + '0';
				}
				if (flag) ans += 'O';
				else ans += 'X';
			}
		}
		cout << "#" << k << " " << ans << "\n";
	}
}