알고리즘/programmers

[Programmers] 캠핑

꾸준함. 2022. 8. 2. 21:59

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

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

 

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

반응형