[알고리즘 문제] 가장 큰 곱 (Python / 파이썬)

문제

유니는 오늘 계단수라는 표현을 배웠다.
계단수란 123, 34, 6789처럼 10진수로 표현한 수의 각 자릿수가 1씩 증가하는 형태의 수를 말한다. 54, 35, 9012 등은 계단수가 아니다.
계단수를 직접 만들어보고 싶었던 유니는 우선 길이가 N인 수열을 만들었다.
이 수열에서 서로 다른 위치에 있는 두 수의 곱이 계단수가 되는 경우를 찾고, 그 중 가장 큰 계단수가 어떤 값인지 계산해 보려고 한다.
그런데 유니가 계산하기에 수열의 길이가 너무 길다. 유니 대신 위 내용을 계산해주는 프로그램을 작성해보자.
만약 두 수의 곱이 계단수가 되는 경우가 없다면 -1을 출력한다.

입력

첫째 줄에 테스트케이스의 수 T가 주어진다..
각 테스트케이스의 첫 줄에 N이 주어진다.
각 테스트케이스의 두번째 줄에 유니가 만든 수열이 공백으로 구분되어 주어진다. 수열에 포함되는 수는 모두 1 이상 10,000 이하의 자연수다.
( 1 ≤ T ≤ 10, 1 ≤ N ≤ 1,000 )

출력

각 테스트케이스마다 '#'과 테스트케이스의 번호, 공백을 출력한 뒤 테스트케이스의 정답을 출력한다.

---

문제 풀이

유니가 만든 수열에서 서로 다른 위치에 있는 두 수의 곱이

계단수가 되는 경우를 찾고 그 중 가장 큰 계단수를 구하는 문제입니다.

 

먼저 유니가 만든 수열에서 서로 다른 위치에 있는 두 수의 곱을 

하나씩 구하며 계단수인지 확인해줍니다.

어떤 수를 10으로 나눈 나머지를 구하면 그 수의 맨 끝자리만 나오고

10으로 나눈 몫을 구하면 끝자리를 제외한 나머지 수가 나오게 됩니다.

즉, 456을 10으로 나눈 나머지는 6이고 몫은 45입니다.

따라서 이를 이용해 각 자리수를 분리할 수 있습니다.

 

만약 10으로 나눈 나머지에서 1을 뺀 값이 다음으로 나눈 나머지와 다르다면 

이는 계단수의 조건과 맞지 않으므로 False를 반환해줍니다.

만약 457을 10으로 나눈 나머지를 구하고 1을 빼면 6 입니다. 

다음으로 나눈 나머지는 5 인데 6과 다르므로 계단수가 아닙니다.

만약 456을 10으로 나눈 나머지를 구하고 1을 빼면 5 입니다.

다음으로 나눈 나머지는 5이므로 계단수 조건에 맞습니다.

위 과정을 모두 수행했는데 False가 반환되지 않았다면 계단수라는 것이므로

True를 반환해줍니다.

 

따라서 만약 계단수라면 최대값을 구하도록 max 함수를 이용해주었습니다.

이때, 만약 계단수가 하나도 없다면 최대값은 -1이 될 것입니다. 

따라서 -1이면 -1을 출력해주고 그렇지 않다면 계단수 중 최대값을 출력해줍니다.

---

My Code

# 계단수인지 확인
def check(x):
    now = x % 10 # 수의 맨 끝자리 값을 넣어줌
    x //= 10     # 맨 끝자리를 없앰
    while x > 0:
        if x % 10 != now - 1: # 이전 끝자리에서 1을 뺀 값과 현재 끝자리가 다르다면  
            return False # 계단 수 아니므로 False 반환
        now = x % 10 # 맨 끝자리 값 넣어줌
        x //= 10 # 맨 끝자리 없앰
    return True # 계단수라면 True 반환
    
for tc in range(int(input())):
    n = int(input()) # 수열의 수

    array = list(map(int,input().split())) # 수열

    result = -1
    for i in range(n - 1):
        for j in range(i + 1, n):
            now = array[i] * array[j] # 서로 다른 위치의 수를 곱해줌 
            if check(now): # 곱한 수가 계단수라면
                result = max(result, now) # 최대값 계산 

    print('#' + str(tc + 1), end = ' ')
    if result == -1: # 계단수가 하나도 없다면
        print(-1)    # -1 출력
    else:            # 계단수가 존재한다면 
        print(result) # 최대값 출력