프로그래머스 - 혼자 놀기의 달인
프로그래머스 2단계 혼자 놀기의 달인을 풀어보겠습니다.
※ 해당 문제는 문제 설명부터 읽는 것을 추천합니다!!
문제 설명
프로그래머스에 적혀있는 문제 설명 중, '필요 없을 것 같은 설명'이 응시자가 문제를 이해함에 있어, 방해 요소로 작용할 것 같아 문제를 풀기 좋게 '필요 없을 것 같은 부분'은 걷어내고 문제를 쉽게 재해석해서 설명해드리겠습니다.
- 범희는 혼자 할 수 있는 게임을 생각해냈습니다.
- 카드 더미에는 1부터 n까지의 숫자가 적혀있는 n장의 숫자 카드가 있습니다.
-> 카드 더미에 중복되는 숫자 카드는 없습니다.
-> 카드 더미에 숫자 카드는 셔플된 상태로 들어가게 됩니다.
-> 배열 'cards'는 카드 더미입니다.
- 범희는 카드 더미에서 아직 뽑지 않은 카드 중에서, 맨 앞에 있는 카드를 가져옵니다.
-> 카드에 적혀있는 숫자를 'a'라고 하겠습니다.
- 범희는 카드 더미에서 a 번째 카드를 가져옵니다.
-> 카드에 적혀있는 숫자를 'b'라고 하겠습니다.
- 범희는 카드 더미에서 b 번째 카드를 가져옵니다.
- 4~5번을 반복하다가 이미 뽑은 숫자 카드가 다시 나온다면, 반복을 중단합니다.
-> 반복을 중단할 때까지 카드를 뽑은 횟수를 count 합니다.
- 모든 카드를 뽑을 때까지, 3~6번을 반복합니다.
-> 필자는 3~6번까지의 과정을 '루틴'이라고 하겠습니다.
- 루틴은 최소 2번 반복해야하며 첫 번째 루틴에서 모든 카드를 뽑았을 경우,
두 번째 루틴의 카드를 뽑은 횟수는 '0'입니다.
- 범희의 루틴 중, 가장 많은 카드를 뽑은 두 가지의 루틴의 카드를 뽑은 횟수를 곱하여 반환합니다.
문제를 전부 이해했는데도 테스트 케이스 2번에서 실패한다면, cards가 아래와 같을 때, 첫 번째 루틴에서 모든 카드를 뽑고 두 번째 루틴에서 카드를 뽑지 못하는 상황에서 '0'을 반환하는지 확인해 보세요!!
cards = [ 2, 3, 4, 5, 6, 7, 8, 9, 10, 1 ]
반환값 = 0
예시
입출력 예시를 그림으로 설명하겠습니다.
풀이
※ 제가 푼 방법보다 더 좋은 방법으로 풀 수 있기 때문에, 참고용으로 봐주셨으면 좋겠습니다.
-
해당 카드를 뽑은 적이 있는지 확인하는 'boolean 타입 배열'을 만듭니다.
-> boolean 타입 배열의 이름을 'drawnCardsArr'라고 하겠습니다.
-> 배열의 길이는 'cards'와 같습니다.
-
범희가 이번 루틴에 뽑은 카드의 개수를 세는 정수형 변수 'count'와 count를 저장하는 '리스트'를 만듭니다.
-
반복문을 이용하여 카드 뭉치에서 '뽑지 않은 카드'를 가져오고, 'drawnCardsArr[i]'의 값을 바꿔주고, count를 1 증가시킵니다.
-> 뽑지 않은 카드에 적혀있는 숫자는 'cards[i]'입니다.
-
'cards[i]'번째에 있는 카드를 이미 뽑았다면, 이번 루틴을 종료하고 'count'를 리스트에 저장합니다.
-
'cards[i]'번째에 있는 카드가 처음 뽑는 카드라면, 카드를 가져오고 'drawnCardsArr[이번에 뽑은 카드]'의 값을 바꿔줍니다.
-
카드 뭉치에서 모든 카드를 뽑을 때까지, 3~5번의 과정을 반복합니다.
코드
import java.util.ArrayList;
import java.util.Comparator;
class Solution {
boolean[] drawnCardsArr; // 카드를 뽑은 적이 있는지 저장하는 배열
int[] cards; // 카드 뭉치 배열
int count; // 이번 루틴에서 뽑은 카드 수를 저장하는 변수
public int solution(int[] cards)
{
this.cards = cards; // 재귀 함수를 사용하므로 cards를 전역 변수로 만듬
drawnCardsArr = new boolean[cards.length];
ArrayList<Integer> list = new ArrayList<>(); // count를 저장하는 리스트
// 카드 뭉치의 카드의 개수만큼 반복
for(int i = 0; i < cards.length; i++)
{
// 뽑은 적이 있는 카드면 뽑지 않고 다음 카드를 가져옴
if(drawnCardsArr[i]) continue;
count = 1; // 이번 루틴에서 뽑은 카드 개수 + 1;
drawnCardsArr[i] = true;
openBox(cards[i]-1); // 루틴 시작 (재귀 함수) '-1'한 이유는 'index'는 0부터 시작하기 때문
list.add(count); // 이번 루틴이 끝났으므로 리스트에 count 저장
}
// 리스트에 저장된 count를 내림차순으로 정렬
list.sort(Comparator.reverseOrder());
// 최소 루틴의 횟수는 2회므로, 루틴이 1회인 경우에는 0을 반환
return list.size() == 1 ? 0 : (list.get(0) * list.get(1));
}
// 재귀 함수
public void openBox(int index)
{
// 이미 뽑은 적이 있는 카드라면 함수를 종료
if(drawnCardsArr[index]) return;
drawnCardsArr[index] = true;
count++;
openBox(cards[index]-1); // 카드에 적혀 있는 숫자의 위치에 있는 카드 가져오기
}
}테스트
-
'static class Solution'에 본인이 적은 코드를 복붙하여 정답 코드와 확인해 틀렸을 경우, 주어진 'order'와 '본인의 코드의 반환값', '정답 코드의 반환값'을 출력해주는 코드입니다.
-
원래 문제에서 주어진 'cards.length'는 2~100까지지만, 코드의 오류를 잡기에는 작은 범위가 좋을 것 같아서 'card.length'를 2~10까지의 범위로 줄였습니다. cards.length를 100까지 늘리려고 한다면, class Source에서 setCards() 메소드의 'length = random.nextInt()의 범위'를 바꾸어 주시면 됩니다.
import java.util.*;
public class Test {
static class Solution {
// 본인 코드 복붙!
}
static class Answer {
boolean[] drawnCardsArr;
int[] cards;
int count;
public int solution(int[] cards) {
this.cards = cards;
drawnCardsArr = new boolean[cards.length];
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < cards.length; i++)
{
if(drawnCardsArr[i]) continue;
count = 1;
drawnCardsArr[i] = true;
openBox(cards[i]-1);
list.add(count);
}
list.sort(Comparator.reverseOrder());
return list.size() == 1 ? 0 : (list.get(0) * list.get(1));
}
public void openBox(int index)
{
if(drawnCardsArr[index]) return;
drawnCardsArr[index] = true;
count++;
openBox(cards[index]-1);
}
}
static class Source {
Random random;
int length;
int[] cards;
public Source()
{
random = new Random();
}
public void setCards()
{
length = random.nextInt(9)+2;
cards = new int[length];
for(int i = 0; i < cards.length; i++)
{
int num;
do {
num = random.nextInt(length)+1;
} while (!chkDuplicatedCard(num));
cards[i] = num;
}
}
public boolean chkDuplicatedCard(int num)
{
for(int card : cards)
{
if(num == card)
return false;
}
return true;
}
}
public static void main(String[] args) {
Source source = new Source();
Answer answer = new Answer();
Solution solution = new Solution();
for(int i = 0; i < 100; i++)
{
source.setCards();
int a = answer.solution(source.cards);
int s = solution.solution(source.cards);
if(a == s) continue;
System.out.println("주어진 order: "+Arrays.toString(source.cards));
System.out.println("정답 코드 답: "+a);
System.out.println("내 코드 답: "+s+"\n");
}
}
}#썸네일 제작 : 미리 캔버스
#예시 그림 제작 : 미리 캔버스
