BOJ_20952_게임 개발자 승희 (Java)

[Gold IV] 게임 개발자 승희 - 20952

문제 링크

성능 요약

메모리: 56632 KB, 시간: 696 ms

분류

구현, 수학

제출 일자

2025년 1월 4일 14:40:17

문제 설명

승희는 최근 369 게임에 푹 빠졌다. 369 게임을 하던 승희는 놀라 자빠질 수밖에 없었다. 369 게임을 잘하는 자기 자신이 너무 대견하였기 때문이다. 369 게임이 식상해진 승희는 369 게임을 변형한 71421 게임을 개발하였다. 369 게임에서는 3, 6, 9가 들어가는 수에 손뼉을 치지만, 71421 게임에서는 7의 배수에 손뼉을 친다. 승희는 71421 게임을 널리 퍼트리기로 결심하였다.

71421 게임은 최근 대학생들 사이에서 큰 인기를 끌고 있다. 369 게임에 이어 71421 게임도 식상해진 승희는 수열을 이용한 새로운 게임을 개발하였다.

승희의 수열 게임은 혼자서 즐길 수 있는 재미난 게임이다. 시작하기에 앞서 길이가 N인 수열 A와 길이가 M인 수열 B를 준비한다. 이후 수열 A에 대하여 M번의 연산을 수행한다. i(1 ≤ i ≤ M)번째 연산은 수열 A의 모든 원소에 B_i를 더한 후 7의 배수인 원소들을 제거하는 연산이다. 단, 연산을 수행한 결과 수열 A의 모든 원소가 제거된다면 해당 연산은 수행하지 않는다.

수열 A와 B가 주어졌을 때, M번의 연산을 수행한 결과를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수열 A의 길이 N과 수열 B의 길이 M이 주어진다.

두 번째 줄에 N개의 정수 A₁, A₂, ..., A_N이 주어진다.

세 번째 줄에 M개의 정수 B₁, B₂, ..., B_M이 주어진다.

모든 입력은 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 M번의 연산을 수행한 후 수열 A의 길이 K를 출력한다.

두 번째 줄에 K개의 정수 A₁, A₂, ..., A_K를 공백으로 구분하여 출력한다. 답이 매우 커질 수 있으므로 10⁹ + 7로 나눈 나머지를 출력한다.

문제 풀이

재밌는 문제! 매번 모든 수에 대해 연산을 수행하고 7로 나누어 확인하는 것은 비효율적이므로, 다음과 같은 전략을 사용했다.

나머지 기반 그룹화

• 수열 A의 각 원소를 7로 나눈 나머지를 기준으로 그룹화
• 0부터 6까지 총 7개의 그룹이 생성됨
• 각 그룹에는 해당 나머지를 가진 원소들이 저장

누적 합 효율적으로 관리

1. 나머지의 합(sumMod)
   • 지금까지 더해진 모든 수를 7로 나눈 나머지
   • 다음 연산에서 어떤 그룹이 7의 배수가 될지 예측하는데 사용
2. 실제 누적 합(actualSum)
   • MOD(10^9 + 7)로 나눈 나머지를 유지
   • 최종 결과 계산에 사용
3. 제거될 그룹 계산

(r + x) % 7 = 0

1. 원본 순서 유지
   • 각 수의 원래 위치(originalIndex) 저장
   • 최종 출력 시 원래 순서대로 정렬하기 위해 사용

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	
	class Number {
	    long value;
	    int originalIndex;
	    Number(long value, int originalIndex) {
	        this.value = value;
	        this.originalIndex = originalIndex;
	    }
	}
	
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, M;
	static ArrayList<Number>[] num;
	static final long MOD = 1000000007;
	static long size;
	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		size = N;
		num = new ArrayList[7];
		for(int i=0; i<7; i++) {
			num[i] = new ArrayList<Number>();
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			long n = Long.parseLong(st.nextToken());
			int m = (int) n % 7;
		    num[m].add(new Number(n % MOD, i));
		}
		
		long sumMod = 0; // 7로 나눈 나머지 ( 계속 추가됨 )
		long actualSum = 0;  // 실제 더할 값

		st = new StringTokenizer(br.readLine());
		for(int i=0; i<M; i++) {
			long l = Long.parseLong(st.nextToken());
			
			long nextSumMod = ((sumMod + (l % 7)) % 7);
			
			//제거될 인덱스
			int idx = (7 - (int) (nextSumMod))%7;
			int l_size = num[idx].size();
			if(size - l_size == 0) {
				continue;
			}
			else {
				size -= l_size;
				num[idx].clear();
				actualSum = ((actualSum % MOD) + (l % MOD)) % MOD;
		        sumMod = nextSumMod;
			}
		}
		
		sb.append(size + "\n");
		
		ArrayList<Number> result = new ArrayList<>();
		for(int i = 0; i < 7; i++) {
		    for(Number n : num[i]) {
		        result.add(new Number(
		            ((n.value % MOD) + (actualSum % MOD)) % MOD, 
		            n.originalIndex
		        ));
		    }
		}

		// originalIndex 기준으로 정렬
		Collections.sort(result, (a, b) -> a.originalIndex - b.originalIndex);


		for(Number n : result) {
		    sb.append(n.value + " ");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}