1회차 결과

https://www.acmicpc.net/problem/1436

1436번: 영화감독 숌

 

>> 영화감독 숌 풀기

숌이 만든 N번째 영화의 제목에 들어간 수를 출력

 

>> 후기: 

- 규칙 찾기로 시도했으나 정리가 깨끗하고 빠르게 되지 않아서 시간을 소모했다.

: 실수원인 cnt변수는 몇번째로 큰지 오름차순의 개수 변수임.

: 반면 (실수 인지 후 추가한) increase변수는 현재 따져야 할 대상인 숫자임. increase변수를 따로 두었어야 했는데, cnt변수를 increase변수처럼 사용하고 있었음.

: 왜 그랬을까? 깔끔하지 못하게 생각하다가 꼬여버렸다.

 

 

>> 성공시킨 내 알고리즘

import java.util.*;

// 숌이 만든 N번째 영화의 제목에 들어간 수를 출력

public class Main {
  static int increase = 0;
  static int cnt = 0;
  static int N = 0;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt();
    int answer;
    while (true) {
      if ((answer = check(increase)) == -1) {
        if (cnt == N) {
          System.out.println(Integer.parseInt(String.valueOf(increase) + "666"));
          break;
        }
      } else {
        System.out.println(answer);
        break;
      }
      increase++;
    }
    sc.close();
  }

  static int check(int i) {
    String str = String.valueOf(i) + "666";
    // 666이 나온 위치 찾기
    int here = str.indexOf("666");
    int right = str.length() - 3;
    // 666이 나온 위치가 i + 666 의 위치가 아니라면?
    if (here != right) {
      // 666이 나온 위치 이후를 다 ___... => n개 masking
      int maskCnt = str.length() - here - 3;
      for (int k = 0; k < Math.pow(10, maskCnt); k++) {
        cnt++;
        if (cnt == N) {
          String format = "%0" + maskCnt + "d";
          String preStr = str.substring(0, str.length() - maskCnt);
          return Integer.parseInt(preStr + String.format(format, k));
        }
      }
    } else {
      cnt++;
    }
    return -1;
  }
}

 

 

---

>> 잘못된 첫 시도 기록

cnt는 전역변수로 관리

전체적인 틀은 다음과 같다. 일단 현재 cnt는 "몇번째"의 integer이다.

먼저, 규칙을 찾았다. 증가하는 값 0, 1, 2, 3, 4, ... 에 따라서 666을 적절히 배치해주면 곧 종말의 수를 오름차순으로 따질 수 있었다. 그래서 cnt를 증가시켜갈 것이다. cnt랑 increase랑 다른 변수로 두기! increase++로 따지기.

핵심 판단 메서드로 check()를 두었다. 

- cnt가 만약 6으로 끝나는 정수라면(ex: 16) 16 + 666 => 16666인데, 그럼 1666_에서 _자리에 0부터 9가 오름차순으로 들어감. 그때 cnt++해주어야 함. check()에서 이 경우를 고려할 수 있음. 아니 cnt가 아니라 별도의 변수를 두어야 하는데, 내가 혼란스러웠다. cnt랑 별개로 increase를 두었음. 그거는 정말 1씩 증가시키면서 check(increase)해야 함

- cnt가 6으로 끝나는 정수가 아닌 경우 - 즉 일반적인 경우 예를들면 14인 경우, 14 + 666 => 14666 이다. 그냥 cnt++ 해주면 된다! (그럼 다음단계에서 15로 넘어갈텐데, 역시 15 + 666 => 15666이 그 다음 종말의 수임)

 

check()는 초반에 이렇게 구현했다. (부족한 알고리즘이다. 666_번대를 고려하지 않음 cnt변수를 부적절하게 사용함)