[codility] Lv2- OddOccurrencesInArray,Lv3-TapeEquilibrium ,TapeEquilibrium

프로그래머스 문제에만 의존하던터라, coldility 라는 새로운 코드풀이 플랫폼을 알게 되었고,

문제를 열심히 풀어보기로 결심했다.

문제를 풀이하면서 처음으로 놀란 것은 코드의 효율성을 신경써야 하는 것

그동안은 그렇게 효율성에 대해서 깊게 생각해보지 못했지만, 

효율성이 좋지않거나 지나친 반복문이 계속되는 코드는.... score에서 깎이게 된다...

 

문제를 풀며 배운 점

1. 예외처리를 해야한다. 

2. 입력값의 범위 크기를 알아야 한다.

3. 시작복잡도에 대한 고민을 하자 (https://rrecoder.tistory.com/63)

 

---

📌   2- OddOccurrencesInArray

배열에서 자신과 중복한 값의 개수가 홀수인 값을 return 하는 문제

첫 풀이

def solution(A):

    cntDic={}

    for i in A:
        if i not in cntDic:
            cnt=0
            for j in A:
                if j==i:
                    cnt+=1
            cntDic[i]=cnt
    for num,cnt in cntDic.items():
        if cnt%2==1:
            return num

1) cnt 딕셔너리 생성

2) 딕셔너리에 있지 않으면 해당 값을 for문을 돌며 찾아서 더해줌

3) 그 딕셔너리를 다시 돌며 개수가 홀수인 값을 더해줌

 

결과는 처참했다. 

일단 bigNumber를 전혀 신경쓰지 않았던 터이기에 성능테스트에서 전부 빵점!

일단 Detected time complexity:O(N**2)  ㄹ즉 시간복잡도 한계가 O(N**2)인데

 

for문 안에서 if 문을 통해 배열을 탐색하는 것 N^2 

근데 나는 for 문 안에서 if 문 안에서 for 문 ? 

 

다른 풀이

def solution(A):
    if len(A) ==1:
        return A[0]
    A = sorted(A)

    for i in range(0,len(A),2):
        if i+1 == len(A):
            return A[i]
        if A[i]!=A[i+1]:
            return A[i]

시간복잡도 : O(N) or O(N*logN)

sorted의 시간복잡도 : O(N*logN)

정렬된 배열을 따라 두개씩 for 문을 돌며 뒤의 값과 다르면 !

 

참고 :https://wayhome25.github.io/algorithm/2017/04/30/OddOccurrencesInArray/

---

📌  STEP 3-1 ) FrogJump 

내 풀이 (100%)

def solution(X, Y, D):
    Y-=X

    if Y%D ==0:
        return Y//D
    else:
        return Y//D+1

개구리가 목표 지점까지 가는 최소 횟수를 구하는 문제인데 , 

생각을 조금 해보니 쉽게 풀 수 있었다..

 

---

📌  STEP 3-2 ) PermMissingElem

내 풀이(50%)

def solution(A):
    if len(A)==1:
        return A[0]
    A=sorted(A)
    
    for idx in range(1,len(A)+1):

        if A[idx]-1 != A[idx-1]:
            return A[idx]-1

1) A를 정렬한 후

2) A를 돌며 현재 값+1 과 다음값이 같지 않으면

3) 현재값+1이없는것이니 return 

하는 방법으로 풀이했는데  오답이 되었다.

런타임 에러가 나오는걸 보니 엄청나게 많은 범위의 수를 가지고 잇는 배열을 정렬하기 때문에 불가능한 것 같다.

고로 정렬은 하지 않아야 한다!

 

 

다른 풀이

def solution(A):
	idxArr= [0]* (len(A)+1)
    
    for i in A:
    	idxArr[i-1]=1
    
    return idxArr.index(0)+1

1) A의 인덱스 배열을 생성

2) A를 돌며 A의 값을 인덱스로 사용

 

idxArr = [1,1,1,0,1] 이 값이 되면서 채워지지 않은 부분의 idx+1 값이 답이 된다.

 

 

다른풀이

def solution(A):
	return sum(range(len(A)+2)) - sum(A)

[1,2,3,5]   15-11 = 4 가 나오는데

[0,1,2,3,4,5] - [1,2,3,5] 라고 볼 수 있다.

 

 

---

📌  STEP 3-3 ) TapeEquilibrium

내 풀이1 ( 53% )

def solution(A):
    sumArr=[]
    length=len(A)
    for i in range(1,len(A)):
        sumArr.append(abs(sum(A[:i])-sum(A[i:length])))

    return min(sumArr)

1) 반복문을 돌며 해당 숫자의 범위까지 slicing한 배열의 합과 차를 구한다

2) 그 값을 sumArr에 넣고 최종값 구하기

 

아마 min값을 구하는 부분에서 많은 시간을 소요한것으로 예상한다.

시간복잡도 한계는 = O(N * N)

역시 모든날 모든 순간 느렸다..

 

다른 풀이

def solution(A):
    firstSum=0
    lastSum=sum(A)
    minSum=None
    for i in range(1,len(A)):
        firstSum +=A[i-1]
        lastSum-=A[i-1]
        diff = abs(firstSum-lastSum)
        if minSum==None:
            minSum = diff
        else:
            minSum = min(minSum,diff)
    return minSum

나와 다른 점 (즉 어디에서 시간을 감소시켰나.)

1) Sum은 한번만 한다 

그 후 반복문을 돌며 위치에 따른 값을 더하고 빼준다

2) min은 필요에 의해 하지만 많은 값들을 한번에 넣은 후 하지 않고 그때그때 작은 범위로 한다.