전설의 야바위꾼 일우는 Shell Game으로 야바위를 한다. Shell Game은 다음과 같은 절차로 진행된다. 1. 진행자가 N개의 컵을 일렬로 놓고, 그 중 X번째 컵에 공을 숨겨둔다. 2. 임의의 서로 다른 두 컵의 위치를 맞바꾼다. 이 항목을 K번 수행한다. * 만약, 공을 숨겨둔 컵을 움직인다면 공도 그 컵을 따라서 움직인다. 3. 참가자는 몇 번째 컵에 공이 숨겨져 있는지 추측한다. 4. 그 컵에 공이 숨겨져 있다면 참가자가, 그렇지 않다면 진행자가 이긴다.
수혁이는 Shell Game을 잘하고 싶다. 하지만, 일우가 진행자라면 무슨 수를 써도 이길 수 없어 수혁이는 일우의 사기도박을 의심하고 있다. 현재 우리는 수혁과 일우가 진행한 Shell Game의 모든 기록을 입수했다. 이를 바탕으로, 일우가 사기도박을 하지 않았다면 공이 몇 번째 컵에 있는지 알려주는 프로그램을 작성하자.
입력
첫째 줄에 N (3 ≤ N ≤ 200,000), X (1 ≤ X ≤ N), K (1 ≤ K ≤ 100,000)가 공백으로 구분되어 주어진다. 둘째 줄부터 K개의 줄에는 순서대로 바꾼 두 컵의 위치 Ai, Bi (1 ≤ Ai, Bi ≤ N, Ai ≠ Bi)가 공백으로 구분되어 주어진다. 주어지는 모든 입력은 정수다.
출력
일우가 사기도박을 하지 않았다면, 공이 몇 번째 위치의 컵에 있어야 하는지 정수로 출력하시오.
예제 입력/출력
예제 입력
예제 출력
3 2 4 1 3 3 2 3 1 2 3
1
2번째 맞바꿈에서 공은 3번째 위치로 가게 된다. 3번째 맞바꿈에서 공은 1번째 위치로 가게 된다.
알고리즘 분류
● 구현 ● 시뮬레이션
소스코드
package Lv1_Bronze;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* @author HanHoon
* @category 구현, 시뮬레이션
* https://www.acmicpc.net/problem/20361
*/
public class BOJ_B3_20361_일우는_야바위꾼 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder str = new StringBuilder();
StringTokenizer st = null;
// T : 테스트케이스 개수, br.readLine()을 int형으로 변경해준다., 범위 확인
int T = 1;
if(!(1<=T&&T<=10)) { System.out.println("1<=T<=10 범위를 초과했습니다."); return;}
// T만큼 반복
for (int testcase = 1; testcase <= T; testcase++) {
// 테스트 케이스 별 출력
// 라인벌로 space 기준으로 토큰으로 나눔
st = new StringTokenizer(br.readLine(), " ");
// 토큰값을 int값으로 변경
// N : 종이컵의 수, 범위 확인, cup 배열 생성(초기값은 false)
int N = Integer.parseInt(st.nextToken());
if(!(3<=N&&N<=200000)) { System.out.println("3<=N<=200,000 범위를 초과했습니다."); return;}
boolean[] cup = new boolean[N];
// X : 간식의 위치, 범위 확인, X번째 값은 true;
int X = Integer.parseInt(st.nextToken());
if(!(1<=X&&X<=N)) { System.out.println("z<=X<=" + N + "범위를 초과했습니다."); return;}
cup[X-1] = true;
// K : 컵의 위치를 바꾸는 횟수, 범위 확인
int K = Integer.parseInt(st.nextToken());
if(!(1<=K&&K<=100000)) { System.out.println("1<=K<=100,000 범위를 초과했습니다."); return;}
// K번의 컵 위치 변경 입력
for (int i = 0; i < K; i++) {
// 임시값
boolean tmp;
st = new StringTokenizer(br.readLine(), " ");
// 컵 A와 B의 위치를 바꿈
int A = Integer.parseInt(st.nextToken())-1;
int B = Integer.parseInt(st.nextToken())-1;
tmp = cup[A];
cup[A] = cup[B];
cup[B] = tmp;
}
for (int i = 0; i < cup.length; i++) {
// 간식이 들어있는 컵을 찾음
if(cup[i] == true) {
// 테스트 케이스 별 결과값 출력
str.append(i+1).append("\n");
break;
}
}
}
// stringbuilder에 저장된 toString 출력
System.out.print(str);
// BufferedReader 종료
br.close();
}
}
댓글