[Python][SWEA] 6190. 정곤이의 단조 증가하는 수 D3

SW Expert Academy

---

🗒️ 파이썬 코드 풀이

def danjo(m_ls) : 
    for i in range(1,len(m_ls)) : 
        if  m_ls[i] < m_ls[i-1] :
            return False 
    return True 

T = int(input())
for test_case in range(1, T + 1):
    N = int(input()) 
    lst = list(map(int,input().split()))
    
    mul_lst = []
    for i in range(N-1) : 
        for j in range(i+1,N) :
            mul_lst.append(lst[i]*lst[j])

    ans = -1   
    for m_ls in mul_lst : 
        if danjo(str(m_ls)) : 
            ans = max(ans,m_ls)
    
    print(f"#{test_case} {ans}")

 

1. 2중 반복문을 이용해서 리스트에 값들을 2개씩 곱하고 mul_lst에 붙여넣는다.

 

2. mul_lst의 값들을 하나씩 문자열로 바꿔 함수에 파라미터 값으로 넣는다. 그리고 단조 증가를 확인한다.

(return을 이용하여 for문을 쉽게 빠져나오기 위해 함수를 만들었다.)

 

3. ans에 최대값을 갱신하여 답을 구한다.

 

시간 복잡도 제한 4초

 

📌 내가 작성한 코드

from collections import deque
T = int(input())
for tc in range(1,T+1) :
    N = int(input())
    lst = deque(list(map(int,input().split())))

    mul_lst = []
    
    while len(lst) > 1:  
        for ls in range(1,len(lst)) :
            mul_lst.append(lst[0]*lst[ls])
        lst.popleft()
    
    str_lst = list(map(str,mul_lst)) 
    mx = -1

    for sr in str_lst :  
        v = list(sr)
        tmp = sorted(v)
        if v == tmp: 
            mx = max(mx,int(sr)) 
    
    print(f"#{tc} {mx}")

 

문제 자체가 어렵지는 않아서 조건들 구현은 문제 없었다. 

다만, 시간 초과가 내 멘탈을 와자작 부셨다...  최대한 시간 복잡도를 줄일려고 했는데, 잘 되지 않았다.

 

[시간 복잡도 줄이기 위한 노력]

 

1. stack 구조를 queue 구조로 바꿔서 리스트들의 곱을 구했는데 큰 효과는 없었다.

 

2. while 문을 for 문으로 바꿔서 효율성을 높히려 했지만  큰 효과는 없었다.

 

3. sorted를 tmp로 선언 후 if 문을 돌렸는데 큰 효과는 없었다.

 

4. 불필요한 타입 변환을 줄이려 했는데 큰 효과가 없었다.

 

하지만, 여기에서 sorted를 쓰지않고 for문으로 해결하면 시간복잡도 문제는 해결된다 ...

(sort로 시간복잡도 문제가 생기면, for문으로 풀자 ... 형 변환도 최대한 자제하고 ...  메모 !)

 

 

정답률 제가 다 낮췄습니다 ... 죄송합니다 ㅠ_ㅠ

---

📚 문제

정곤이는 자신이 엄청난 수학자임을 증명하기 위해, 어떤 규칙 만족하는 수를 찾아보기로 했다.

그 규칙은 단조 증가하는 수인데, 각 숫자의 자릿수가 단순하게 증가하는 수를 말한다.

어떤 k자리 수 X = d1d2…dk 가 d1 ≤ d2 ≤ … ≤ dk 를 만족하면 단조 증가하는 수이다.

예를 들어 111566, 233359는 단조 증가하는 수이고, 12343, 999888은 단조 증가하는 수가 아니다.

양의 정수 N 개 A1, …, AN이 주어진다.

 1 ≤ i < j ≤ N 인 두 i, j에 대해, Ai x Aj값이 단조 증가하는 수인 것들을 구하고 그 중의 최댓값을 출력하는 프로그램을 작성하라.


[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N(1 ≤N ≤ 1,000) 이 주어진다.

두 번째 줄에는 N개의 정수 A1, …, AN(1 ≤ Ai ≤ 30,000) 이 공백 하나로 구분되어 주어진다.


[출력]

각 테스트 케이스마다 단조 증가하는 수인 Ai x Aj중에서 그 최댓값을 출력한다.

만약 Ai x Aj중에서 단조 증가하는 수가 없다면 -1을 출력한다.