SW 적성진단 - 사각형 면적

문제

N개의 (x, y)좌표가 주어지면 그 좌표들을 포함하는 선과 x축, y축 사이의 최소한의 면적을 구한다
좌표를 포함하는 선은 오른쪽or아래 로만 이동할 수 있다

SSAFY n기 CT시험에서 출제되었던 문제를 기억해두었다

N=3, N=5, N=7 ... N=12 등으로 6개까지 있었고, 그림은 주어지지않는다

권장풀이시간은 6분으로 추정된다

규칙을 찾지 못하면 대부분 3~5개? 정도 풀수있는 시간이 되었던거 같다

시험에서는 단순히 답만 작성하면 되지만 소스코드 까지 작성해보았다

풀이

예제)
N=6
(5,1) (8,8) (5,3) (4,10) (2,2) (12,4)

일단 2차원 배열을 생성해 각각의 좌표값들을 1차원 배열로 다시 담았다
그 뒤 x좌표값을 오름차순으로 정렬하면
[2,2], [4,10], [5,1], [5,3], [8,8], [12,4] 과 같은 모양이된다
여기서 핵심은 n번째y좌표가 n+1번째 y좌표보다 작거나 같다면 n번째 좌표는 뭍히는 좌표이므로 건너뛴다는 점이다.

y가 8을넘지 않으면 (8,8)에 의해 포함됨

그렇지 않으면 결과값에 면적을 더한다
더해줄 때는 이전에 계산한 x값을 저장하였다가 현재 x값에서 빼준뒤 더해줄 면적을 구한다

3번 더해짐

답 : 88

소스코드

python)

def square(point):
    i=0
    prev_num=0
    result=0
    point.sort()

    while i<=len(point):
        try:
            if(point[i][1] >= point[i+1][1]):
                result = result + (point[i][0]-prev_num)*point[i][1]
                prev_num=point[i][0]
            i += 1
        except IndexError:
            result = result + (point[i][0]-prev_num)*point[i][1]
            break
        
    return result

print(square([[5,1],[8,8],[5,3],[4,10],[2,2],[12,4]]))