[실버 3] 11540. Competition (Java)

https://www.acmicpc.net/problem/11540

11540번: Competition

Jessy~

---

※  문제를 요약하면 아래와 같습니다.

▶ 프로그래밍 콘테스트에서 1~N까지의 문제 번호 중 Alice와 Bob이 각각 풀 수 있는 문제의 번호가 주어짐

▶ 컴퓨터는 단 1대로, Alice와 Bob이 풀이 가능한 문제 번호가 나오면 풀 수 있는 사람이 컴퓨터 사용

▶ 둘 다 풀 수 없는 번호는 Pass

▶ 문제를 다 풀면서 컴퓨터 사용자가 변경 되는 최소 경우의 수 출력

▶ Input : 첫번째 줄에 문제의 갯수 N, Alice가 풀 수 있는 문제의 갯수 A, Bob이 풀 수 있는 문제의 갯수 B,

                 두번째 줄에 Alice가 풀 수 있는 문제의 번호, 세번째 줄에 Bob이 풀 수 있는 문제의 번호 입력

▶ Output : 컴퓨터 사용자가 변경 되는 최소 경우의 수 출력

---

◈ Input - 1

5 2 3
2 4
1 5 3

◈ Output - 1

4

◈ Input - 2

4 3 3
1 2 3
2 3 4

◈ Output - 2

1

◈ Input - 3

4 3 3
1 3 4
4 3 1

◈ Output - 3

0

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 문제의 번호 범위는 1~10^9 까지로 완전 탐색 시 O(10^9) > 1초 == 시간초과

▶ 문제의 번호를 HashMap의 Key로 입력 받고, Value값은 Alice의 번호는 1, Bob의 번호는 2, 둘 다 가능이면 3으로 저장

▶ HasyMap의 Key를 List로 받은 뒤 오름차순 정렬, 사용자가 변경될 때마다 카운트하는 탐색 진행

    1. 첫 사용자 값이 1이나 2가 될 때 까지 탐색 ( 백준 2% 반례,,)

    2. 이후 List에 저장된 Key값으로 차례대로 HashMap의 Value를 호출

    3. 사용자 값이 3이 나오지 않고 이전 사용자 값과 달라질 경우 마다 카운트, 사용자 값 변경

            ex 1->2, 2->1 일 경우 사용자 값 변경 후 카운트, 1->3, 2->3일 경우 탐색 진행

▶ 스위치 될 때 마다 카운트된 값 출력

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(bReader.readLine());
		int N = Integer.parseInt(st.nextToken());
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());

		HashMap<Integer, Integer> mapProbs = new HashMap<>();
		// Alice 만 가능하면 1
		// Bob 만 가능하면 2
		// 둘다 되면 3

		// Alice first
		st = new StringTokenizer(bReader.readLine());
		for (int i = 0; i < A; i++) {
			int nNum = Integer.parseInt(st.nextToken());
			mapProbs.put(nNum, 1);
		}

		// BOB
		st = new StringTokenizer(bReader.readLine());
		for (int i = 0; i < B; i++) {
			int nNum = Integer.parseInt(st.nextToken());
			if (mapProbs.get(nNum) == null)
				mapProbs.put(nNum, 2);
			else
				mapProbs.put(nNum, 3);
		}

		// Map의 Key들을 리스트로 모아
		List<Integer> keyList = new ArrayList<>(mapProbs.keySet());
		Collections.sort(keyList);

		int nOld = 0;
		int nSwitch = 0;

		// Old값을 처음으로 정의
		int nIndex = 0;
		nOld = mapProbs.get(keyList.get(nIndex));
		while (nOld == 3 && nIndex < keyList.size()) {
			nOld = mapProbs.get(keyList.get(nIndex++));
		} 
		
		// 사용자의 값이 3이 아니고 이전 Key값과 다르다
		for (int i = nIndex; i < keyList.size(); i++) {
			if (nOld != mapProbs.get(keyList.get(i)) && mapProbs.get(keyList.get(i)) != 3) {
				nOld = mapProbs.get(keyList.get(i));
				nSwitch++;
			}
		}

		bWriter.write(String.valueOf(nSwitch));
		bWriter.close();
	}

}

---

Good Luck! (피드백 감사합니다!)