알고리즘/programmers

[Programmers] 외벽 점검

구데타마 2022. 8. 9. 15:07

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

 

프로그래머스

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

programmers.co.kr

weak와 dist 크기가 별로 크지 않기 때문에 단순 구현으로 풀 수 있는 문제였습니다.

 

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

1. 외벽이 원형이므로 weak 벡터 크기를 두 배로 늘려 (각각의 약점 + n) 값들을 추가해줍니다.

1.1 기존 weak 벡터 사이즈를 weakSize라고 정의하겠습니다.

2. answer를 최댓값으로 설정합니다. (INT_MAX)

3. 취약지점을 모두 점검했다는 것은 weak[idx] ~ weak[idx + weakSize - 1]를 전부 점검했다는 뜻입니다.

4. 각 취약점에 친구들을 어떤 순서로 보낼지 모르기 때문에 next_permutation 메서드를 통해 모든 경우의 수를 확인하고 해당 순서로 보냈을 때 취약지점을 모두 점검할 수 있는지 확인합니다.

4.1 취약지점을 모두 점검했을 경우 answer를 업데이트 해줍니다.

4.2 dist 벡터 크기가 최대 8이므로 최대 8!

5. answer가 INT_MAX일 경우 취약지점을 모두 점검할 수 있는 케이스가 없다는 뜻이므로 -1을 반환하고 INT_MAX가 아니라면 answer를 그대로 반환합니다.

 

 

개발환경: Programmers IDE

 

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

반응형

'알고리즘 > programmers' 카테고리의 다른 글

[Programmers] 블록 이동하기  (0) 2022.08.15
[Programmers] 매칭 점수  (0) 2022.08.15
[Programmers] 공 이동 시뮬레이션  (0) 2022.08.07
[Programmers] 카드 짝 맞추기  (0) 2022.08.05
[Programmers] 캠핑  (0) 2022.08.02