알고리즘 풀이56 [프로그래머스] 양과 늑대 - 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. [BOJ] 15898. 피아의 아틀리에 ~신비한 대회의 연금술사~ - JAVA 🔗문제 👨🏻💻 풀이 및 코드 문제 유형 및 난이도 : 구현, 브루트 포스 / G1 1. Point 클래스 생성 재료를 회전할 수 있기 때문에, score, color 배열을 따로 만든다면 각각을 회전 시켜야 한다. 한번에 넣어 회전시키기 위해 Class 를 생성했다. static class Point { int score; char color; Point(int score, char color) { this.score = score; this.color = color; } } 2. N개 중에 3개를 뽑아 나열한다. -> 순열 N개 중에 이미 뽑은 재료는 건너뛴다. selection에는 넣어야 할 재료의 번호와 순서를 저장한다. ex) 2, 1, 3 3개의 재료를 모두 뽑았다면, 가마의 상태를 초기화하고.. 2023. 6. 30. 이전 1 2 3 4 ··· 10 다음
