[백준 JAVA] 1515번: 수 이어쓰기

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

 

처음 접근은 1~N 까지의 자리의 수 중 지운수를 찾으려고 했으나 너무 비효율적이라 생각해서

그냥 1부터 N까지 계속 while문을 돌며 앞자리 부터 수들을 찾으려고 했다.

 

이 과정에서 무한 루프가 돌수도 있다고 생각이 들었지만 수는 1부터 0까지 최대 10개이고 주어지는 수가 최대 3000자리 였기 때문에 최악의 경우에도 O(30000) 정도면 해결될거라고 생각했다.

 

그리고 수같은 경우도 정수형을 사용할 경우 자릿수 때문에 Long 으로 해도 부족하고 String을 사용하여 계속 잘라나갈경우 너무 비효율 적이라는 생각이 들어서 애초에 큐를 사용하여 각각의 자리를 한자리씩 끊어 저장하고 앞부분을 비교하고 일치하는 경우 큐에서 꺼내는 식으로 풀이하였다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static int N;
    public static String str;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine();
        N = 1;
        Queue<Character> q = new LinkedList<>();
        for(int i = 0; i < str.length(); i++){
            q.offer(str.charAt(i));
        }

        while(!q.isEmpty()){
            String cur = N + "";
            for(int i = 0; i < cur.length(); i++){
                if(q.isEmpty()) continue;
                char next = q.peek();
                char now = cur.charAt(i);
                if(next == now){
                    q.poll();
                }
            }
            N++;
        }

        System.out.println(N - 1);
    }
}

 

역시나 깔끔하게 푼 느낌은 아니여서 GPT로 피드백을 받아보았다.

 

피드백

1. 현재 큐를 사용해서 풀이하고 있지만 차라리 인덱스 포인터로 대체하는것이 났다고 함

 

2. while문 조건에서 큐의 상태를 확인하고 있지만 for문에서 확인하지 않을 경우 null point exception 이 발생해서 이를 방지하기위해 

if(q.isEmpty()) continue;

이런식으로 사용을 해주었는데 이것보다는 가독성 적인 측면에서 continue; 대신 break; 를 사용하는게 맞다고 함

 

피드백을 반영하여 다시 푼 풀이

 

import java.io.*;
import java.util.*;

public class Main {
    public static int index, N;
    public static String str;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        str = br.readLine();

        index = 0;
        N = 1;

        while(index < str.length()){
            String cur = N + "";
            for(int i = 0; i < cur.length(); i++){
                if(index < str.length() && cur.charAt(i) == str.charAt(index)) index++;
            }
            N++;
        }

        System.out.println(N - 1);
    }
}

 

훨씬 깔끔하고 가독성도 좋고 효율도 좋아진 느낌 시간이나 메모리차이는 유의미하게 줄어들진 않았다.

 

회고:

1. 무작정 자료구조를 사용하는것보단 더 효율적으로 사용할 수 있는 방법이 있으면 미리 생각해보기

2. 변수에 값을 배열할때도 한번밬에 사용하지 않는 값이라면 그냥 한번만 연산해주면 되므로 생략하기