원재의 메모리 복구하기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV19AcoKI9sCFAZN&categoryId=AV19AcoKI9sCFAZN&categoryType=CODE&problemTitle=1289&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

풀이

입력으로 들어오는 값의 길이가 짧기때문에 "0"으로 초기화된 값이랑 입력값이랑 비교하여 바꾸면서 입력값과 같도록 만들어주는 방식으로 풀 수 있다.

이럴 경우 n^2에서 n^3까지 시간복잡도가 나오는데 이는 좋은 알고리즘이 아니라고 생각한다.

그래서 더 나은 방법을 찾아보았다.

현재 값을 기준으로 이전값과 다르다면 그건 현재값을 변하도록 조치를 취했다는 것이라 보고 cnt를 증가시켜준다.

왜냐하면 이전 값과 다르다는 것은 값을 바꿔주는 행위를 했다는 것을 의미하기 때문이다.

1010 같은 경우 먼저 제일 앞의 수를 1로 만들어주기 위해 cnt가 1증가하고 0을 만들기 위해 증가, 1을 만들기 위해 증가, 0을 만들기 위해 증가. 총 4번 시행한다.

이처럼 현재값이랑 이전 값이 다른 경우만 보면 되기때문에 n으로 시간복잡도가 나오고 더 빠른 시간 내에 처리할 수 있다.

#1 1
63900
#1 1
9200
#2 2
38400
#2 2
4500

두 가지 방법으로 해본 결과 위와 같은 결과가 나왔고 두번째 알고리즘이 더 나은 것이라는 것을 알 수 있었다.

코드

import java.io.*;

public class Main {
    static int n, m, k;

    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 = Integer.parseInt(br.readLine());

        for (int t = 0; t < T; t++) {
            String before = br.readLine();

            StringBuilder sb = new StringBuilder();

            //2번 방법법
           long sTime = System.nanoTime();

            for(int i  = 0; i<before.length();i++) {
                sb.append("0");
            }
            String after = sb.toString();
            int count = 0;

            char[] beforeArr = before.toCharArray();
            char[] afterArr = after.toCharArray();

            int start = 0;
            while (!before.equals(after)) {
                for (int i = start; i < beforeArr.length; i++) {
                    if (beforeArr[i] != afterArr[i]) {
                        changeValue(beforeArr[i], i, afterArr);
                        start = i + 1;
                        count++;
                    }
                }
                after = String.valueOf(afterArr);
            }

            sb = new StringBuilder();
            sb.append("#").append(t + 1).append(" ").append(count).append("\n");
            bw.write(sb.toString());

            long endTime = System.nanoTime();
            bw.write((endTime-sTime)+"\n");

            // 1번 방법
            sTime = System.nanoTime();

            int[] arr = new int[before.length()];
            for (int i = 0; i < before.length(); i++) {
                arr[i] = before.charAt(i) - '0';
            }
            count = arr[0];

            for (int i = 1; i < arr.length; i++) {
                if(arr[i] != arr[i - 1])
                    count++;
            }

            sb = new StringBuilder();
            sb.append("#").append(t + 1).append(" ").append(count).append("\n");
            bw.write(sb.toString());

            endTime = System.nanoTime();

            bw.write((endTime-sTime)+"\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static void changeValue(char value, int pos, char[] after) {
        for (int i = pos; i < after.length; i++) {
            after[i] = value;
        }
    }
}