알고리즘 일기장 - 2
프로그래머스 - 2025 프로그래머스 코드 챌린지 본선
개인적인 사정이 생겨 이번주에 하기로 했던 일정들이 거의 미뤄지게 되었다. 그러다 보니 퇴사일기 3편의 경우 중간까지만 작성하고 아직 수정을 하지 못한 상태다.
아마 다음주 금요일에 업로드 할 것 같다.
그래도 한 주에 최소 하나의 아티클은 작성하는게 목표였다 보니, 주말에 집에 있지 않을 것 같아... 토요일 새벽인 지금 잠시 짬을 내어 주 중에 풀었던 알고리즘 문제에 대한 후기 글을 작성하고자 한다.
프로그래머스 - 2025 프로그래머스 코드 챌린지 본선 - 가장 큰 삼각형 덩어리 (LV4)
해당 문제의 경우, 특정 예외케이스를 생각하지 못하여 꽤나 긴 시간 고생했던 문제다.
문제를 푼 로직 중 핵심로직에 대한 정리를 하며 다시 한 번 문제를 곱씹어 보려한다.
로직 정리 전에 overlap이라는 나만의 단어를 정의하겠다.
overlap -> y좌표와 x좌표가 동일한 두 삼각형이 하나의 그룹에 속한 경우
이제 부터 해당 문제를 해결한 핵심 아이디어를 적어보겠다.
1. n * m의 2차원 격자인데, 각 칸마다 2개의 삼각형을 포함하고 있기 때문에 n * m * 2의 삼각형 배열을 정의하였다.
2. 삼각형의 경우, 총 네가지 모양이 존재하며, 나는 각각의 삼각형을 형태에 따라 0,1,2,3으로 명명하였다.
3. 삼각형 배열을 전체 순회하여, 삼각형들을 모두 그룹화 하였다.
4. 그룹화된 그룹 중, overlap이 존재하지 않는 경우, 삼각형 전체가 그룹에 포함되도 되기 때문에 count로 answer값 갱신
5. 그룹화된 그룹 중, overlap이 존재하는 그룹의 경우 포인터 개념을 추가적으로 활용하여, 일방향 bfs를 진행한다.
굿노트로 작성한 이미지의 예외 케이스를 확인 못해서.... 10번 넘게 도전 후, 마지막에 맞췄다.
- 나중에 좀 더 알아보기 쉽게 코드 정리를 좀 해야겠다.
https://gist.github.com/cws3299/2ca80b5d8d16cd734ba7d9c21c1b825b
