[그리디] 프로그래머스 level 3 숫자게임 (Python 파이썬)

💡문제 링크

프로그래머스

 

 

💡문제 분석 요약

A팀에 n개의 자연수, B팀에 n개의 자연수가 있다.

A팀과 B팀에서 자연수 하나씩 비교해서 B팀의 자연수가 더 크면 1점을 얻는다.

A팀의 자연수 목록을 알고 있을 때, B팀이 가지고 있는 자연수의 순서를 어떻게 배치해야 최대 점수를 얻을 수 있을까.

 

💡알고리즘 설계

먼저 정렬이 필요하다고 생각했다. 오름차순으로 정렬한 뒤, 앞에서부터 비교한다.

예를 들어 A = [2, 2, 7, 8, 9]이고 B = [3, 4, 6, 8, 10]인 경우 A의 첫번째 원소와 B의 첫번째 원소를 비교하며 시작한다.

A의 원소 < B의 원소이면 그 다음 원소로 넘어간다.만약 A의 원소 < B의 원소이면 B만 그 다음 원소로 넘어가고, 다시 비교한다.while문을 이용해서 구현했다.

 

💡코드

def solution(A, B):
    A.sort()
    B.sort()
    answer = 0
    i, j = 0, 0
    while i <= len(A)-1 and j <= len(B)-1:
        if A[i] < B[j]: 
            answer += 1
            i += 1
            j += 1
        else:
            j += 1
    return answer

 

💡 오답 풀이

def solution(A, B):
    A.sort()
    B.sort()
    answer = 0
    for i in range(len(A)):
        if A[i] <= B[i]:
            answer += 1
    return answer

맨 처음에 제출했던 바보같은 코드.. 같은 위치에서만 비교한다고 잘못 생각했다.

def solution(A, B):
    A.sort()
    B.sort()
    answer = 0
    i, j = 0, 0
    while i <= len(A)-1 and j <= len(B)-1:
        if A[i] <= B[j]: 
            answer += 1
            i += 1
            j += 1
        else:
            j += 1
    return answer

부등호를 A[i] <= B[j]로 해서 틀렸다. <=가 아니라 <이어야 한다.

💡 다른 풀이

def solution(A, B):
    answer = 0
    A.sort()
    B.sort()
    j = 0
    for i in range(len(A)):
        if A[j] < B[i]:
            answer = answer + 1
            j = j+1
    return answer

for문과 while문(j += 1)을 같이 썼다.

i는 for문 속에서 1씩 커지고, j는 A[i] < B[j]를 만족하는 경우에 1씩 커진다.

💡 느낀점 or 기억할정보

27분 소요