Always awake
[백준][16566][Python 파이썬][P5] 카드 게임 본문
문제
철수와 민수는 카드 게임을 즐겨한다. 이 카드 게임의 규칙은 다음과 같다.
- N개의 빨간색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 M개의 카드를 고른다.
- N개의 파란색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 빨간색에서 고른 번호와 같은 파란색 카드 M개를 고른다.
- 철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다.
- 철수와 민수는 고른 카드 중에 1장을 뒤집어진 상태로 낸다. 그리고 카드를 다시 뒤집어서 번호가 큰 사람이 이긴다. 이 동작을 K번 해서 더 많이 이긴 사람이 최종적으로 승리한다. 한 번 낸 카드는 반드시 버려야 한다.
철수는 뛰어난 마술사이기 때문에 본인이 낼 카드를 마음대로 조작할 수 있다. 즉, 카드를 버리고 민수 몰래 다시 들고 온다거나 민수한테 없는 카드를 내기도 한다.
민수는 뛰어난 심리학자이기 때문에 철수가 낼 카드를 알아낼 수 있다. 그래서 민수는 철수가 낼 카드보다 큰 카드가 있다면 그 카드들 중 가장 작은 카드를 내기로 했다.
K번 동안 철수가 낼 카드가 입력으로 주어진다. 그렇다면 민수가 어떤 카드를 낼지 출력하라. 단, 민수가 카드를 내지 못하는 경우는 없다고 가정한다.
입력
첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000))
다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 다르다.
다음 줄에 K개의 자연수가 주어진다. i번째 수는 철수가 i번째로 내는 카드의 번호이다. 철수가 내는 카드 역시 1 이상 N 이하이다.
출력
K줄에 걸쳐서 수를 출력한다. i번째 줄에는 민수가 i번째로 낼 카드의 번호가 출력되어야 한다.
테스트케이스
10 7 5 2 5 3 7 8 4 9 4 1 1 3 8 |
10 5 4 5 6 7 8 9 1 2 3 4 |
10 5 3 1 11 21 31 41 35 25 15 5 |
7 5 3 3 4 5 6 7 6 3 3 |
5 2 3 4 9 |
5 6 7 8 |
41 31 21 |
7 4 5 |
코드
후기
사실 예전에 도전할때 정렬 후 이분탐색으로 접근했다가 시간초과 띄운담에 한달정도 지나 클래스 5 다풀어가고 공부 많이 한 후에 다시 도전했다.
보자마자 느낀건 어 이거 공항(https://www.acmicpc.net/problem/10775) 반대버전이네? 공항은 가능한 가장 큰숫자를 넣어주면 되는거고, 얘는 가능한 가장 작은 숫자 넣어주면 되는거구나? 라는 생각은 바로 했는데
공항과 달리 이게 더 큰걸 내야하다보니 1 차이가 나고, 수가 듬성듬성 있고.. 하다보니 구현이 바로 떠오르진 않았다
그래도 일단 있는 카드들은 정렬하고, 그에 따라서 노드 번호 매기고, 그리고 철수가 뭘 내든 바로 적절한 인덱스로 갈 수 있게 idx 배열을 만들어서 해결했다.
'PS > 백준 BOJ' 카테고리의 다른 글
[백준][9048][Python 파이썬][S3] 수위 아저씨의 고민 (0) | 2023.12.13 |
---|---|
[백준][14939][Python 파이썬][P4] 불 끄기 (0) | 2023.12.13 |
[백준][17143][Python 파이썬][G1] 낚시왕 (1) | 2023.12.11 |
[백준][2887][Python 파이썬][P5] 행성 터널 (0) | 2023.12.11 |
[백준][1509][Python 파이썬][G1] 팰린드롬 분할 (0) | 2023.12.09 |