알고리즘 트랙 문제가 이미 많이 공부한 우선순위 큐에 대한 문제이기 때문에 정리할 게 없어서
알고리즘 추가 문제를 풀어봤는데 첫 문제부터 4시간을 썼지만 못 풀고 풀이를 봤다.
[뻘짓하게된 계기]
먼저, 쉽게 푸는 방법을 하고싶었는데, 하나하나 계산하면 시간초과가 나지 않을까? 염려하던게 실제로 일어났다. 처음 작성한 코드는 아래와 같이 숫자를 받아 연속된 3개의 6이 있는지 검사하도록 했다.
static boolean isShomNumber(int n){
boolean flag = false;
int sixCount = 0;
while(n>0){
if(n/10 == 6){
sixCount++;
}
else
sixCount=0;
if(sixCount == 3){
flag = true;
break;
}
}
return flag;
}
static void input(){
int num = 666;
int n = scan.nextInt();
int count = 0;
while(count < n){
if(isShomNumber(num)){
count++;
}
num++;
}
System.out.println(num-1);
}
count번째 수를 찾기 위해 반복문을 활용했는데 시간초과가 났다..
그래서 문제를 좀 오해해서 규칙을 찾아 푸는 Ad hoc 유형이구나 하며 장장 3시간 30분 간의 사투가 벌어졌는데, 규칙은 무조건 존재하며 구현할 수 있다는 신념으로 종이에 6이 도배되도록 반복했다.
static int shomNumberCount(int n){
// 만의 자리 단위로 예를 들어 현재 110000을 검사중이라면,
// 110000 ~ 120000 사이에 종말의 수가 몇개 있는지 반환하는 함수
// 만약 60000인 경우 66600, 66601 모두 종말의 수가 될 수 있어 109개를 리턴한다.
if(n == 0)
return 19;
int sixCount = 0;
int maxConsequenceSix = 0;
while(n>0){
if(n%10 == 6)
sixCount++;
else
sixCount=0;
n/=10;
maxConsequenceSix = Math.max(maxConsequenceSix, sixCount);
}
return 9 + (int)Math.pow(10, (maxConsequenceSix + 1));
}
static void input() throws Exception {
// 666 1666 2666 3666 4666 5666 6660 6661 6662 6663 6664 6665 6666 6667 6668 6669 7666 8666 9666
// 10666 11666 12666 13666 14666 15666 16660 16661 16662 16663 16664 16665 16666 16667 16668 16669 17666 18666 19666
// 20666 21666 .... 25666 26660 26661 26662 26663 26664 26665 26666 26667 26668 26669 27666 28666 29666
// 19개씩 반복되며 첫번째 수 666을 0번째라고 가정하면
// 0~ ~ 6 + 10 + 3
// 10000 ~ 6 + 10 + 3
// 이하동일
// 문제는 만의 자리가 6이 되었을때인데,
// 60666 61666 62666 63666 64666 65666 6개
// 66600 부터 66699 100개
// 67666 ~ 69666 3 개로
// 60666 ~ 6 + 100 + 3
// 70666 부터 90666 까지는 다시 6 + 10 + 3
// 0~99999 사이 숌넘버는 총 9 * 10 + 10 * 9 + 100개
// 100000 부터는?
// 101666 102666 103666 104666 105666 106660 ~ 106669 107666 108666 109666
// 160666 은 6 + 100 + 3
// 600666 은 6 + 1000 + 3
// 100000~200000 사이도 또한 9 * 10 + 10 * 9 + 100개
// 10만 단위로 280개씩있다가 600000 일때는 9 * 10 + 10 * 9 + 1000 = 1180개
// 만약 숫자가 20 이상이라면 10666부터 검사
// 39 이상이라면 20666 ...
// 00 10 20 30 40 50 "60" 70 80 90
// 100 110 120 130 140 150 "160" 170 180 190
// -----
// 600 610 620 630 640 650 "660" 670 680 690
// 19 19 19 19 19 19 109 19 19 19
// 19 19 19 19 19 19 109 19 19 19
// 19 19 19 19 19 19 109 19 19 19
// 19 19 19 19 19 19 109 19 19 19
// 19 19 19 19 19 19 109 19 19 19
// 19 19 19 19 19 19 109 19 19 19
// 19 19 19 19 19 19 1009 19 19 19
// 19 19 19 19 19 19 109 19 19 19
// 19 19 19 19 19 19 109 19 19 19
// 19 19 19 19 19 19 109 19 19 19
// 이런식으로 진행된다는 것
// 현재 몇번째 연산중인지를 0부터 기록해서, 6, 16 ,26 ... 66일때는 6이 두개니까 1000으로 세볼까..
int n = scan.nextInt();
int count = 0;
while(true){
// 받아온 n이 280이하라면 100000 미만의 숌 넘버,
int nowShomNumberCount = shomNumberCount(count);
if(n>=nowShomNumberCount){
n -= nowShomNumberCount;
count++;
}
else
break;
}
// count만큼의 만의 자리를 채워줘야함
// 현재 n의 경우
// count = 16, n = 1~6 -> 160666 ~ 165666
// count = 16 n = 6 ~ 105 -> 166600 ~ 166699
int shomNumber = 0;
if(n <= 6){
shomNumber = count * 10000 + (n-1) * 1000 + 666;
}
else{
// 현재 수가 91이고 shomNumberCount가 109라면
if(n< shomNumberCount(count) -3){
// 뒤에자리를 채운 경우
int digit = 0;
while(n / 10 > 0){
n /=10;
digit++;
}
// digit 만큼을 다른데다가 더 곱해줘야함
// 예를들어 count가 166이면 1666000 부터 시작해야한다.
shomNumber = count*10000 + (666 / (int)Math.pow(10, digit)) * (int)Math.pow(10, digit+1);
shomNumber += n - 7;
}
else{
// 106 107 108
shomNumber = count * 10000 + ((n % 10) + 1) * 1000 + 666;
}
}
System.out.println(shomNumber);
}정말 열심히 찾았는데 의도한 대로 비슷하게 되긴 하지만 예제 문제를 돌려보면 1 혹은 1000씩 차이가 났었다 더 이상 머리가 돌아가지 않아서 포기했다.
결국 다른 사람 답 보니까 그냥 반복문으로 풀리네?.. 내 잃어버린 3시간 반..
아래는 정답코드
static void input() throws Exception {
int n = scan.nextInt();
int shomNumber = 0;
int count = 0;
int tempNumber = 0;
while(count < n){
shomNumber ++;
tempNumber = shomNumber;
while(tempNumber > 0){
if(tempNumber % 1000 == 666){
count++;
break;
}
tempNumber /= 10;
}
}
System.out.println(shomNumber);
}
정답코드와 내 코드의 다른점 → 배울점은 나의 shomNumber Check 코드는 연속해서 10으로 나눈 나머지가 6인 상황이 등장하는지 검사하지만 이게 사실 필요가 없고, 언젠가 1000으로 나눈 나머지가 666이 되는지만 확인해도 연속된 6 3개임이 확실히 보장된다는 것이다.
나의 의도를 더더욱 간결한 조건으로 해결하는 법을 한번 더 고민하고 구현해야 한다는 생각이 들었다.
또, 코테도 문제 순서대로 난이도가 다르니까, 이런 문제가 1~2번에 나왔다면 무조건 브루트포스로 풀수 있다는 확신이 필요했을것같다. 얘도 실버5밖에 안되니까는..ㅠㅠ
