Q. 1225. 암호생성기(D3)

Q. 1225. 암호생성기(D3)

 

0. 문제

 

D3 난이도의 문제이고, Queue를 사용한 구현 문제라고 생각된다.

숫자가 8개 주어지고 맨 앞의 숫자에 1을 빼고 맨 앞의 숫자를 맨 뒤로 보낸다.

이후 다음 숫자는 2를 빼고 맨 뒤로 보낸다.

빼는데 사용하는 숫자를 n이라고 했을 때 n이 5를 넘어서면 n은 1이 된다.

입력에 주어진 8개의 수 중 하나라도 0이 되면 루프를 종료하고, 결과를 출력하는 문제이다.

---

1. 풀이

 

1) 입력값을 받은 뒤에 큐에 저장한다.

2) 일일히 값을 빼가며 문제의 로직대로 수행한다.

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
class Solution
{
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int[] inputNum = new int[8];
    static Deque<Integer> queue;
     
    static void input() throws IOException
    {
        queue = new LinkedList<Integer>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < inputNum.length; i++) {
            inputNum[i] = Integer.parseInt(st.nextToken());
        }
    }
     
    static void pro(int tc) {
         
         
        for (int i = 0; i < inputNum.length; i++) {
            queue.add(inputNum[i]);
        }
         
        int num = 1;
        while (true) {
             
            int element = queue.poll();
            element -= num;
            if (element <= 0) {
                queue.add(0);
                break;
            }
            queue.add(element);
            num++;
            if (num > 5) num = 1;
        }
         
        sb.append(String.format("#%d ", tc));
         
        while (!queue.isEmpty()) {
            sb.append(queue.poll()).append(' ');
        }
        sb.append('\n');
    }
     
     
    public static void main(String args[]) throws Exception
    {
         
        //br = new BufferedReader(new FileReader(new File("res/input.txt")));
        br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while (true) {
            s = br.readLine();
            if (s == null || s.isEmpty()) break;
            input();
            pro(Integer.parseInt(s));
        }
//      for(int test_case = 1; test_case <= T; test_case++)
//      {
//          input();
//          pro(test_case);
//      }
        System.out.println(sb);
    }
}

---

2. 시간복잡도 계산

 

0) N의 최대값은 Int 범위이므로 2147483647이다.

1) 최악의 경우 (모든 원소가 2147483647로 주어지는 경우) 문제가 생긴다.

직접 해보니 40초가 걸리는 것을 확인했다.

문제는 위 코드로도 풀 수 있지만, 개선할 필요성을 느꼈다.

---

3. 성능 개선 방안

1 2 3 4 5 1 2 3
4 5 1 2 3 4 5 1
2 3 4 5 1 2 3 4
5 1 2 3 4 5 1 2
3 4 5 1 2 3 4 5

n(1~5)의 값을 보면 모든 원소에 대해 5번 반복하면 처음으로 돌아오는 것을 확인할 수 있고, 이 경우 합은 15이다.

그리고 이 값을 아래와 같이 활용할 수 있다.

1) 처음 들어온 원소 중 최소값을 구한다.

2) 최소값 % 15를 계산한다.(x라 하자)

3) 최소값 - x를 한다.(y라 하자)

3) 모든 원소들에서 y를 빼준다.

4) 이후 문제의 루프를 돈다.

 

이렇게 계산하면 루프 한 번(처음 1번 원소에 빼는 값  n이 1이 될 때 까지)이 돌아오는데 40번이면 되므로

모든 원소가 Integer.MAX_VALUE여도 빠르게 계산할 수 있다.

 

하지만 두 번째 문제가 있는데, 입력된 원소에 대해 최소값이 여러개 일 경우이다.

이 경우 루프 종료 뒤 출력에 0이 여러개 나오는 것을 확인할 수 있다.

이를 방지하기 위해 x값에 15를 더해주었다.

실제로 입력값으로 넣어 보고 시간을 측정해 보니 아래와 같이 문제없이 작동하는 것을 확인했다.

처음 제출한 코드와 실행 시간을 비교하니 조금 줄어든 것을 확인했다.

(유의미한 차이는 아닌 것 같다..)

개선한 코드는 아래와 같다.

import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
class Solution
{
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int[] inputNum = new int[8];
    static Deque<Integer> queue;
    static int min;
     
    static void input() throws IOException
    {
        queue = new LinkedList<Integer>();
        st = new StringTokenizer(br.readLine());
        min = Integer.MAX_VALUE;
        for (int i = 0; i < inputNum.length; i++) {
            inputNum[i] = Integer.parseInt(st.nextToken());
            min = Math.min(inputNum[i], min);
        }
    }
     
    static void pro(int tc) {
         
        int x = min % 15 + 15;
        int y = min - x;
        for (int i = 0; i < inputNum.length; i++) {
            queue.add(inputNum[i] - y);
        }
         
        int num = 1;
        while (true) {
            int element = queue.poll();
            element -= num;
            if (element <= 0) {
                queue.add(0);
                break;
            }
            queue.add(element);
            num++;
            if (num > 5) num = 1;
        }
         
        sb.append(String.format("#%d ", tc));
         
        while (!queue.isEmpty()) {
            sb.append(queue.poll()).append(' ');
        }
        sb.append('\n');
    }
     
     
     
    public static void main(String args[]) throws Exception
    {
 
        //br = new BufferedReader(new FileReader(new File("res/input.txt")));
        br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while (true) {
            s = br.readLine();
            if (s == null || s.isEmpty()) break;
            input();
            pro(Integer.parseInt(s));
        }
//      for(int test_case = 1; test_case <= T; test_case++)
//      {
//          input();
//          pro(test_case);
//      }
        System.out.println(sb);
    }
}