[프로그래머스] 카펫

programmers.co.kr/learn/courses/30/lessons/42842

코딩테스트 연습 - 카펫

brown 개수와 yellow 개수만 알면 전체 사각형의 가로 길이와 세로 길이를 알 수 있다

brown 개수	yellow 개수	return 값
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

 

왜냐면

1) brown 개수 + yellow 개수 = 전체 개수 = 가로 길이 * 세로 길이 를 알 수 있다

2) 테두리만 brown으로 되어있다는 말은 사각형의 둘레 - 4(중복 개수 빼기)가 brown의 개수다

가로 길이 + 세로 길이 = (brown 개수 + 4)/2 이다.

 

정리하면

가로 * 세로 = brown 개수 + yellow 개수

가로 + 세로 = (brown 개수 + 4)/2

 

이거 어디서 본 거 같으면 우리나라 정규 과정을 잘 따라온 친구들이다

 

가로, 세로를 x, y로 치환하면 이차방정식이라는 걸 알 수 있다

=> 그 유명한 근의 공식을 사용하면 O(1)로 풀 수 있다

x * y = b

x + y = a

라고 하면 x, y = ( b +-√(b^2-4a))/2 로 풀 수 있다

하지만 stl을 쓸 수 없을 땐 어쩔 수 없이 O(n)으로 노가다 해야 함

 

 

x, y 가 자연수일테고 x가 항상 y보다 크거나 같다고 하니

x = a-1 ~ a/2 까지로 범위를 좁힐 수 있다

x가 정해지면 y = a-x로 y도 정할 수 있다.

그러면 x * (a-x) 가 b인지만 확인하면 끝!

 

풀 수 있는 문제는 풀이하기도 쉽구만

 

def solution(brown, yellow):
    mul_ = brown + yellow
    sum_ = (brown+4)//2
    answer = []
    for i in range(sum_-1,sum_//2-1,-1):
        if i * (sum_-i) == mul_:
            answer.append(i)
            answer.append(sum_-i)
            break
    
    return answer