📖 문제
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
💡 풀이 방식
• DFS
필요 자료구조
- 그룹 별 상자 갯수 저장할 int형 우선순위 큐 (상자 갯수가 많은 순으로 내림차순 정렬)
- 상자가 열림/닫힘을 표현할 boolean형 방문 표시 배열
1. cards 배열의 0부터 cards.length-1번째 원소까지 돌며 방문하지 않은 칸이 있다면, 방문 처리하고 그룹 내에 포함된 상자 수를 세러 간다. (dfs 메소드)
2. DFS 메소드 구현
- 종료 조건 : 열었던 상자인 경우(visited[idx] == true), 여태껏 구한 상자 갯수를 큐에 저장하고 리턴한다.
- 만약 방문하지 않았다면, 방문 처리하고, 배열의 해당 idx-1 위치로 이동하면서 (현재 그룹 내 상자 수+1)한 값을 함께 가져간다.
private static void dfs(int idx, int depth) {
if(visited[idx]) { // 열었던 상자인 경우
pq.add(depth); // 상자 갯수를 큐에 저장하고 리턴
return;
}
visited[idx] = true;
dfs(cards[idx] - 1, depth + 1); // 배열의 해당 idx-1 위치로 이동하면서 그룹 내 상자 수+1
}
🔺 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
import java.util.*;
class Solution {
static int[] cards;
static PriorityQueue<Integer> pq; // 상자 그룹 수 저장용 우선순위 큐
static boolean[] visited;
static int answer = 0; // 얻을 수 있는 최고 점수
public int solution(int[] cards) {
this.cards = cards;
pq = new PriorityQueue<>(Collections.reverseOrder()); // 리스트 크기 기준 정렬
visited = new boolean[cards.length];
for(int i = 0 ; i < cards.length ; i++) {
if(!visited[i])
dfs(i, 0);
}
if(pq.size() != 1) // 그룹이 2개 이상인 경우, 1번 그룹 수 * 2번 그룹 수
answer = pq.poll() * pq.poll();
return answer;
}
private static void dfs(int idx, int depth) {
if(visited[idx]) { // 열었던 상자인 경우
pq.add(depth); // 연 상자 갯수를 큐에 저장하고 리턴
return;
}
visited[idx] = true;
dfs(cards[idx] - 1, depth + 1); // 다음 위치로 이동하면서 그룹 내 상자 수+1
}
}
|
cs |
➕ 다른 풀이 방식
나의 추구미.. 이렇게 풀려고 했었다!!!
import java.util.*;
class Solution {
public int solution(int[] cards) {
int n = cards.length;
boolean[] visited = new boolean[n];
List<Integer> groups = new ArrayList<>(); // 각 그룹별 상자 갯수 저장
for (int i = 0; i < n; i++) {
int now = i;
int cnt = 0; // 연 상자 갯수
while (!visited[now]) {
cnt++;
visited[now] = true;
now = cards[now] - 1;
}
groups.add(cnt);
}
Collections.sort(groups, Comparator.reverseOrder()); // 상자 갯수 많은 순 내림차순 정렬
return (groups.size() == 1) ? 0 : groups.get(0) * groups.get(1);
}
}
+ 유니온파인드도 사용한 방식
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
💦 어려웠던 점
- 각 그룹 별 원소를 모두 저장하고 그 길이를 구하려고 했었다. (List<List<Integer>>) ⇒ 그냥 int형 변수를 활용해 그룹별 갯수만 저장하면 되었다. (List<Integer>)
🧐 새로 알게 된 내용
- 꼭 그릅의 모든 원소를 다 저장할 생각하지 말고, 그냥 변수 하나만 사용해 해당 그룹의 갯수를 저장하도록 하자,,,
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V |
(참고)
(Java) 프로그래머스 - 혼자 놀기의 달인
문제가 잘 이해되지 않아서 몇 번을 읽었다. 이해하고 보니 결국 연결되어 있는 노드의 개수를 저장하고 최댓값 2개를 꺼내서 곱을 반환하면 되는 문제였기에 DFS를 이용해서 풀이했다. 로직 cards
rovictory.tistory.com
'코테 > 프로그래머스' 카테고리의 다른 글
[프로그래머스/Level2] 도넛과 막대 그래프 (JAVA) (0) | 2024.03.26 |
---|---|
[프로그래머스/Level2] 배달 (JAVA) (0) | 2024.03.24 |
[프로그래머스/Level2] 광물 캐기 (JAVA) (0) | 2024.03.19 |
[프로그래머스/Level1] 공원 산책 (JAVA) (0) | 2024.03.18 |
[프로그래머스/Level3] 거스름돈 (JAVA) (0) | 2024.03.16 |