백준 30805번 : 사전 순 최대 공통 부분 수열 [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

사전 순 최대 공통 부분 수열 골드 4

 

📖 문제

 

삽질을 많이 한 문제

그리디 알고리즘인데 

 

처음에는 문자열로 만들어서 하다가 생각해보니 100 같은 건 더 큰 수인데 사전순으로는 매우 낮다. 

 

두번째로 A  수열의 각각의 위치에서 시작해서 LDS 탐색을 해서 여러 LDS를 얻어

B  수열에서 또 LDS각각 원소에 대해 맞는지 확인하는 식이였는데 그냥 엉터리였고, 이상한 접근법을 해서 

틀렸다.

 

A 수열에서 큰값순으로 값을 저장한다음 단순히 B 수열에서 순차적으로 찾아도 안된다.

5
1 90 100 85 5 
5
100 90 5 1 2

//answer
2
100 5

// wrong
3
100 90 5

 

A수열에서 큰 값 순으로 저장했다면

100 90 85 5 1

이렇게 저장되어있을 것이다. 

 

제일 큰 100을 고르고 그 다음 큰 수를 골라야하는데 원래 A수열에서 100보다 인덱스가 앞에 있는 90을 골라버리면 문제 부분수열 조건에 어긋나게된다. 

 

 

 

해결방법

A 수열의 값을 우선순위 큐에 저장할 때, 값과 인덱스를 함께 저장하고, 비교방식을 정의한다. 

1. 값이 클수록 우선순위가 높음 (내림차순)
2. 값이 같다면, 인덱스가 작은 쪽이 우선 (오름차순)

이렇게 구성된 A의 우선순위 큐에서 하나씩 꺼내면서,
B 수열에서 해당 값과 같은 값을 이전에 탐색한 위치 + 1 부터  순차적으로 탐색한다.

이때, 이전에 선택된 A 원소의 인덱스보다 뒤에 있는 인덱스만 유효한 후보로 간주한다.

즉, 선택된 A의 인덱스를 limitIdx로 갱신해 가며,
B에서도 값과 인덱스 조건을 동시에 만족하는 원소만 선택해 부분 수열에 포함시킨다.

이때 (탐색한 위치 + 1)를 start에 갱신한다.

 

---

 

 

🔅 문제 풀이

import java.io.*;
import java.util.*;

public class Main {

    static class Num implements Comparable<Num> {
        int value;
        int idx;

        public Num(int value, int idx) {
            this.value = value;
            this.idx = idx;
        }

        // 숫자를 내림차 순으로
        // 같다면 인덱스 오름차순으로
        @Override
        public int compareTo(Num o) {
            return this.value == o.value ? this.idx - o.idx : o.value - this.value;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] A = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int m = Integer.parseInt(br.readLine());
        int[] B = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();


        // 값이 더 큰 것 대로, 같다면 인덱스가 더 앞인 것으로
        // A 수열의 최대값 순으로 우선순위큐에 저장
        PriorityQueue<Num> Apq = new PriorityQueue<>();

        // B 수열의 최댓값 순으로 우선순위큐에 저장
        PriorityQueue<Num> Bpq = new PriorityQueue<>();

        // 큰 값 순으로 정렬해서 Apq에 담음
        for (int i = 0; i < n; i++) {
            Apq.add(new Num(A[i], i));
        }

        int start = 0; // B 배열에서 탐색 시작 위치
        int limitIdx = -1; // 이미 선택된 A 값들의 인덱스보다 앞선 값은 무시하기 위한 기준

        // A의 큰 값부터 B에서 순차적으로 대응되는 값 찾기
        while (!Apq.isEmpty() ) {
            Num nextMax = Apq.poll();

            for (int i = start; i < m; i++) {
                // 다음 큰 값이 B[i] 와 같고, 이전 선택된 최댓값의 인덱스 값보다 크다면
                if (nextMax.value == B[i] && limitIdx < nextMax.idx) {
                    Bpq.add(new Num(nextMax.value, i));

                    start = i + 1; // 탐색 범위를 다음으로 지정
                    limitIdx = nextMax.idx; // 큰 값의 인덱스를 현재 맥스값으로 갱신
                    break;
                }
            }
        }

        // 정답 작성
        StringBuilder sb = new StringBuilder();
        sb.append(Bpq.size()).append("\n");

        while (!Bpq.isEmpty()) {
            sb.append(Bpq.poll().value).append(" ");
        }

        System.out.println(sb.toString());

    }




}

 

 

 

❗ 오답노트 / 필요한 지식

1.  탐색 범위를 잘 확인하자.
2. 뭔가 설명하기 어렵다.