Coding 자릿수더하기, 순열검사 예제 With Python feat.시간만족도

문제 설명

길이가 n인 배열에 1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는지를 확인하려고 합니다.
1부터 n까지 숫자가 중복 없이 한 번씩 들어 있는 경우 true를, 아닌 경우 false를 반환하도록 함수 solution을 완성해주세요.

제한사항

• 배열의 길이는 10만 이하입니다.
• 배열의 원소는 0 이상 10만 이하인 정수입니다.

---

입출력 예

arr	result
[4, 1, 3, 2]	true
[4, 1, 3]	false

입출력 예 설명

입출력 예 #1
입력이 [4, 1, 3, 2]가 주어진 경우, 배열의 길이가 4이므로 배열에는 1부터 4까지 숫자가 모두 들어 있어야 합니다. [4, 1, 3, 2]에는 1부터 4까지의 숫자가 모두 들어 있으므로 true를 반환하면 됩니다.

입출력 예 #2
[4, 1, 3]이 주어진 경우, 배열의 길이가 3이므로 배열에는 1부터 3까지 숫자가 모두 들어 있어야 합니다. [4, 1, 3]에는 2가 없고 4가 있으므로 false를 반환하면 됩니다.

문제 출처 : https://programmers.co.kr

---

시간만족도.. 처음 접하였을때 뭐 이런것까지 생각해야하나.. 때문에 풀리지 않았다.. 지금도 완벽히 알고있지는 않지만.

놀라운부분을 알게되었다.

위의 문제를 접하였을때 

def solution(arr):
    if len(arr) != max(arr):
        return False

    if len(arr) == max(arr):
        testlist = [0]*len(arr)
        for i in range(0,len(arr)):
            testlist[i] = arr.count(i+1)
        if testlist.count(2) or testlist.count(0):
            return False
        else:
            return True

나는 이렇게 문제를 해결하였다. 

그런데 시간만족도가 만족이 되지 않다는것을 알게되었고. 

좀더 많은 경우의 수를 앞에서 걸러볼까 고민고민하다가.. 

for 문에서 O(n) 의 문제로 인한것도 확인하게되었다.

그럼 어떻게 해결할까 고민하였고 생각해보니. 두번째 방안으로 정렬 sort 를 먼저 한후 

차례로 비교시키도록 하고 while 문을 이용해 보는 방법도 떠오르게 되었다.

def solution(arr):
    arr.sort()
    i = 1
    while i <= len(arr):
        print(arr[i-1],i)
        if arr[i-1] != i :
            print("false")
            return False
        i = i + 1
    return True

이렇게 하였을 경우는 시간만족도와 공간만족도가 해결되었다.. 

False 의 경우 리턴의 확률이 1번보다는 훨씬 응답이 빠르기때문에 오는 결과 같았다.

주구장창 for 문만 쓰던나에게.... 시간만족도와 공간만족도부분은 새로운 충격이였다.. 공부할께 너무너무 많다.. ㅜ 

---

for 문의 항상 나쁜것은 아니였다 다른 문제의 경우 .

문제 설명

자연수 N이 주어지면, N의 각 자릿수의 합을 구해서 return 하는 solution 함수를 만들어 주세요.
예를들어 N = 123이면 1 + 2 + 3 = 6을 return 하면 됩니다.

제한사항

• N의 범위 : 100,000,000 이하의 자연수

---

입출력 예

N	answer
123	6
987	24

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
9 + 8 + 7 = 24이므로 24를 return 하면 됩니다.

def solution(n):

    ts = time.time()
    n = str(n)
    ex_sum = 0
    for i in range(0,len(n)):
        ex_sum = ex_sum + int(n[i])

    answer = ex_sum
    print(ex_sum)
    nowtime = time.time()- ts
    print(nowtime)
    print("------------------------------------")
    return answer

일부러 시간을 계산해보기 위하여 많은 값을 넣어보았다. 

for 문을 썻기때문에 시간만족도가 성립하지 않았겠지 싶어서

def solution(n):
    ts = time.time()
    ex_sum = 0
    while n>0:
        ex_sum = ex_sum + n%10
        n = n // 10


    nowtime = time.time()- ts
    print(nowtime)
    print(ex_sum)


    #return answer

while 문을 써보았다 

무수히 많은 값을 넣었을때 시간을 재기위해서 타임스템프를 기록하였고 확인해본결과

1번

결과값 : 155688

소요시간 : 0.02316761016845703

------------------------------------

2번

소요시간 : 0.7799994945526123

결과값 : 155688

1번이 훨씬더 빠른 결과값을 가져오는걸 알수있었다..

때에따라서 알맞은 방식을 써야 하는것 같다.. ㅠㅠ 너무 어렵다..