-
1515. [Python]수 이어 쓰기Python_알고리즘/Silver III 2023. 4. 14. 00:21
1. 문제
https://www.acmicpc.net/problem/1515
1515번: 수 이어 쓰기
세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 브루트 포스
3. 파이썬 코드
answer = input() # 1부터 ~ N 까지 값 변수 cnt = 1 # 리스트 인덱스 index = 0 # 언제까지 반복할지 모르기때문에 while while True: # 10 이상일 경우 자리수마다 나눠서 값을 비교해야기 때문에 if cnt >= 10: # 두자리 수 이상일 경우 각 자리마다 값 체크 for j in str(cnt): # 만약 값이 인덱스값과 같은 경우 인덱스 증가 if int(j) == int(answer[index]): index += 1 # 증가한 인덱스가 끝인경우 break if index == len(answer): break else: # 한자리 수가 인덱스 값과 같은 경우 인덱스 증가 if cnt == int(answer[index]): index += 1 # 인덱스가 끝인 경우 1씩 증가한 값 중 cnt 값 출력 if index == len(answer): print(cnt) break cnt += 1
4. 문제를 풀고난 후 생각
- 문제를 읽고 문제를 이해하는데 많은 시간이 들었다.
- 처음 들었던 생각으로는 0~9 까지 숫자중 같은 숫자들만 빼고 나머지를 남겨뒀다고 생각했다. 하지만 이렇게 생각하니 예제가 들어맞지 않아서 다른 방법으로 접근을 해야겠다고 생각이 들었다.
- 1부터 N까지 모든 숫자를 나열하고 그 중 숫자 일부를 빼는 것이기 때문에 1부터 시작해서 input 으로 들어온 값의 각 자리수와 비교해가며 일치할 경우 인덱스 값을 증가해 나가는 방식으로 문제를 해결했다.
- 위 그림을 예시로 23415가 주어질 경우 1부터 1씩 증가해 나가며 인덱스의 값들과 매칭되는지 확인하고 두 자리수 이상 부터는 각 자리수를 나눠서 인덱스값과 비교해가며 일치하는지 확인하였다.
- 이렇게 값들을 비교해 나가다 인덱스 값이 끝인 경우 그 때의 N(cnt)를 출력하는 방식으로 해결했다.
5. 문제를 푸는데 도움이 되는 지식
- 브루트 포스
'Python_알고리즘 > Silver III' 카테고리의 다른 글
1213. [Python]팰린드롬 만들기 (0) 2023.04.22 1788. [Python]피보나치 수의 확장 (0) 2023.04.19 14425. [Python]문자열 집합 (0) 2023.03.01 2108. [Python]통계학 (0) 2023.02.25 1463. [Python]1로 만들기 (0) 2023.02.11