Line Japan fresh grad online test문제입니다. (English person welcome!)
문제는 cup shuffle 문제이구요. 예를 들어 한국에서 야바위(?) 라고 하나? 컵에 물건 넣어 놓고 돌려서 어느 컵에 물건 있나 맞추는 게임이요.
cups = [1,2,3] 이라고 하면 컵은 총 세게 initial position은 무조건 1번 컵입니다.
그리고 shuffle = [(1,2),(2,3)] 뭐 이런 식인데요 (1,2)라는 건 1번과 2번컵을 바꾼다는 겁니다.
그래서 최종위치를 알아 맞추는 function을 만드는 거구요. k라는 변수가 또 있는데 k는 shuffle을 k번 반복한다는 겁니다.
예를 들어 k=1인 경우라면 위의경우 최종위치는 3번컵입니다.

이경우는 뭐 딱히 생각나는게 없어서 Brute Force로 전부 iteration하면서 컵의 위치를 찾았구요. k가 큰경우는 원래 위치로 언제 돌아 오나를 찾아서 k를 줄였습니다. 예를 들어 k=10이고 original position에 3번 만에 온다고 하면 k%=3으로 재 정의 해서 풀었어요.

그랬더니, correctness는 만점나오고 midium문제는 반만 해결하고 나머지 반과 large문제들은 time limit이 나왔습니다.
이경우에 효과적인 방법이 있을까요?

답변감사합니다!

셔플에는 어떤 규칙같은거 없나요? 항상 순차적으로 (1,2),(2,3),(3,4)로 가나요?
time limit도 어느정도 requirement 를 알아야 마춰줄텐데 무조건 제일 빠른걸루 만들라는 건가요?

순차적이 아니구 단순한 얘기입니다 [(3,2),(1,2)(2,1)] 이렇게 될수도 있어요 ㅎㅎ

k%=3 이후에 다시 Brute Force로 하신건 가요 아니면 각 attempt 에 값을 기억해서 바로 답을 낸건가요?

일단 저는 k==1인 경우에 알고리즘을 우선 만들었구요. 그다음에 이를 반복해서 원래 포지션으로 돌아오는 k를 찾았어요. 3이라는건 예일 뿐이구요. 원래 포지션으로 돌아오는 횟구가 235라고 하고 k==1000000이라고 하면 k%=235로 재 정의 해서 풀었어요. 이 방법을 쓰기 전까지는 small problem만 통과 시켰는데 이거 하고 나서는 medium까지는 통과 시키더라구요.

쓰신 것보다 빠르게 할라면, 셔플을 한 번 돌리고 나서의 맵핑을 저장하고 맵핑을 이용해서 k번 돌리면 되지 않을까요? O(n + k) 로

말씀인즉, 셔플 알고리즘을 한번 돌렸을때 위치를 dictionary에 저장하면서 돌리라는 말씀이신가요???

윗분 말대로, 셔플을 저장할 때 시작점, 끝점 있는 링크드리스트같은 데이터 구조로 셔플을 짓고, 반복이 가능하니까 양 끝을 붙이십시오. 드럼통 모양처럼.

그럼 실패에 줄이 감긴 것 처럼 서로 이어지게 되는데, 이것으로 Len(suffle)안에 임의의 k에 대한 모든 끝점을 알 수 있습니다

아 넵 감사합니다. 말씀이 셔플 결과 값들을 다 연결 시키라는 거죠??