[프로그래머스] [Level 1] 최소직사각형

문제) 최소직사각형

코딩테스트 연습 - 최소직사각형

 

• 내 풀이
• 1트 
  • 두 번째 예제 실패
  • 첫 번째 if문에서 현재 최댓값과 비교하지 못하는 못하고 i 값으로 비교

def solution(sizes):
    w=list(sorted(sizes, key=lambda x: x[0], reverse=True))
    h=list(sorted(sizes, key=lambda x: x[1], reverse=True))
    max_w=w[0][0]
    max_h=h[0][1]
    answer=0

    for i in range(len(sizes)-1):
        if w[i][0]>=h[i][1]:
            if h[i][0]<=h[i+1][1]:
                max_h=h[i+1][1]
            else:
                answer=min(max_w * max_h, max_w*h[i][0])
                break
        else:
            if w[i][1]<=w[i+1][0]:
                max_w=w[i+1][0]
            else:
                answer=min(max_w * max_h, w[i][1]*max_h)
                break
                
    return answer

print(solution([[60, 50], [30, 70], [60, 30], [80, 40]]))
print(solution([[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]]))
print(solution([[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]]))
#결과
4000
100 #실패: 정답 120
133

 

• 2트
  • max_w>=max_h 로 변경 
  • 최댓값의 인덱스를 따로 구해서 값 비교
    • 런타임 에러 & 테스트 실패

def solution(sizes):
    w=list(sorted(sizes, key=lambda x: x[0], reverse=True))
    h=list(sorted(sizes, key=lambda x: x[1], reverse=True))
    max_w=w[0][0]
    max_h=h[0][1]
    index_w=0
    index_h=0
    answer=0

    for i in range(len(sizes)):
        if max_w>=max_h:
            if h[index_h][0]<=h[index_h+1][1]:
                max_h=h[index_h+1][1]
                index_h+=1
            else:
                answer=min(max_w * max_h, max_w*h[index_h][0])
                break
        else:
            if w[index_w][1]<=w[index_w+1][0]:
                max_w=w[index_w+1][0]
                index_w+=1
            else:
                answer=min(max_w * max_h, w[index_w][1]*max_h)
                break
                
    return answer

 

 

 

 

 

 

 

 

 

 

 

 

 

• 3트
  • for문 안의 if문 수정
    • : 명함을 뒤집었을 때의 길이가 다음 길이와 같을 때도 다음 길이를 택해야 하므로 비교연산자를 <= 에서 <로 변경
  • max_w ==max_h 일때 max(min_w, min_h) 값이랑 곱해야 함
    
    • 런타임 에러는 해결
    • 여전히 실패하는 테스트 케이스 존재(4,6) 
    • 해결 못함

def solution(sizes):
    w=list(sorted(sizes, key=lambda x: x[0], reverse=True))
    h=list(sorted(sizes, key=lambda x: x[1], reverse=True))
    max_w=w[0][0]
    max_h=h[0][1]
    answer=0
    min_w=w[0][0] #max_w, max_h 값은 변경할 수 없으므로
    min_h=h[0][1]
    index_w=0
    index_h=0
    
    if max_w>=max_h:
        for i in range(1, len(sizes)):
            if h[index_h][0]<h[i][1]:
                min_h=h[i][1]
                index_h=i
            else:
                if h[index_h][0]<=max_w:
                    min_h=min(min_h,h[index_h][0])
                break
        answer=max_w * min_h
    
    if max_w<=max_h:
        for j in range(1, len(sizes)):
            if w[index_w][1]<w[j][0]:
                min_w=w[j][0]
                index_w=j
            else:
                if w[index_w][1]<=max_h:
                    min_w=min(min_w,w[index_w][1])
                break
        answer=min_w* max_h    
        
    if max_w==max_h:
        answer=max_w* (max(min_w,min_h))
                
    return answer

 

 

4,6번이 어떤 이유에서 틀리는 건지 못찾음...

 

 

 

 

 

 

 

 

 

 

 

 

 

 

• 힌트 보고 풀이
  • 직사각형의 가로, 세로가 정해져 있지 않으므로 각각의 쌍 중 큰 값들 / 작은 값들을 한쪽으로 모아서 직사각형 크기 구함

def solution(sizes):
    w=[max(size[0],size[1]) for size in sizes]
    h=[min(size[0],size[1]) for size in sizes]
    w.sort(reverse=True)
    h.sort(reverse=True)
    return w[0]*h[0]

print(solution([[60, 50], [30, 70], [60, 30], [80, 40]]))
print(solution([[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]]))
print(solution([[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]]))
#결과
4000
120
133