자바 백준 1920번 문제 : 수 찾기

문제 출처 : https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

문제 :

 

풀이 :

이분 탐색을 이용하면 해결될 문제지만

왠지 투포인터 알고리즘을 사용해 풀어보고 싶었다.

투포인터 알고리즘을 사용하기 위해선 mArr와 nArr 둘 다 정렬되어 있어야 하는데

문제는 mArr를 정렬시켜버리면 기존 인덱스(위치)도 섞여서 출력 시 1이 출력되는 위치도 변한다는 것이다.

 

그럼 HashMap을 사용해 기존 인덱스(위치)를 key로 저장하고 값을 value로 저장한 다음

LinkedHashMap을 사용해 value값을 기준으로 정렬해주면

순서가 변해도 기존 위치를 기억(key값이 기존 위치)해서 출력 시 기존 위치에 해당하는 수가 존재할 경우

해당 위치의 배열을 1로 만들면 해결된다는 생각이 들었다.

 

소스코드 :

import java.util.*;
import java.io.*;
class Main {
	// comparator 이용해 value 기준으로 map 정렬하는 함수 작성
	public static LinkedHashMap<Integer, Integer> sortMapByValue(Map<Integer, Integer> map) {
        List<Map.Entry<Integer, Integer>> entries = new LinkedList<>(map.entrySet());
        Collections.sort(entries, (o1, o2) -> o1.getValue().compareTo(o2.getValue()));
        LinkedHashMap<Integer, Integer> result = new LinkedHashMap<>();
        for (Map.Entry<Integer, Integer> entry : entries) {
            result.put(entry.getKey(), entry.getValue());
        }
        return result;
    }

	public StringBuilder solution(int n, int[] nArr, int m, int[] mArr) {
		StringBuilder sb = new StringBuilder();
		// nArr 오름차순 정렬하기
		Arrays.sort(nArr);
		// 답 출력할 mArr 크기의 배열
		int[] ansArr = new int[m];
		// mArr 정렬 전 인덱스 기억하기 위해 HashMap 생성
		// <Index, Value>
		HashMap<Integer, Integer> map = new HashMap<>();
		for(int i=0; i<m; i++) {
			map.put(i, mArr[i]);
		}
		// map을 value 기준으로 정렬한 후 sortMap에 저장
		Map<Integer, Integer> sortMap = sortMapByValue(map);
		Iterator<Map.Entry<Integer, Integer>> entries = sortMap.entrySet().iterator();
		int p1 = 0;
		int p2 = 0;
		int p2Value = 0;
		boolean next = true;
		Map.Entry<Integer, Integer> entry;
        while(true) {
			// mapList 모두 순회하거나 nArr 모두 순회할 경우 반복문 종료
			if (entries.hasNext() == false || p1 >= n) {
				break;
			}
			// nArr[p1] == p2Value일 경우와 nArr[p1] > p2Value일 경우 다음 entry 가져오기
			if (next == true) {
				entry = entries.next();
				p2 = entry.getKey();
				p2Value = entry.getValue();
				next = false;
			}
			if (nArr[p1] == p2Value) {
				ansArr[p2] = 1;
				next = true;
			}
			else if (nArr[p1] < p2Value) {
				p1++;
			}
			else {
				next = true;
			}
        }
		for(int i=0; i<m; i++) {
			sb.append(ansArr[i]).append("\n");
		}
		return sb;
	}
	public static void main(String[] args) throws IOException {
		Main T = new Main();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] nArr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) nArr[i] = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(br.readLine());
		int[] mArr = new int[m];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<m; i++) mArr[i] = Integer.parseInt(st.nextToken());
		System.out.println(T.solution(n, nArr, m, mArr));
	}
}