[코드트리] 아름다운 수열 - 자바(Java)

문제

https://www.codetree.ai/training-field/search/problems/beautiful-sequence/description?page=1&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

코드

N개의 정수로 이루어진 수열 A와 M개의 정수로 이루어진 수열 B를 입력받아 아름다운 수열의 개수와 시작 인덱스를 차례로 출력하는 문제다.

• 아름다운 수열 : 수열 A에서 길이가 M인 부분 수열들 중 수열 B의 각 원소들에 동일한 숫자를 더하거나 빼고 순서를 바꿔 나오는 수열을 의미 (순서를 바꾸지 않아도 아름다운 수열)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];

        // 수열 a 배열 만들기
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        int m = sc.nextInt();
        int[] b = new int[m];

        // 수열 b 배열 만들기
        for (int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }
        // 수열 b 오름차순 정렬
        Arrays.sort(b);

        // 아름다운 수열의 개수를 담을 k
        int k = 0;

        // 아름다운 수열의 시작 인덱스를 담을 리스트
        List<Integer> indexList = new ArrayList<>();

        for (int i = 0; i < a.length - m + 1; i++) {
            List<Integer> list = new ArrayList<>();

            // 수열 a의 부분 수열 만든 후 오름차순 정렬
            for (int j = i; j < m + i; j++) {
                list.add(a[j]);
            }
            Collections.sort(list);

            Set<Integer> set = new HashSet<>();
            // 부분 수열과 b의 각 자리수끼리 뺀 후 set에 담기
            for (int j = 0; j < list.size(); j++) {
                set.add(list.get(j) - b[j]);
            }

            // set의 크기가 1이면 k 증가, 시작 인덱스 담기
            if (set.size() == 1) {
                k++;
                indexList.add(i + 1);
            }
        }

        // 결과 출력
        System.out.println(k);
        for (int i = 0; i < indexList.size(); i++) {
            System.out.println(indexList.get(i));
        }
    }
}

• 자료구조, 정렬, 완전 탐색 알고리즘을 적절히 이용하면 풀 수 있다.
• 비교대상인 수열 b와 a의 부분수열을 비교할 때 오름차순 정렬한 상태로 각 원소들의 뺀 값이 모두 동일한 경우 아름다운 수열이다.
• set을 이용하여 뺀 값들을 담은 뒤, 길이가 1인 경우 아름다운 수열로 판단할 수 있다.