[백준/Python] 1515번 수 이어 쓰기
브루트포스 알고리즘, 그리디 알고리즘, 구현, 문자열 문제이며, 실버3 문제를 풀어보았습니다.
![[백준/Python] 1515번 수 이어 쓰기](https://inblog.ai/_next/image?url=https%3A%2F%2Finblog.ai%2Fapi%2Fog%3Ftitle%3D%255B%25EB%25B0%25B1%25EC%25A4%2580%252FPython%255D%25201515%25EB%25B2%2588%2520%25EC%2588%2598%2520%25EC%259D%25B4%25EC%2596%25B4%2520%25EC%2593%25B0%25EA%25B8%25B0%26logoUrl%3Dhttps%253A%252F%252Finblog.ai%252Finblog_logo.png%26blogTitle%3Dcode-with-me&w=1920&q=75)
문제
세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준이는 저녁을 먹으러 갔다 와서, 자기가 쓴 수의 일부가 지워져있는 모습을 보고 충격받았다.
세준이는 수를 방금 전과 똑같이 쓰려고 한다. 하지만, N이 기억이 나지 않는다.
남은 수를 이어 붙인 수가 주어질 때, N의 최솟값을 구하는 프로그램을 작성하시오. 아무것도 지우지 않을 수도 있다.)
입력
첫째 줄에 지우고 남은 수를 한 줄로 이어 붙인 수가 주어진다. 이 수는 최대 3,000자리다.
출력
가능한 N 중에 최솟값을 출력한다.
문제 풀이
number
를 1씩 증가시키면서 모든 숫자를 검사한다.(브루트포스)이 코드에서는
n[idx]
와num
이 일치할 때마다idx
를 증가시키는 방식으로 최선의 선택을 한다. (그리디)python에서
for
루프나while
루프에else
절을 사용하면, 루프가 완전히 실행된 후 (즉, 루프를 중단하지 않고 정상적으로 종료된 후)에else
절이 실행되는데 막상 그렇게 써 본 적은 없었다. 그래서 gpt한테 물어봤음.
처음엔 문제를 이해 못해서 풀이과정 올린 블로그를 보고 이해했다. 문자열n
과num
을 비교하여 해결한다. idx가 n의 길이보다 커질 때 해당 수를 출력하면 number의 최솟값을 구할 수 있다.
# n = 234092를 예로 들어보자. n의 길이는 6. # 1. number = 0, idx = 0 # 2. number = 1, idx = 0, n[idx] = 2, num = 1, 1 != 2, continue # 3. number = 2, idx = 0, n[idx] = 2, num = 2, 2 == 2, idx = 1 # 4. number = 3, idx = 1, n[idx] = 3, num = 3, 3 == 3, idx = 2 # 5. number = 4, idx = 2, n[idx] = 4, num = 4, 4 == 4, idx = 3 # 6. number = 5, idx = 3, n[idx] = 0, num = 5, 5 != 0, continue # 이런 식으로 진행되다가 idx가 n의 길이보다 커지면 해당 수를 출력하고 반복문을 빠져나온다
Share article