[프로그래머스] [Level 2] [BFS] [2022 KAKAO BLIND RECRUITMENT] 양궁대회

문제) 양궁대회

코딩테스트 연습 - 양궁대회

 

• 내 풀이 → Error
  • 가장 큰 값들로 구할 경우와 다른 경우들의 코드를 따로 나눈 첫 코드
  • 두가지를 합친 코드로 아래에 다시 작성

def solution(n, info):
    score=[10,9,8,7,6,5,4,3,2,1,0]
    answer = []
    count=0
    count2=0
    lion_sum, lion_sum2=0,0
    apeach_sum=sum([score[info.index(i)] for i in info if i!=0]) #현재 어피치 점수
    apeach_sum2=apeach_sum
    answer2=[]
    last=0
    
    for i in info:
        if count==n:
            answer.append(0)   
            continue
        if count+(i+1)>n:
            answer.append(0)
            continue
        else:
            count+=(i+1)
            answer.append(i+1)
            lion_sum+=score[info.index(i)]
            if i!=0:
                apeach_sum-=score[info.index(i)] #라이언이 점수 얻는 경우 어피치 점수에서 감점
    if count!=n:
        answer[-1]+= (n-count)
        
    for i in info:
        if count2==n:
            answer2.append(0)   
            continue
        if count2+(i+1)>n:
            answer2.append(0)
            continue
        else:
            if i==max(info):
                answer2.append(0)
            else:
                count2+=(i+1)
                answer2.append(i+1)   
                lion_sum2+=score[info.index(i)]
                if i!=0:
                    apeach_sum2-=score[info.index(i)]
                
    if count2!=n:
        answer2[-1]+= (n-count2)
        
    if lion_sum<=apeach_sum:
        answer.clear()
        answer.append(-1)
    if lion_sum2<=apeach_sum2:
        answer2.clear()
        answer2.append(-1)
    
    if lion_sum-apeach_sum<lion_sum2-apeach_sum2:
        answer=answer2
    elif lion_sum-apeach_sum==lion_sum2-apeach_sum2:
        for i in range(10,-1):
            if answer2[i]>answer[i]:
                answer=answer2
                break
        
    return answer

 

• 내 풀이 → Error
  • 리스트로 합쳐서 한가지 for문으로 한 번에 해결

def solution(n, info):
    score=[10,9,8,7,6,5,4,3,2,1,0]
    max1=[0,1,2,3,4,5,6,7,8,9,10]
    info2=info
    
    answer = []
    count=[0]*11
    lion_sum=[0]*11
    apeach_sum=[sum(score[idx] for idx,i in enumerate(info) if i!=0)]*11 #현재 어피치 점수
    gap=[0]*11
    
    for j in range(11):
        ans=[]
        if j>=1:
            max1.remove(info.index(max(info2)))
            info2[info2.index(max(info2))]=-1
            
        for idx, i in enumerate(info):
            if count[j]==n:
                ans.append(0)   
                continue
            if count[j]+(i+1)>n:
                ans.append(0)
                continue
            else:
                if idx not in max1:
                    ans.append(0)
                    continue
                        
                count[j]+=(i+1)
                ans.append(i+1)   
                lion_sum[j]+=score[idx]
                if i!=0:
                    apeach_sum[j]-=score[idx]
            
        if count[j]!=n:
            ans[-1]+= (n-count[j])

        answer.append(ans)
        gap[j]=lion_sum[j]-apeach_sum[j]
        
    if max(gap)<=0:
        return [-1]
    elif gap.count(max(gap))>1:
        gap.reverse()
        indx=gap.index(max(gap)) #점수차가 제일 큰 값중 제일 작은 값을 가지는 배열 선택
        return answer[11-indx-1]
    else:
        return answer[gap.index(max(gap))]

 

테스트 케이스는 모두 통과하지만 제출 코드는 에러

 

 

 

 

 

 

 

 

 

 

 

 

 

• 다른 사람 풀이
  • BFS
  • 앞부분 부터 무조건 어피치보다 +1 발 쏘는 경우 / 0발 쏘고 뒤로 턴 넘기는 경우 두가지 모두 실행
  • 참고한 블로그

[Python] 프로그래머스 양궁대회 (BFS)

 

from collections import deque

def bfs(n, info):    
    res = []
    q = deque([(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])])
    maxGap = 0
    
    while q:
        focus, arrow = q.popleft()
        
        if sum(arrow) == n:  # 종료조건 1) 화살 다 쏜 경우: 점수 계산
            apeach, lion = 0, 0
            for i in range(11):
                if not (info[i] == 0 and arrow[i] == 0):
                    if info[i] >= arrow[i]:
                        apeach += 10 - i
                    else:
                        lion += 10 - i
            if apeach < lion:  # 라이언이 이기면
                gap = lion - apeach
                if maxGap > gap:
                    continue
                if maxGap < gap:
                    maxGap = gap  # 최대점수차 갱신
                    res.clear()
                res.append(arrow)  # 같은 값일 때는 res 지우지 않고 추가
        
        elif sum(arrow) > n:  # 종료조건 2) 화살 더 쏜 경우
            continue
        
        elif focus == 10:  # 종료조건 3) 화살 덜 쏜 경우
            tmp = arrow.copy()
            tmp[focus] = n - sum(tmp)
            q.append((-1, tmp)) #종료조건1로 계산할 수 있게 다시 q에 넣음
        
        else:  # 화살 쏘기 (무조건 +1 더크게 / 0발 쏘고 뒤로 턴 넘기는 방법 두가지 모두 실행)
            tmp = arrow.copy()
            tmp[focus] = info[focus]+1 
            q.append((focus+1, tmp))  # 어피치보다 1발 많이 쏘기
            tmp2 = arrow.copy()
            tmp2[focus] = 0
            q.append((focus+1, tmp2))  # 0발 쏘기
    return res

def solution(n, info):
    winList = bfs(n, info)
    
    if not winList:
        return [-1]
    elif len(winList) == 1:
        return winList[0]
    else:
        return winList[-1]