https://www.acmicpc.net/problem/1515
initial
Trying greedy questions after a long time. I always found that I tend to implement like how a human would solve it. What i mean is i implement just like how the question described. So I thought of concatentating number from 1 to max 3000 (as given in question) and somehow deleting numbers and matching numbers of the given n.
But I have to think broadly. Don’t implement exactly like the question description, especially greedy questions. Lets think. Instead of iterating through the given string n, what about we increment a number variable and its digits and if it matches with the n[index], we increment index and see the next n’s digits? Once index goes out of boundary, that is when we exit and return the number.
solution
n = input()
index = 0
num = 0
while n:
num += 1
for i in str(num):
if i == n[index]:
index += 1
if index >= len(n):
print(num)
exit()complexity
Iterating through str(num) is log(10^k), which is k. Quiz number can increment from 0 to 9 and it still iterates one time. So number of iterations is proportional to log10 (k) where k is length of number (string type). The outer while loop is 10^k cuz There are 10^k possible combinations of digits of length k (from 000...0 to 999...9). So final is k * 10^k. Space is k.
Example to Illustrate
Consider n = "123":
Length k=3
Worst case, you might have to search through all numbers from 1 to 999.
That's 10^3=1000 numbers.
For each number, converting to a string and checking could take up to O(k).
Thus:
1000 numbers to check.
Each number check takes O(3) time.
This givesO(10^3⋅3)=O(3000).
