📌 문제 : 백준 1436번
📌 문제 탐색하기
N : 찾으려는 종말의 수의 순서 (1 ≤ N ≤ 10,000)
✅ 입력 조건
1. N 입력
✅ 출력 조건
1. N번째 종말의 수 출력
6이 연속으로 3개 들어간 숫자들 중 N번째 숫자를 찾는 문제이다.
문자열에서 원하는 문자를 찾는 방식으로 구현하면 된다.
숫자를 하나씩 증가시켜가면서, 그 숫자에 666이 있는지 확인하고 있다면 1을 더해주면서 N이 될 때까지 이 과정을 반복해주면 된다.
가능한 시간복잡도
입력받기 →
문자열 변환 →
666 있는지 찾기 →
while 루프 반복 →
최종 시간복잡도
으로 제한 시간 내에 연산이 가능하다.
알고리즘 선택
브루트포스 방식으로 N번째 수를 찾을 때까지 하나하나 확인한다.
📌 코드 설계하기
- N 입력
- 몇 번째인지 셀 변수 정의
- 666부터 세도록 변수 정의
- while문으로 종말의 수 찾기
4-1. 숫자를 문자열로 캐스팅해 666 있는지 찾기
4-2. 666이 있다면 count 증가
4-3. count가 N과 동일하면 출력하고 while 종료
4-4. 종료되지 않았다면 숫자 증가
📌 시도 회차 수정 사항
1회차
### Before
for i in range(666, 10001):
str_i = str(i)
if '666' in str_i:
count += 1
if count == N:
print(i)
break
### After
i = 666
while True:
str_i = str(i)
if '666' in str_i:
count += 1
if count == N:
print(i)
break
i += 1N의 조건에 따라for문으로i에 직접 잘못된 범위 제한을 두었다.N은 몇 번째인지를 의미하는 것이므로N번째 숫자는10,000을 가뿐히 넘을 수 있는 숫자인데 그 부분을 착각했다.while문으로N번째 숫자를 찾을 때까지i를 계속 증가시키는 방식으로 변경하였다.
📌 정답 코드
import sys
input = sys.stdin.readline
# 1. N 입력
N = int(input())
# 2. 몇 번째인지 셀 변수 정의
count = 0
# 3. 666부터 세도록 변수 정의
i = 666
# 4. while문으로 종말의 수 찾기
while True:
# 4-1. 숫자를 문자열로 캐스팅해 666 있는지 찾기
str_i = str(i)
# 4-2. 666이 있다면 count 증가
if '666' in str_i:
count += 1
# 4-3. count가 N과 동일하면 출력하고 while 종료
if count == N:
print(i)
break
# 4-4. 종료되지 않았다면 숫자 증가
i += 1- 결과
다른 풀이
import sys
input = sys.stdin.readline
# 1. N 입력
N = int(input())
# 2. 찾으려는 수
movie = 666
# 3. N이 0이 될 때까지 반복
while N:
# 3-1. 666 있으면 N 감소
if "666" in str(movie):
N -= 1
# 3-2. 숫자 증가
movie += 1
# 4. 결과 출력 (마지막에 movie를 하나 증가시키므로 빼주기)
print(movie - 1)- 결과
- 정답 풀이와 달리 원하는
N을 찾을 때까지N을 감소시켜가며 브루트포스로 찾는 방법이다.
📌 회고
- 문제에 따라 여러 알고리즘이나 자료구조를 적용해서 푸는 것보다 브루트포스처럼 하나하나 찾아내는게 더 효율적인 경우도 있다는 것을 염두해두어야겠다.
- 처음부터 어떠한 알고리즘을 적용해야봐야겠다고 생각하는 것이 아니라, 일단 완전탐색으로 구현해보고 개선할 방향을 찾아야 한다는 이야기가 무슨 말인지 체감할 수 있는 문제였다.
