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

SW Expert Academy

SW Expert Academy

---

개인적으로 많이 고쳐서 풀어냈지만 몇몇 테스트케이스에서 빗나갔다.

 

다시 고쳐내는데 가시성이 좋지 않게 작성하여 생각하기 어려웠다. 

 

그래서 다른 분들의 정답을 참고해서 내 문제점을 알게되었다.

 

다들 조건문 처리에서 함수를 사용하여 나타내었고, 타인인 자신이 보기에도 이해하기 쉬웠다.

 

나는 조건확인으로 boolean 형 변수를 계속 사용했었다. 하지만 함수로 선언해서 반환값으로 사용하면 좋다고 느꼈다.

 

또한 리스트는 최대한 줄이는 방향이 좋다고 느꼈다. 그래야 코테에서도 유리할 것이다.(시간적으로)

 

---

 

문제풀이에서 조건을 꼭 확인한다!

 

• 양의 정수 N 개 A1, …, AN이 주어진다.
• 1 ≤ i < j ≤ N 인 두 i, j에 대해, Ai x Aj값이 단조 증가하는 수인 것들을 구하고 그 중의 최댓값을 출력
•  Ai x Aj중에서 단조 증가하는 수가 없다면 -1을 출력한다

 

문제예제처럼 2 4 7 10 이라면 Ai x Aj 값은 i < j 임을 꼭 숙지!!

 

A1 *A2~4 = [ 8, 14, 20 ]   

A2 *A3~4 = [ 28, 40 ]   

A3 *A4 = [ 70 ]   

 

 

이 중에서 단조 증가하는 수는 14, 28 이고 이 중에서 최대값은 28

 

---

 

다른분 참고하여 만든 정답

def check(number): #단조증가인지 확인
    number = str(number)
    for index in range(len(number)-1):
        if (number[index] > number[index+1]):
            return False # 한번이라도 감소하면 false;
    return True # 감소하지 않으면 True

T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    integer_lst = list(map(int,input().split(" ")))
    result = -1 # -1 or 최대값
    for i in range(N):
        for j in range(i+1,N):
            mul_number = integer_lst[i]*integer_lst[j]
            if result < mul_number and check(mul_number): #최대값인지 동시에 단조증가인지 확인
                result = mul_number
    print(f"#{test_case} {result}")

 

 

여기서 나는 모든 Ai * Aj 조합을 한 리스트에 넣고 전부 넣은 이후 for 문을 통해  Ai * Aj 가 단조증가인지 확인하였다.

하지만 다른분의 풀이에서는 result < Ai * Aj 을 사용하였다. 이 부분에서 이미 현재  Ai * Aj 최대값보다 작으면 단조증가를 확인안해도 되어 더 효율적이라는 것에 배워가는게 많았다.

---

 

다음은 내 최근 오답이다.

T = int(input())
 
for test_case in range(1, T + 1):
    N = int(input())
 
    integer_lst = list(map(int,input().split(" ")))
    mul_lst = list()
    for i in range(len(integer_lst)):
        for j in range(i+1,len(integer_lst)):
            mul_lst.append(integer_lst[i]*integer_lst[j])
    condition_lst = list()
    for number in mul_lst:
        increase = True
        number = str(number) #단조증가인지 확인하기 위해 문자열로 만듦.
        if len(number) <= 1: #한자리는 단조증가아님
            increase = False
            continue
 
        pre = number[0]
        for num in number[1:]: # 각 자리수 확인
            if int(num) < int(pre):
                increase = False
                continue
            pre = num
        if increase:
            condition_lst.append(int(number))
    if len(condition_lst) == 0:
        print(-1)
    else:
        print(f'#{test_case} {max(condition_lst)}')

 

 

---

 

	메모리	시간	코드길이
최근오답	159,368 kb	3,129 ms	907
다른분코드 참고	60,932 kb	693 ms	676

무려 메모리에서는 약 2.7배, 시간에서는 4.4배, 코드길이 1.3배 차이가 난다. 엄청난 효율차이를 보여준다.

SWEA 에서 Python 은 제한시간이 4초 인것을 감안하면 잘 작성해야겠다는 것을 느꼇다.