백준 22351번 파이썬 풀이

홍태리·2022년 1월 31일

백준 브루트포스 알고리즘 알고리즘 파이썬

백준

목록 보기

1/9

문제 원본 링크 : 백준 22351번 문제

파이썬 문법만 배운 상태에서 알고리즘 문제 풀이에 도전하는 첫번째 시도였다.

나중에 알고 보니 완전탐색 알고리즘을 활용해 푸는 문제였지만 패기롭게 도전한 나로서는 그런 것을 알고 있을 리 만무하다..
그래서 첫 시도로 작성한 코드는 대단히 길고, 복잡하고, 심지어 정확하지도 않았다.

첫 시도, 잘못된 코드

s = input()
num_list = []
next_index = 0

#문자열, 시작인덱스, 자리수를 받으면 문자열 내 시작인덱스부터 해당 자리수의 연속하는 숫자를 num_list에 추가하는 함수
def append_num(charset, index, digits):
  if index == None: #시작인덱스가 None 타입일 경우(이미 문자열 탐색이 종료된 경우)
    return
  button = True
  while button: #같은 자릿수의 숫자가 연속되는 한 각 숫자를 리스트에 추가
    if index+digits > len(charset)-1: #문자열의 끝에 도달했는지 검증
      num_list.append(charset[index:index+digits]) #끝에 도달했다면 마지막 숫자를 리스트에 추가하고 함수를 종료
      return
    if int(charset[index:index+digits])+1 == int(charset[index+digits:index+(digits*2)]):
      num_list.append(charset[index:index+digits])
      index += digits
    else: #자리수에 변화가 있는 경우
      num_list.append(charset[index:index+digits])
      change_index = index+digits #변화가 있는 자리수의 시작인덱스를 반환
      button = False
  return change_index #다음 자리수 숫자의 시작인덱스

if len(s) == 1: #문자열 길이가 짧을 때의 판별(길이 1)
  num_list.append(s)
elif len(s) == 2: #문자열 길이가 짧을 때의 판별(길이 2)
  if int(s[0])+1 == int(s[1]):
    num_list.append(s[0])
    num_list.append(s[1])
    
  else:
    num_list.append(s)
    
elif len(s) == 3: #문자열 길이가 짧을 때의 판별(길이 3)
  if int(s[0])+2 == int(s[1])+1 == int(s[2]):
    num_list.append(s[0])
    num_list.append(s[1])
    num_list.append(s[2])
  else:
    num_list.append(s)
else: #문자열 길이가 길 때의 판별(길이 4 이상) 문자열의 첫 시작이 몇 자리 수인지만 판단
  if int(s[0])+1 == int(s[1]): #문자열 첫 2개 1자리수 연속: 1자리수 시작
    if int(s[0:2])+1 == int(s[2:4]): #1자리수 시작 같은 2자리수 시작
      next_index = append_num(s, 0, 2)
      append_num(s, next_index, 3)
    elif len(s) >= 6 and int(s[0:3])+1 == int(s[3:6]): #1자리수 시작같은 3자리수 시작
      append_num(s, 0, 3)
    else: #진짜 1자리수 시작
      next_index = append_num(s, 0, 1)
      next_index = append_num(s, next_index, 2)
      append_num(s, next_index, 3)
  else: #문자열 첫 2개 1자리수 불연속: 910 시작, 2자리/3자리수 시작
    if int(s[0]) == 9 and int(s[1:3]) == 10: #910 시작
      next_index = append_num(s, 0, 1)
      next_index = append_num(s, next_index, 2)
      append_num(s, next_index, 3)
    elif int(s[0:2])+1 == int(s[2:4]): #문자열 첫 2개 2자리수 연속
      if len(s) >= 6 and int(s[0:3])+1 == int(s[3:6]): #2자리수 시작 같은 3자리수 시작
        append_num(s, 0, 3)
      else: #진짜 2자리수 시작
        next_index = append_num(s, 0, 2)
        append_num(s, next_index, 3)
    else: #3자리수 시작
      append_num(s, 0, 3)
  
print(num_list[0], num_list[-1])

작성에만 무려 5시간이 넘게 걸린 코드였으나...

장렬하게 전사해버린 코드(이때 솔직히 멘탈이 나갔다)

그래도 퍼즐 풀 듯 차근차근 생각해나가는 과정이 그리 재미없지는 않았던 것에 위안을 삼고

구글 검색을 통해 브루트포스 알고리즘(완전탐색 알고리즘)에 대해 대략적인 개념을 습득한 뒤 다시 코드를 작성해보았다.

수정한 코드

s = input()

#지정한 숫자부터 오름차순으로 자연수를 나열한 문자열을 생성하는 함수
def create(start_num, total_length):
  charset = ''
  start = str(start_num)
  end = ''
  for n in range(start_num, 1000):
    if len(charset) >= total_length:
      break
    charset += str(n)
    end = str(n)
  return charset, start, end

def solve():
  cases = []
  cases.append(create(int(s[0]), len(s))) #입력된 문자열이 한 자리 수부터 시작한다고 가정할 때 생성되는 오름차순 문자열
  if len(s) >= 2: 
    cases.append(create(int(s[0:2]), len(s))) #입력된 문자열이 두 자리 수부터 시작한다고 가정할 때 생성되는 오름차순 문자열
  if len(s) >= 3:
    cases.append(create(int(s[0:3]), len(s))) #입력된 문자열이 세 자리 수부터 시작한다고 가정할 때 생성되는 오름차순 문자열
  
  for i in range(3):
    if s == cases[i][0]:
      print(cases[i][1], cases[i][2])
      break

solve()