[programmers] 혼자 놀기의 달인

문제
https://school.programmers.co.kr/learn/courses/30/lessons/131130

프로그래머스

 

---

< 혼자 놀기의 달인 >

 

문제 풀이 (Java)

import java.util.*;

class Solution {
	public int solution(int[] cards) {
		int answer = 0;

		ArrayList<Integer> list = new ArrayList<>();

		for (int i = 0; i < cards.length; i++) {
			if (cards[i] == -1) {
				continue;
			}
			int idx = i;
			int cnt = 0;
			while (cards[idx] != -1) {
				int temp = cards[idx] - 1;
				cards[idx] = -1;
				idx = temp;
				cnt += 1;
			}
			list.add(cnt);
		}

		Collections.sort(list, Collections.reverseOrder());

		if (list.size() >= 2) {
			answer = list.get(0) * list.get(1);
		}
		return answer;
	}
}

 

cards를 살펴보며 값이 -1이라면 이미 그룹에 속한 것이므로 넘어가고, -1이 아니라면 새로운 그룹을 구한다. 현재 위치를 idx에 저장하고 cards[idx]가 -1이 아닐 때까지 다음 과정을 반복한다. 

 

1) temp에 다음 위치 저장

2) 현재 위치에 해당하는 값을 -1로 저장

3) idx에 다음 위치 저장

4) cnt+1

 

한 그룹을 다 구했다면 ArrayList에 cnt를 저장한다. 

 

최종 ArrayList를 내림차순으로 정렬 후 ArrayList의 크기가 2 이상이라면 (첫 번째 값) * (두 번째 값)을 구해 반환한다. ArrayList의 크기가 2보다 작다면 0을 반환한다.

---

---

 

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges