[완전탐색] 최소직사각형 (프로그래머스, Level 1)

Soorim Yoon·2022년 9월 24일
0
post-custom-banner

문제

https://school.programmers.co.kr/learn/courses/30/lessons/86491

  • 모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 sizes가 매개변수로 주어진다.
  • 모든 명함을 수납할 수 있는 가장 작은 지갑을 만들 때, 지갑의 크기를 return 하도록 solution 함수를 완성해라.

풀이

  • 가로와 세로 값을 저장할 수 있는 garo, saero 배열을 각각 생성해 sizes 배열에 이차원배열 형태로 저장된 길이 정보를 저장한다. garo 배열에는 가로 값들만, saero 배열에는 세로 값들만 저장한다.
  • 가로, 세로 통틀어 최대 길이 값이 어디에 위치한지 파악한다.
  • 만약 최댓값이 가로에 위치한다면, 해당 최댓값을 제외한 나머지 (가로, 세로) 값들 중 가로 < 세로인 경우, 즉 가로보다 세로 값이 더 긴 경우를 찾는다. 해당 경우가 존재하면 가로와 세로의 값을 바꿔준다.
  • 만약 최댓값이 세로에 위치한다면, 해당 최댓값을 제외한 나머지 (가로, 세로) 값들 중 가로 > 세로인 경우, 즉 가로가 세로보다 더 긴 경우를 찾는다. 해당 경우가 존재하면 가로와 세로 값을 바꿔준다.
  • 모든 연산이 다 끝나고 garo, saero 배열이 정해지면, 정답은 처음에 구한 최댓값과 상대편 배열의 최댓값의 곱이 된다.

예시

예시를 통해 알아보자.

1) 최댓값이 가로에 있는 경우
sizes = [[60, 50], [30, 70], [60, 30], [80, 40]]

  • 가로와 세로 값을 정리해보면 다음과 같은 상황이다. 이때 최댓값은 가로의 80이며, 가로가 80인 경우를 제외한 나머지 값들의 가로, 세로 값의 크기를 비교하면 다음과 같다.
  • 가로가 세로보다 큰 경우는 (30, 70) 인 경우이다. 해당 값들을 서로 교환해준다.
  • 교환 후의 모습은 위와 같다. 최종적으로 정답을 구하면, 처음에 구한 최댓값(80)과 세로의 최댓값인 50을 곱한 값이 정답이 된다.

2) 최댓값이 세로에 있는 경우
sizes = [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]]

  • 가로와 세로 값을 정리해보면 다음과 같은 상황이다. 이때 최댓값은 세로의 15며, 세로가 15인 경우를 제외한 나머지 값들의 가로, 세로 값의 크기를 비교하면 다음과 같다.
  • 나머지 세 개의 (가로, 세로) 쌍이 모두 가로 값이 세로 값보다 크다. 해당 경우들을 서로 값을 교환해준다.
  • 교환 후의 모습은 위와 같다. 최종적으로 정답을 구하면, 처음에 구한 최댓값(15)와 가로의 최댓값인 8을 곱한 값이 정답이 된다.

코드

위 풀이를 코드로 구현하면 다음과 같다.

def solution(sizes):
    answer = 0
    
    garo = []	# 가로 값들을 모두 저장
    saero = []	# 세로 값들을 모두 저장
    for i in range(len(sizes)):
        garo.append(sizes[i][0])
        saero.append(sizes[i][1])
    
    max_length = max(max(garo), max(saero))		# 가로, 세로 통틀어 가장 긴 값을 찾아 max_length에 저장
    
    if max_length in garo:		# 최댓값이 가로에 있다면
        for i in range(len(garo)):		# 최댓값을 제외한 나머지 값들 중, 가로 < 세로인 경우를 찾아 서로 값을 바꿔준다.
            if garo[i] < saero[i]:
                garo[i], saero[i] = saero[i], garo[i]
        answer = max_length * max(saero)	# 최댓값(가로)*세로의 최댓값이 최종 정답
    elif max_length in saero:	# 최댓값이 세로에 있다면
        for i in range(len(garo)):		# 최댓값을 제외한 나머지 값들 중, 가로 > 세로인 경우를 찾아 서로 값을 바꿔준다.
            if garo[i] > saero[i]:
                garo[i], saero[i] = saero[i], garo[i]
        answer = max_length * max(garo)		# 최댓값(세로)*가로의 최댓값이 최종 정답
    
    return answer
  • 위 방식으로 구현한 코드가 정답 코드였지만, 더 간략하게 작성하는 방법이 있을지 더 생각해보고자 한다.

채점 결과


profile
👩🏻‍💻 AI를 좋아하는 IT학부생
post-custom-banner

0개의 댓글