[D3] n1225_암호생성기

package com.ssafy.algo.w0805.n1225_암호생성기;

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.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {

	public static void main(String[] args) throws IOException {
		System.setIn(new FileInputStream("src\\com\\ssafy\\algo\\w0805\\n1225_암호생성기\\input (4).txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		for(int t=1;t<=10;t++) {
			int test = Integer.parseInt(br.readLine());
			
			Queue <Integer> q = new LinkedList<>();
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
			final int N = 8;

			for(int i=0;i<N;i++) {
				q.offer(Integer.parseInt(st.nextToken()));
			}
			
			int temp = 99999;
			int cnt = 0;
			final int CYCLE = 5;
			
			while(true) {
				++cnt;
				temp = q.poll()-cnt;
				if(cnt==CYCLE) cnt=0;
				if(temp<=0) {
					q.offer(0);
					break;
				} else {
					q.offer(temp);
				}
			}
			
			bw.append("#"+t+" ");
			while(!q.isEmpty()) {
				bw.append(q.poll()+" ");
			}
			bw.append("\n");
			
			bw.flush();
		}
		bw.close();
	}

}

 

input1

1
9550 9556 9550 9553 9558 9551 9551 9551 
2
2419 2418 2423 2415 2422 2419 2420 2415 
3
7834 7840 7840 7835 7841 7835 7835 7838 
4
4088 4087 4090 4089 4093 4085 4090 4084 
5
2945 2946 2950 2948 2942 2943 2948 2947 
6
670 667 669 671 670 670 668 671 
7
8869 8869 8873 8875 8870 8872 8871 8873 
8
1709 1707 1712 1712 1714 1710 1706 1712 
9
10239 10248 10242 10240 10242 10242 10245 10235 
10
6580 6579 6574 6580 6583 6580 6577 6581

 

input2

1
2147483647 2147483640 2147483644 2147483647 2147483647 2147483646 2147483645 2147483644
2
2147483647 2147483640 2147483644 2147483647 2147483647 2147483646 2147483645 2147483644
3
2147483647 2147483640 2147483644 2147483647 2147483647 2147483646 2147483645 2147483644
4
2147483647 2147483640 2147483644 2147483647 2147483647 2147483646 2147483645 2147483644
5
2147483647 2147483640 2147483644 2147483647 2147483647 2147483646 2147483645 2147483644
6
2147483647 2147483640 2147483644 2147483647 2147483647 2147483646 2147483645 2147483644
7
2147483647 2147483640 2147483644 2147483647 2147483647 2147483646 2147483645 2147483644
8
2147483647 2147483640 2147483644 2147483647 2147483647 2147483646 2147483645 2147483644
9
2147483647 2147483640 2147483644 2147483647 2147483647 2147483646 2147483645 2147483644
10
2147483647 2147483640 2147483644 2147483647 2147483647 2147483646 2147483645 2147483644

 

위 코드는 input1으로 할 때는 빠르게 잘 동작 하지만 input2 처럼 매우 큰 값이 입력받게 될 경우 1분 이상의 시간이 걸린다. 그래서 일정한 규칙을 찾아 모듈러 연산을 수행하면 매우 빨리 시간을 단축할 수 있다.

모듈러 연산이란? 
int i % 2 같은 나머지 연산을 의미한다.

package com.ssafy.algo.w0805;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class T02_1225 {
	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 T = 10;
		
		for(int t=1;t<=T;t++) {
			int n=Integer.parseInt(br.readLine());
			String [] inp = br.readLine().split(" ");
			int [] pw=new int[inp.length];
			
			int min=Integer.MAX_VALUE;
			for(int i=0;i<inp.length;i++) {
				pw[i]=Integer.parseInt(inp[i]);
				if(pw[i]<min) min=pw[i];
			}
			int num=min/15;
			for(int i=0;i<inp.length;i++) {
				pw[i]-=15*(num-1);
			}
			
			doCycle(pw);
			bw.write("#"+t+" ");
			for(int a:pw) {
				bw.write(a+" ");
			}
			bw.write("\n");
		}
		bw.close();
		
	}
	static void doCycle(int [] pw) {
		
		for(int i=1;i<=5;i++) {
			int tmp=pw[0]-i;
			if(tmp<0) {
				tmp=0;
			}
			for(int j=0;j<pw.length-1;j++) {
				pw[j]=pw[j+1];
			}
			pw[pw.length-1]=tmp;
			if(tmp==0) return;
		}
		doCycle(pw);
	}
}

같이 스터디하는 오빠가 모듈러 연산으로 코드이다. 규칙성은 15

12345 빼면서 총 8 사이클 돌면 각 숫자는 원래 위치로 돌아오고 15씩 빠진다.

 

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?contestProbId=AV14uWl6AF0CFAYD&solveclubId=AXqjxFI6_SQDFATi&problemBoxTitle=08%EC%9B%9405%EC%9D%BC&problemBoxCnt=2&probBoxId=AXsTu7uqz5cDFARX 

SW Expert Academy