[프로그래머스] 09/16 (3)

[폰켓몬]-[찾아라 프로그래밍 마스터]

My answer

def solution(nums):
    tmp=set(nums)
    
    if(len(nums)/2>=len(tmp)):
        return len(tmp)
    else:
        return len(nums)//2

Another answer

def solution(nums):
    return min(len(set(nums)), len(nums)//2)

[체육복]-[탐욕법(Greedy)]

My answer

def solution(n, lost, reserve):
    answer = 0
    cloth = [1]*n
    
    for i in lost:
        cloth[i-1]-=1
    for i in reserve:
        cloth[i-1]+=1     
    i=0   
    
    while(i!=len(cloth)):
        if(cloth[i]>1):
            if(i==0):
                if(cloth[i+1]==0):
                    cloth[i]-=1
                    cloth[i+1]+=1
            elif(i==len(cloth)-1):
                if(cloth[i-1]==0):
                    cloth[i]-=1
                    cloth[i-1]+=1
            else:
                if(cloth[i-1]==0):
                    cloth[i]-=1
                    cloth[i-1]+=1
                    continue
                elif(cloth[i+1]==0):
                    cloth[i]-=1
                    cloth[i+1]+=1
                    continue
        i+=1
    answer=cloth.count(1)+cloth.count(2)
            
    return answer

탐욕법(Greedy)

미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법으로, 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘이다. 따라서 특정 문제를 만났을 때 단순히 현재 상황에서 가장 좋아보이는 최적의 해만 선택해도 문제를 정상적으로 풀어낼 수 있는지 파악해야 한다.

Another answer

def solution(n, lost, reserve):
    reserved = 0
    # 차집합의 성질을 이용
    # 옷이 아예 없는 사람 
    lostN = list(set(lost) - set(reserve))
    # 여분의 옷이 있는 사람 
    reserveN = list(set(reserve) - set(lost))
    lostN.sort()
    for l in lostN:
        for x in range(l-1, l+2):
        # 여분의 옷이 있는 사람중 
            if x in reserveN:
            # 제거하고 reserved(옷이 있는사람) 수를 늘림 
                reserveN.remove(x)
                reserved += 1
                break
    return n - len(lostN) + reserved
--------------------------------------------------------------------
def solution(n, lost, reserve):
    _reserve = [r for r in reserve if r not in lost]
    _lost = [l for l in lost if l not in reserve]
    for r in _reserve:
        f = r - 1
        b = r + 1
        if f in _lost:
            _lost.remove(f)
        elif b in _lost:
            _lost.remove(b)
    return n - len(_lost)

내 코드는 우선 O(n)의 시간복잡도를 가지고있는 것 같고, 2번째 코드는 O(n^3), 3번째 코드는 O(n^2)의 시간복잡도를 가진다. 우선 2,3번째 코드는 똑같은 방법이다. 여분이 있는 사람과 옷이 아예 없는 사람을 미리 구분해두고 remove를 이용하여 계산하였다. 내 코드가 시간은 더빠르지만 코드가 지저분해보인다는 단점이 있는 것 같다.

[모의고사]-[완전탐색]

My answer

def solution(answers):
    answer,score=[],[0]*3
    
    stu=[[1,2,3,4,5],[2,1,2,3,2,4,2,5],[3,3,1,1,2,2,4,4,5,5]]
        
    for i in range(len(answers)):
        for j in range(len(stu)):
            if(answers[i]==stu[j][i%len(stu[j])]):
                score[j]+=1  
                
    for i in range(len(score)):
        if(max(score)==score[i]):
            answer.append(i+1)
        
    return answer

Another answer

def solution(answers):
    pattern1 = [1,2,3,4,5]
    pattern2 = [2,1,2,3,2,4,2,5]
    pattern3 = [3,3,1,1,2,2,4,4,5,5]
    score = [0, 0, 0]
    result = []

    for idx, answer in enumerate(answers):
        if answer == pattern1[idx%len(pattern1)]:
            score[0] += 1
        if answer == pattern2[idx%len(pattern2)]:
            score[1] += 1
        if answer == pattern3[idx%len(pattern3)]:
            score[2] += 1

    for idx, s in enumerate(score):
        if s == max(score):
            result.append(idx+1)

    return result

[enumerate]

enumerate는 "열거하다"라는 뜻으로 순서가 있는 자료형(리스트, 튜플, 문자열)을 입력으로 받아 인덱스 값을 포함하는 enumerate 객체를 돌려준다.