백준 1110번 더하기 사이클 v

알고리즘을 잘 파악하면 간단하게 풀 수 있는 문제였는데

나는 처음에 엄청 복잡하게 풀어서 메모리 초과가 났었다.

내가 처음에 풀었던 방식은 다음과 같다.

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();

    //입력받기
    String str = br.readLine();
    int input = Integer.parseInt(str);

    //10미만인가
    check(sb, input);

    int idx = 1;
    int cnt = 0;
    String con = "";

    while(!str.equals(con)) {
      //두 수를 더하기
      int sum = Integer.parseInt(sb.substring(4*(idx-1),4*(idx-1)+1)) + Integer.parseInt(sb.substring(4*(idx-1)+1,(4*(idx-1)+1)+1));
      check(sb, sum);

      //두 수를 합치기
      con = sb.substring(4*(idx-1)+1,(4*(idx-1)+1)+1) + sb.substring(1 + 4 * (idx - 1) + 2, 1 + 4 * (idx - 1) + 2+1);
      sb.append(con);
      idx++;
      cnt++;
    }
    System.out.println(cnt);
  }

  static void check(StringBuilder sb, int n) {
    if(n < 10) {
      sb.append(0);
      sb.append(n);
    } else {
      sb.append(n);
    }
  }
}

문제에서 파악한 내용을 한글 -> 코드로 곧이곧대로 옮긴 셈인데..

시작 숫자부터 연산 과정에서 나오는 숫자들을 StringBuilder에 차례로 쭉 넣는 것이다. 

그렇게 보면 숫자를 연산하는 과정에서 인덱스가 등차수열인 규칙이 있어서 

필요한 인덱스 위치의 수를 이용해 새로운 숫자를 만들 수 있다.

내가 생각해도 너무 구린 풀이다.

결과는 맞게 나온다. 그런데 백준에서 메모리 초과 안 났으면 이정도까지 구린 줄은 덜 깨달았을 것 같다.

 

 

인터넷을 검색해보고 파악한 알고리즘을 적용하면 

이렇게 풀 수 있다.

 

1. N의 십의 자리 수와 일의 자리 수를 더한다

 -> N / 10 + N % 10

2. 1번 과정에서 나온 숫자의 일의 자리 수를 일의 자리수,

   N의 일의 자리 수를 10의 자리수로 하여 새 수를 만든다.

 -> (N / 10 + N % 10) % 10 + (N %10 ) * 10

 

=> 결국 (N / 10 + N % 10) % 10 + (N %10 ) * 10 의 반복이다.

     단, 처음 숫자와 같아지면 반복문을 종료한다.

     이 과정에서 N이 계속 변하기 때문에 반복문 안의 if문에서

     처음 입력한 숫자와 새로 만든 수를 비교하기 위해

     변수 int org를 생성해 처음 입력받은 숫자를 저장해 N과 비교하였다.

 

     처음 입력값과 연산하여 만든 수가 같아지는 데 몇 번의 사이클이 필요한지 구해야 하므로

     int cnt를 0으로 초기화하여 1회 반복할 때마다 cnt값을 1씩 증가시켰다.

     반복문이 종료되면 cnt를 출력한다.

 

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());
    int org = N;

    int cnt = 0;
    while(true) {
      N = (N/10 + N%10) % 10 + (N % 10 * 10);
      cnt++;
      if(N == org) {
        System.out.println(cnt);
        return;
      }
    }
  }
}