알고리즘 풀이/프로그래머스9 [프로그래머스] 양과 늑대 - JAVA 🔗 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨🏻💻 풀이 및 코드 ArrayList[] childs = new ArrayList[info.lenght] 를 사용하여 child[parent].add(child); 를 통해 부모 자식 간의 관계를 연결합니다. dfs를 통해 갈 수 있는 노드들을 순회하면서, 만약 늑대의 수와 양의 수가 같아진다면 더 이상 진행이 불가하므로 해당 경우의 순회를 종료합니다. 아니라면 최종 답 answer를 Max 값으로 갱신합니다. 자식 노드들을 추가하여 해당 경로로 다시 dfs 순회합니다. 전체 코드 import j.. 2023. 9. 21. [프로그래머스] 기둥과 보 설치 - JAVA 🔗 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨🏻💻 풀이 및 코드 단순 구현 문제였습니다. 기둥과 보를 설치하는 조건이 여러 개여서, 설치하거나 삭제할 때 해당 조건을 만족하는 지를 체크하는 알고리즘을 구현하는 것이 관건이었습니다. 먼저, 헷갈리지 않게 기둥과 보 설치 유무를 체크하는 boolean[][] 배열을 각각 따로 만들어서 체크했습니다. 설치할 땐, checkPillar() 함수와 checkBeam() 함수를 각각 따로 만들어 주어진 조건을 만족하는지 체크했습니다. 삭제할 떈, 우선 삭제를 진행했다가 전체 구조물이 주어진 조건을 만족.. 2023. 9. 20. [프로그래머스] 길 찾기 게임 - JAVA 🔗 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨🏻💻 풀이 및 코드 전위 순회와 후위 순회는 전형적인 알고리즘이라 어려울 게 없지만, 주어진 노드들을 이용해 이진트리를 만드는 것이 까다로운 문제였습니다. 노드들의 연결을 위해 Node 클래스를 생성하여 해당 노드의 x좌표, y좌표, 노드의 번호, 왼쪽 노드, 오른쪽 노드 의 값을 저장합니다. 주어진 노드들을 y좌표가 큰 순서대로 정렬합니다. y좌표가 같다면 x좌표가 작은 순서대로 정렬합니다. 정렬된 노드들 중 가장 첫 번째 노드가 root 노드가 되므로(가장 레벨이 높은 노드), 이 root 노.. 2023. 9. 19. [프로그래머스] 파괴되지 않은 건물 - JAVA 🔗 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨🏻💻 풀이 및 코드 시도 1 - 브루트포스 (시간초과) 단순히 완탐으로 스킬에 포함되는 구간만큼 내구도를 높이거나 낮추는 작업을 하면 시간 초과가 발생합니다. 이 때의 시간 복잡도는 세로의 길이를 N, 가로의 길이가 M, 스킬의 갯수가 K개 일때 O(N * M * K) 의 시간 복잡도를 가집니다. 누적합을 사용하여, 스킬을 사용할 떄마다 N*M 크기만큼 배열을 도는 것이 아니라 O(1) 만에 해결할 수 있습니다. 시도 2 - 누적 합 (성공) 1) 1차원 누적합 만약 [1, 2, 3, 4, 5] .. 2023. 9. 18. [프로그래머스] 풍선 터트리기 - JAVA 🔗 문제 👨🏻💻 풀이 및 코드 이 문제의 핵심은 번호가 작은 풍선은 1번만 터트릴 수 있기 때문에, 현재 풍선을 기준으로 왼쪽에 인접한 풍선과 오른쪽에 인접한 풍선 모두 현재 풍선보다 번호가 작은 풍선이 있다면 현재 풍선은 끝까지 살아남을 수 없습니다. 이 원칙을 사용한 구현 방법은 현재 인덱스를 기준으로 왼쪽 풍선들 중 가장 작은 번호의 풍선 번호를 구하고, 오른쪽 풍선들 중 가장 작은 번호를 구합니다. 가장 작은 번호를 구하는 이유는 큰 풍선들만 터트렸을 때 가장 작은 번호만 남게 되기 때문입니다. 예제 2) 주어진 배열 0 1 2 3 4 5 6 7 8 9 -16 27 65 -2 58 -92 -71 -68 -61 -33 현재 인덱스를 기준으로 왼쪽 풍선들 중 가장 작은 번호 0 1 2 3 4 5 6.. 2023. 8. 4. [프로그래머스] 당구 연습 - JAVA 🔗 문제 👨🏻💻 풀이 및 코드 이 문제를 해결하기 위해선 한 가지 수학적 아이디어가 필요합니다. 입사각과 반사각이 같은 경우는 다음과 같이 네 방향으로 공을 대칭 이동 할 수 있습니다. 예를 들어, 빨간 타겟공을 1번 위치로 대칭이동을 한다면, 파란 시작 공과 1번 공과의 거리가 시작 공에서 벽을 맞고 빨간 공으로 돌아온 거리와 같기 때문에 해당 거리가 최단 거리 입니다. 즉, 네 방향으로 대칭 이동 시킨 후, 그 중 시작 공과의 거리가 가장 짧은 값을 리턴하면 됩니다. 단, 주의할 점이 있습니다. 예시와 같이 3번 방향으로 대칭 이동을 시키는 경우 벽에 맞기 전에 타겟 공을 먼저 맞기 때문에 이와 같이 일직선으로 놓인 방향은 제외시켜야 합니다. 대칭 이동하는 공의 좌표를 수식으로 바꾸면 다음과 같습니.. 2023. 6. 28. 이전 1 2 다음
