카드를 섞는데 원하는 답이 안 나올 수도 있다.
그 때 언제 카드 섞는걸 멈춰야할까?사실 이 문제는 인덱스와 원소값이 너무 헷갈리게 다가와서 이해하는데 힘들었던 문제이다.
주석을 적어가며 천천히 생각해보니 좀 더 이해가 잘 됐던 문제
제출코드
파이썬
import sys
input = sys.stdin.readline
# 어떻게 끊을까?
N = int(input())
P = list(map(int, input().split()))
S = list(map(int, input().split()))
cards = [i for i in range(N)] # cards[i] 번호의 카드는 i%3 플레이어한테 간다.
# i 번호의 카드는 P[i] 한테 가도록 하고 싶다.
def shuffle():
global cards
t = [-1] * N
for i in range(N):
t[S[i]] = cards[i]
cards = t
def check():
for i in range(N):
# x 번호의 카드는 P[x] 한테 가도록 하고 싶다.
# 지금 x번호의 카드는 i%3 한테 돌아간다.
x = cards[i]
if P[x] != i%3:
return False
return True
def convert():
v = 0
for i in range(N):
v += 10**i * cards[i]
return v
dd = {}
cnt = 0
while check() == False:
k = convert()
if dd.get(k) == None:
dd[k] = 1
else:
cnt = -1
break
cnt += 1
shuffle()
print(cnt)자바
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N;
static int[] P;
static int[] S;
static int[] cards;
static int[] originalCards;
static int cnt = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
P = new int[N];
S = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
P[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
S[i] = Integer.parseInt(st.nextToken());
}
cards = new int[N];
for (int i = 0; i < N; i++) {
cards[i] = i;
}
originalCards = cards.clone();
while (check() == false) {
if (cnt != 0 && Arrays.equals(cards, originalCards)) {
cnt = -1;
break;
}
cnt += 1;
shuffle();
}
System.out.println(cnt);
}
public static void shuffle() {
int[] t = new int[N];
for (int i =0; i < N; i++) {
t[S[i]] = cards[i];
}
cards = t.clone();
}
public static boolean check() {
for (int i = 0; i < N; i++) {
int x = cards[i];
if (P[x] != i%3) {
return false;
}
}
return true;
}
}접근방법
생성한 변수를 하나하나 살펴보자
cards
현재 카드의 상태를 리스트로 나타냈다. 각 카드는 고유번호를 가지고 있다. ( =cards[i] )
총 3명의 사람 (0번, 1번, 2번 플레이어)에게 카드가 차례로 나눠지기 때문에
i%3번의 플레이어에게 cards[i]번호의 카드가 주어진다고 생각하면 되겠다.
shuffle()
카드를 S 규칙에 따라 섞는다.
문제 조건에 따라 i번째 위치에 있던 카드는 S[i]번째 위치로 이동 하도록 만들었다.
check()
현재 카드 상태가 P를 만족하는지 확인한다.
문제에서 P[i]의 의미는 맨 처음 i번째있던 카드를 P[i] 플레이어게 주어져야한다는 뜻이다. 섞으면서 맨 처음 i번째 카드가 어떤 카드인지 모르기에 처음 cards를 만들때 인덱스 값으로 번호를 부여했다.
즉, "번호가 i인 카드가 P[i]번 플레이어한테 주어져야 한다." 는 의미다. ... 1
cards[i] 번호의 카드는 처음 의도대로 i%3번의 플레이어에게 주어진다. ... 2
1번과 2번을 조합해보면 x = cards[i]라 했을 때
x번호의 카드는 P[x]번 플레이어한테 주어져야 하고, ... 1
현재 카드 상태로는 x번호의 카드는 i%3번의 플레이어에게 주어지므로 ... 2
P[x] == i%3를 모든 i에 대해 만족한다면 P상태를 만족하는 것이 된다.
convert()
일정한 규칙 S에 따라 섞이기 때문에 이전에 한번 나온 카드의 상태가 한번 더 나올때까지 P를 만족하지 못했다면 몇 번을 섞어도 P를 만족할 수 없다는 얘기가 된다.
지금까지 나온 상태를 유니크하게 만들기 위한 가장 쉬운 방법은 그냥 배열그대로 붙이는 것이라고 생각했고 convert()는 그 상태값을 만들기 위한 함수다.
생각해보니...
java로 한번 더 풀어 보면서 생각난 건데 굳이 convert()로 만들고 이를 딕셔너리에 저장해서 비교할 필요가 없다.
그냥 맨 처음 상태의 cards를 기록해 두고 섞었을때 한번 더 맨 처음 cards가 나온다면 P를 만족하지 못한채 무한 루프에 들어간다고 판단하고 끊어주면 될 것 같다.
