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

문제

✔ 난이도 - Silver 2

설명

문자열을 배열에 쭉 넣고 하나씩 훑어.
count는 1부터 시작하면서 ++되면서 검사하는데, 현재 찾는 수가 count 내에 존재하는지 확인해

• 이 때 count가 123일때 찾는 수가 1이라면 존재하는건데 만약 그 다음 찾는수가 2라면 같은 count인거잖아. 이것도 생각해야됨
• 해당숫자인거 찾았으면 다음 찾는 수도 해당 count에 존재하는지 봐야함

따라서 count를 앞에서부터 하나씩 검사하면서 현재 찾는 수가 있는지 확인해.
있다면 다음 찾는 수가 있는지 또 확인하고 count 끝수까지 확인했으면 count++해서 또 확인

예시를 들어보자면

count가 123이고 입력받은 수가 13이라면

⤓
1 2 3
⤓
1 3
찾는 1이 123에 있으니까 다음으로는 3을 봐야해. 그리고 count의 1은 검사했으니까 이것도 다음으로 옮겨

..⤓
1 2 3
..⤓
1 3
3을 찾아야하는데 2를 보고있잖아. 달라. count의 다음 수를 검사해

.....⤓
1 2 3
..⤓
1 3
동일함!

입력받은 수 끝까지 다 검사했다! 현재 count가 답이다!
만약 앞으로 더 검사할 입력받는 수가 있다면 count++ 해서 또 다시 진행하면 된다.

풀이

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // StringBuilder sb = new StringBuilder();

        String str = br.readLine();
        int length = str.length();

        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            arr[i] = str.charAt(i) - '0';
        }
        // System.out.println(Arrays.toString(arr));

        int count = 1;
        for (int i = 0; i < length; ){
            String s = Integer.toString(count);
            for (int j = 0; j < s.length(); j++){
                if(s.charAt(j) - '0' == arr[i]){
                    i++;

                    if (i == length){
                        System.out.println(count);
                        return;
                    }
                }
            }
            count++;
        }
    }
}

⏰ 시간복잡도

O(N log N)

• 바깥쪽 for문은 count 수만큼 돈다 O(N)
• 안쪽 for문은 count의 자릿수만큼 돈다 O(logN) (10,000은 5번 반복)

💡 TIL

• 숫자를 문자로 변환

  • Integer.toString()
  • String.valueOf()

• indexOf는 문자열 내에서 특정 문자나 문자열의 위치를 찾을 때 사용하기도하지만, 객체들이 담긴 리스트에서 특정 요소가 몇 번째에 있는지 찾을 때 사용하기도 한다.

  ArrayList<String> list = new ArrayList<>();
  list.add("Apple");
  list.add("Banana");
  
  int index = list.indexOf("Banana"); // 결과: 1