[Programmers] 캠핑

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/1833

프로그래머스

n이 최대 5000이라 O(n^3)으로 풀 수 없는 문제라고 생각했는데 적절한 가지치기를 진행하니 AC를 받을 수 있는 문제였습니다.

사실 문제에서 주어진대로 구현을 하고 제출을 해봤는데 얼떨결에 맞은 문제라 제대로 풀었는지 잘 모르겠습니다.

 

알고리즘은 아래와 같습니다.

1. 우선, data 벡터를 y좌표(문제에서는 x좌표라고 칭함)를 기준으로 정렬을 했습니다.

2. 쐐기의 모든 조합을 확인하고자 이차원 반복문을 작성했고

2.1 두 쐐기가 y 축이든 x 축이든 같은 선상에 있을 경우 직사각형의 넓이가 0이 되므로 제외시켰습니다.

2.2 2.1 조건에서 걸러지지 않은 쐐기 조합에 대해서도 직사각형 사이 다른 쐐기가 들어올 수 있는지 확인하고 들어올 수 있다면 제외시켰습니다.

2.3 2.1, 2.2 조건 둘 다 통과했을 경우 answer를 1 증가시켰습니다.

3. answer를 반환합니다.

 

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~