35470번 - 카드 섞기 게임 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 71 | 45 | 44 | 91.667% |
문제
달구와 포닉스가 알파벳 소문자가 하나씩 적혀있는 $N$개의 카드로 게임을 하고 있다.
- 달구가 카드를 아무렇게나 섞은 뒤, 맨 위 카드부터 적힌 알파벳을 순서대로 이어 만든 문자열을 포닉스에게 준다.
- 포닉스도 같은 방식으로 문자열을 만들어서 달구에게 준다.
- 문자열을 사전 순서로 비교했을 때 더 앞에 오는 문자열을 갖고 있는 사람이 이긴다.
달구는 어떻게 한 건지 포닉스를 3판 연속으로 이겨버렸고, 기세등등한 달구는 윤이에게도 대결을 신청했다. 게임에서 이기기 위해 달구의 전략을 분석하던 윤이는 달구가 다음과 같은 방식으로 카드를 섞는 과정을 $K$번 반복하는 것을 관찰했다.
카드를 한 번 섞을 때, $1$번째 카드는 항상 다음에 $A_1$번째 카드가 되고, $2$번째 카드는 항상 다음에 $A_2$번째 카드가 되고, $\cdots$ $N$번째 카드는 항상 다음에 $A_N$번째 카드가 된다. 예를 들어서, $N=4,A_1=2,A_2=4,A_3=3,A_4=1$이면, abcd를 한 번 섞으면 dacb가 되고, 한 번 더 섞으면 bdca가 된다.
이에 윤이는 달구가 위 과정을 정확히 $K$번 반복하여 섞어서 주는 결과가 사전 순으로 가장 앞서도록 몰래 카드를 미리 섞어 두려고 한다. 카드에 적힌 알파벳의 목록, $K$, 그리고 $A_1,A_2,\cdots A_N$이 주어질 때, 윤이가 몰래 섞어둘 카드의 배열을 구하는 프로그램을 작성해 보자!
입력
첫째 줄에 두 정수 $N$과 $K$가 공백으로 구분되어 주어진다. $(1\le N\le 100\, 000;1\le K\le 10^9)$
둘째 줄에 카드에 적힌 알파벳의 목록 $S$가 주어진다. $S$는 알파벳 소문자로 이루어진 길이가 $N$인 문자열이다.
셋째 줄에 서로 다른 $N$개의 정수 $A_1,A_2,\cdots ,A_N$이 공백으로 구분되어 주어진다. $(1\le A_i\le N)$
출력
첫째 줄에 윤이가 몰래 섞어둘 카드의 배열을 위에서부터 순서대로 한 줄로 출력한다.
예제 입력 1
4 2 udpc 2 4 3 1
예제 출력 1
ucpd
예제 입력 2
8 19 ddccbaaa 1 8 2 7 3 6 4 5
예제 출력 2
aacddcba
예제 입력 3
5 7 asdfg 1 2 3 4 5
예제 출력 3
adfgs
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호