21.08.18 기록

백준 알고리즘 1436 풀이

🎆나의 오답

-six 배열에 종말의 숫자값을 모두 입력한 후, 입력값-1을 인덱스 값으로 해서 출력하는 로직을 짜고 싶었다.
-열심히 if,for문으로 배열을 채워봤으나 답은 출력하지 못했다.
-로직이 점점 산으로 가는 것 같아 그냥 해설을 보기로 했다.

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

  public class B1436 {
      public static String[] six = new String[10000];

      public static void main(String[] args) throws IOException {
          setArray();

          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          System.out.println(six[(Integer.parseInt(br.readLine())-1)]);
      }

      public static void setArray() {
          six[0] = "666";

          int idx = 0;
          for(int i = 1; i < six.length ; i++) {
              if(!String.valueOf(i).contains("6")) { six[i] = (i + "666");}
              else {
                  for(int j = 0; j < 10; j++) {
                      six[i] = ("666" + j);
                      i += 1;
                  }
              }

              if(six[i-1].equals("6669")) {
                  idx = i;
                  break;
              }
          }

          int k = 7;
          for(int i = (idx+1); i < six.length; i++) {

              i--;
              for(int j = 0; j <= 8; j++) {
                  six[i] = (k + "666");
                  k += 1;
                  if(i+1 < six.length) { i += 1; }
              }

              if(k % 100 == 66) {
                  int share = k/100;
                  for(int j = 0; j <= 9; j++) {
                      if(share > 0) { six[i] = share + "6660" + j; }
                      else { six[i] = "6660" + j; }
                      if(i+1 < six.length) { i += 1; }
                  }
                  for(int j = 10; j <= 99; j++) {
                      if(share > 0) { six[i] = share + "666" + j; }
                      else { six[i] = "666" + j; }
                      if(i+1 < six.length) { i += 1; }
                  }
                  k += 1;
              }
              else {
                  for (int j = 0; j <= 9; j++) {
                      six[i] = (k / 10 + "666" + j);
                      if(i+1 < six.length) { i += 1; }
                  }
                  k += 1;
              }
          }
      }
  }

🎆해설

-해설을 보니 “666”을 포함하고 있는지 포함하고 있지 않은지를 고려하여 풀 수도 있었다.
-위 방법과 자릿수를 고려하여 카운트 하는 두 가지 풀이 방법을 제시한다.
-두번째 방법이 내가 풀고자 하던 맥락과 엇비슷한데.. 풀이를 봐도 복잡하다.

• 첫번째 방법 - “666”을 포함하고 있는지 count (메모리 87.1MB, 시간 324ms로 통과)

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  //해설 1.
  public class B1436 {
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int N = Integer.parseInt(br.readLine());
  
          int num = 666;
          int cnt = 1;
          while(cnt != N) {
              num++;
              if(String.valueOf(num).contains("666")) { cnt++; }
          }
          System.out.println(num);
      }
  }
  

• 두번째 방법 - 경우의 수를 나눠서 count (메모리 14.2MB, 시간 132ms로 통과)

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
  
    public class B1436 {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int N = Integer.parseInt(br.readLine());
  
            if(N > 1) { six(N); }
            else { System.out.println(666); }
        }
  
        public static void six(int N) {
            int cnt = 1;
            int preDigit = 0;   //앞 자릿수
            int num = 0;        //앞 자릿수를 제외한 나머지 뒷 자릿수
  
            while(true) {
  
                if( (preDigit % 10000)/10 == 666 && preDigit % 10 != 6) {
                    for (int i = 0; i < 1000; i++) {
                        if (cnt == N) {
                            System.out.println(preDigit * 1000 + num);
                            return;
                        }
                        num++;
                        cnt++;
                    }
                    preDigit++;
                }
  
                else if (preDigit % 1000 == 666) {
                    num = 0;
                    for(int i = 0; i < 1000; i++) {
                        if(cnt == N) {
                            System.out.println(preDigit*1000 + num);
                            return;
                        }
                        cnt++;
                        num++;
                    }
                    preDigit++;
                }
  
                else if (preDigit % 100 == 66) {
                    num = 600;
                    for(int i = 0; i < 100; i++) {
                        if(cnt == N) {
                            System.out.println(preDigit*1000 + num);
                            return;
                        }
                        cnt++;
                        num++;
                    }
                    preDigit++;
                }
  
                else if(preDigit % 10 == 6) {
                    num = 660;
                    for(int i = 0; i < 10; i++) {
                        if(cnt == N) {
                            System.out.println(preDigit*1000 + num);
                            return;
                        }
                        num++;
                        cnt++;
                    }
                    preDigit++;
                }
  
                else {
                    num = 666;
                    if(cnt == N) {
                        System.out.println(preDigit*1000 + num);
                        return;
                    }
                    cnt++;
                    preDigit++;
                }
            }
        }
    }