[codility] Lesson 4) FrogRiverOne MaxCounter

📌   4-1) - FrogRiverOne

주어진 1부터 주어진 X값이 나온 가장 빠른 idx를 구하는 문제

 

 

첫 풀이 (54%)

def solution(X, A):
    idArr = [0]*X
    for i in range(len(A)):
        idArr[A[i]-1]=1

        if sum(idArr)==X:
            return i
    return -1

1) idArr 생성

2) A를 돌며 해당 값을 idx로 넣어줌 

3) idArr가 다 찼을 때 return

 

역시나 시간복잡도로 인하여 점수르 반이나 깎였다.

제한 시간복잡도는 O(N ** 2)

 

 

이미 for + if의 조합으로 N^2이 되어있엇고 

그안에서 sum연산까지 하기 때문에 모자라고 sum을 없애야 한다!!

 

다른 풀이 (100%)

def solution(X, A):
    idArr = [0]*X
    idSum=0

    for i in range(len(A)):
        if idArr[A[i]-1]==0:
            idArr[A[i]-1]=1
            idSum+=1

        if idSum==X:
            return i
    return -1

역시나 sum을 없애니 해결

개선한점 1) 어차피 for 안에 if가 있을거면 연산 자체도 조건에 해당할 때만 하게 함

개선한점 2) 반복문을 돌 때마다 Sum을 하지 않고 idSum을 만들어 만족함을 확인

 

---

📌   4-2) - MaxCounter

 

내 풀이 (55%)

def solution(N, A):

    ans=[0]*N
    for num in A:
        if 1<= num <=N:
            ans[num-1]+=1

        else :
            maxNum = max(ans)
            ans=[maxNum]*N

    return ans

1) A를 돌며  조건을 비교한다.

2) 그 숫자가 N+1 이면 그 당시의 max값으로 전체 ans 변경

3) 그게 아니면 해당 값을 인덱스로 해 ans 변경

 다른 풀이 (100%)

def solution(N, A):
    counters = N * [0]
    nextMax =  maxNum = 0

    for i in A:
        if i <= N:
            curr = counters[i-1] = max(counters[i-1] +1, maxNum+1)
            nextMax = max(curr,nextMax)
        else:
            maxNum =nextMax

    return [c if c > maxNum else maxNum for c in counters]

nextMax: 매 상황의 max 값

maxNum: 조건이 N+1일 때의 max 값 

 

 

나는 조건이 N+1일때 ans 전체를 매번 ans=[maxNum]*N  다시만들기 때문에 시간이 많이 소요되는 반면에 

 

조건이 N+1이나올 당시의 max값을 저장해 두고 

넣어줄때마다 그 max+1 값과 넣어줄 값(+1) 을 비교해 넣어주고 

 

마지막에 한번도 탐색하지 않은 index 만 마지막 max값으로 변경해주면 된다.

 

 

 

 

 

 

 

💙 시간복잡도를 위해 이렇게 신경쓴 코드를 짤 수 있다니 그 논리력에 놀랐다.

핵심은 반복문을 돌며 그 조건을 마주했을 때의 동작(전체다 바꿔주기) 을 없앴다는 것이다.

 

---

 

📌   4-3)  MissingInteger

배열이 주어졌을 때 나오지 않은 가장 작은 정수를 return

음수일땐 1, 나오지 않은게 없을땐 max +1 

 

 

첫 풀이

def solution(A):

    A=list(filter(lambda x: x>0, A))
    A.sort()
    smallNum=1
    changeCnt=0
    
    if len(A)==0:
        return 1
    for i in range(len(A)-1):
        if A[i]+1!=A[i+1]:
            smallNum = A[i]+1
            changeCnt+=1

    if changeCnt==0:
        return max(A)+1
    else:
        return smallNum

1) A에서 음수 필터링

2) A 배열이 비었으면 1 리턴

3) A 배열을 돌며 연속적이지 않은 수를 계속 smallNum에 넣어줌

4) 한번도 바뀌지 않은 (즉 연속적인) 값은 max+1

 

결과는 처참! 

예외처리 안한 부분과 성능면에서 낮아졌다.

 

 

다른 풀이

def solution(A):
    A=list(set(A))
    A.sort()
    smallNum=1
    for i in A:

        if smallNum ==i:
            smallNum+=1

    return smallNum

smallNum을 1로 잡아두고 A를 돌며 비교한다

이 로직은 모든  테스트케이스를 만족한다.

 

음수만 있는 경우 : return 1

연속하는 수가 다 있는경우 : return max+1

빠지는 수가 있는경우 : 연속하지 않은 부분에서 멈춘 값 (제일작은 나오지 않은 값)

 

 

참고 :https://sooho-kim.tistory.com/33