[백준] 귀여운 수_17294

문제

욱제는 귀여운 수~ε٩(๑> ₃ <)۶з를 좋아한다. 귀여운 수~ε٩(๑> ₃ <)۶з는 수를 이루는 각 자릿수가 등차수열을 이루는 수이다. 당신은 욱제한테 귀여운 수~ε٩(๑> ₃ <)۶з 하나를 선물해주고 싶다. 수 하나가 주어졌을 때 이 수가 귀여운지 판단하는 프로그램을 짜 보자.

등차수열을 이루는 숫자들은, 왼쪽에서 오른쪽으로 가면서 일정한 크기(0일 수도 있음)만큼 커지거나 일정한 크기만큼 작아진다. 뭔지 모르겠으면 예제를 보고 알아보자.

입력

정수 k(1 ≤ k ≤ 1018)가 주어진다. 입력은 0으로 시작하지 않는다.

출력

수가 귀여우면 "◝(⑅•ᴗ•⑅)◜..°♡ 뀌요미!!"를, 귀엽지 않으면 "흥칫뿡!! <(￣ ﹌ ￣)>"를 따옴표 없이 출력한다.

사고의 체계

1. 숫자 입력-> 자릿수별로 숫자를 분리한다 -> while문, 10으로 나누는것 활용 숫자하나하나 분리 -> 리스트로 저장
2. 분리된 숫자의 차이를 이용해 등차수열인지 아닌지 확인-> 리스트로 저장한 각 자릿수 -> for문으로 비교

코드를 작성(Java)

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class cuteNumber_17294 {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        long num = sc.nextLong();
		
        //인풋을 통해 받은 숫자를 각 자릿수별로 분리
        List<Long> digits = new ArrayList<>();
        while(num > 0){
            digits.add(num % 10);
            num /= 10;
        }
		
        //list의 size가 1보다 작거나 같을 때도 출력해야 함
        if(digits.size() <= 1){
            System.out.println("◝(⑅•ᴗ•⑅)◜..°♡ 뀌요미!!");
            return;
        }
		
        //list의 인접한 두 원소의 차이를 diff(공차)와 같은지 비교
        boolean isArithmetic = true;
        long diff = digits.get(1) - digits.get(0); //공차
        for(int i = 2; i<digits.size(); i++){
            if(digits.get(i) - digits.get(i-1) != diff){
               isArithmetic = false; //만약 공차가 다르면 false값을 저장
               break;//공차가 다른것을 알았으면 더 이상 비교할 필요가 없으므로 for문을 빠져나옴
            }
        }
		
        //for문을 빠져나왔을 때 isArithmetic의 값에 따라 출력값을 결정지음.
        if(isArithmetic){
            System.out.println("◝(⑅•ᴗ•⑅)◜..°♡ 뀌요미!!");
        }else {
            System.out.println("흥칫뿡!! <(￣ ﹌ ￣)>");
        }
    }
}

코드 분석

• 이 코드의 단점은 자바로 짰기 때문에 일단 코드가 너무 복잡하다.
• 1) while문에서 자릿수를 계산할때 $O(n)$의 시간복잡도 발생
  2) for문에서 인접한 두 원소의 차이를 n-1번 비교하는 시간복잡도 $O(n)$ 발생
  1)과 2)를 통해 이 코드의 총 시간복잡도는 $O(n)$
  

코드 개선

• 위의 사진에서 봤을 때 시간이 216ms , 메모리도 17800KB 로 매우 느리다.
• while문과 for문에서 총 두번의 반복문이 발생하므로 실행 속도가 느려지고 효율성이 낮아진다는 단점이 있다.
• 자릿수를 계산할 때 불필요한 나눗셈 계산을 하지 않고 각 자릿수를 바로 구해서 list에 추가하는 방법이 있음
• Scanner는 입력처리 시 굉장히 실행시간도 느리고 메모리도 잡아먹어 안쓰는게 좋다.-> BufferedReader를 사용해 입력처리를 한다
• 객체지향언어답게 함수를 사용해 등차수열인지 확인을 한다.

개선한 코드 부분

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

public class cuteNumber_17294 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        if (check(br.readLine())) {
            System.out.print("◝(⑅•ᴗ•⑅)◜..°♡ 뀌요미!!");
        }
        else {
            System.out.print("흥칫뿡!! <(￣ ﹌ ￣)>");
        }
    }
    public static boolean check(String str) {
        if (str.length() == 1) {
            return true;
        }
        int diff = str.charAt(0) - str.charAt(1);
        for(int i = 2; i < str.length(); i++) {
            if (diff != str.charAt(i - 1) - str.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

• 확실히 이전보다 메모리를 덜쓰고 시간도 두배로 단축할 수 있었다.

다른 사람의 코드(숏코딩)

*a,=map(int,input())
print(["흥칫뿡!! <(￣ ﹌ ￣)>","◝(⑅•ᴗ•⑅)◜..°♡ 뀌요미!!"][len({j-i for i,j in zip(a,a[1:])})<2])

• a, = map(int, input()) : 입력된 값들을 int형으로 변환해서 a 리스트에 저장합니다. 입력된 값들이 변수 a에 저장됩니다.

• zip(a, a[1: ]) : a 리스트와 그 다음 요소를 각각 묶어서 튜플 형태로 반환합니다. 예를 들어, [1, 2, 3, 4]라는 리스트가 있다면 [(1, 2), (2, 3), (3, 4)]로 반환됩니다.

• {j - i for i, j in zip(a, a[1:])} : 리스트 a의 각 요소들 사이의 차이를 계산해서 집합(set)으로 만듭니다. {1, 1, 1}과 같은 집합이 만들어집니다

• len({j - i for i, j in zip(a, a[1:])}) < 2 : 만들어진 집합의 길이가 2 미만이면 True, 2 이상이면 False를 반환합니다. 이 값에 따라서 리스트 [흥칫뿡!! <(￣ ﹌ ￣)>, ◝(⑅•ᴗ•⑅)◜..°♡ 뀌요미!!]에서 출력할 값을 선택합니다

• 이제부터 언어를 python 으로 해야겠다고 다짐하는 계기가 되었다.