ABC 324 - D번 복기, 순열 다루는 테크닉 - 두 문자열이 서로의 순열일려면? -

1. 문제

 

D - Square Permutation (atcoder.jp)

D - Square Permutation

 

2. 풀이

 

주어진 정수 문자열의 순열이 어떤 정수의 제곱수가 될때, 그러한 순열의 개수를 구하는 문제.

 

길이 제한이 13이라고 해도 모든 순열을 찾고, 각 순열이 어떤 수의 제곱수인지 검사하면 매우 느리다

 

1) 만약 길이 N인 s의 순열이 X의 제곱수가 될려면, X는 아무리 커봐야 $\sqrt{10^{N}}$이다.

 

그러므로 0부터 $\sqrt{10^{N}}$까지 모든 정수 i에 대해 i의 제곱이 길이 N인 s의 순열이 될 수 있는지 체크해본다.

 

 

여기서 s의 순열을 모두 구하고 체크하는게 아니라, 어떤 두 문자열 s와 t가 서로의 순열이 될 수 있는지를 생각해본다.

 

2) 만약 s의 순열이 t가 된다는 뜻은, s와 t가 동일한 문자로 구성되어 있다는 뜻이다.

 

그러므로, 애초에 s를 정렬해두고 i의 제곱을 list로 바꾼 다음 정렬해서 두 리스트의 구성이 동일한지 체크하면 된다.

 

 

여기서 주의할 점은 주어진 정수 문자열 s에는 0이 들어가 있을 수 있는데, "0부터 $\sqrt{10^{N}}$까지 모든 정수 i"에는 

 

0이 없으니까, s와 i의 제곱이 동일한 길이가 되도록 i의 제곱 리스트에 0을 넣어준다

 

n = int(input())

s = sorted(input())

count = 0

max_value = pow(10,n)

i = 0

while i*i < max_value:
    
    t = list(str(i**2))

    while len(s) != len(t):
        
        t.append('0')
    
    t.sort()
        
    find = False
    
    for j in range(len(s)):
        
        if s[j] != t[j]:
            
            find = True
            break
    
    if find == False:
        
        count += 1

    i += 1

print(count)

 

여기서 중요한 디테일이 있는데... for문으로 바꾸면 시간이 4초가 넘어서 시간초과가 난다

 

n = int(input())

s = sorted(input())

count = 0

for i in range(int((10**n)**(1/2))+1):
    
    t = list(str(i**2))

    while len(s) != len(t):
        
        t.append('0')
    
    t.sort()
        
    find = False
    
    for j in range(len(s)):
        
        if s[j] != t[j]:
            
            find = True
            break
    
    if find == False:
        
        count += 1

print(count)

 

for문 range()가 배열 만들어서 while보다 느리겠다 생각했는데..

 

알고보니 len(t)가 시작부터 len(s)보다 큰 경우가 있어서.. 여기서 무한루프 일어나더라...

 

while len(s) != len(t):
        
    t.append('0')

 

뒤에 int((10**n)**(1/2))로 고치면 시간은 비슷하더라...

 

근데 이러면 오답임... 확실히 int((10**n)**(1/2))+1까지는 해야돼.. 이게 루트 구하면서 오차가 있으니까

 

n = int(input())

s = sorted(input())

count = 0

for i in range(int((10**n)**(1/2))):
    
    t = list(str(i**2))

    while len(s) != len(t):
        
        t.append('0')
    
    t.sort()
        
    find = False
    
    for j in range(len(s)):
        
        if s[j] != t[j]:
            
            find = True
            break
    
    if find == False:
        
        count += 1

print(count)

 

그래서 애초에 len(t)가 len(s)보다 크면 continue로 스킵

 

n = int(input())

s = sorted(input())

count = 0

for i in range(int((10**n)**(1/2))+1):
    
    t = list(str(i**2))
    
    if len(t) > len(s):
        continue

    while len(s) != len(t):
        
        t.append('0')
    
    t.sort()
        
    find = False
    
    for j in range(len(s)):
        
        if s[j] != t[j]:
            
            find = True
            break
    
    if find == False:
        
        count += 1

print(count)

 

핵심은 두 문자열이 서로의 순열이라는 것은?

 

두 문자열의 구성이 서로 동일하다.

 

따라서 두 문자열을 정렬하면 동일한 문자열이 되어야한다.