난이도

Silver 4

풀이 참고 유무

X

막힌 부분

X

문제

문제 바로가기
상근이는 수학시간에 딴 짓을 하다가 선생님께 걸렸다. 선생님은 상근이에게 이번 주말동안 반성하라며 엄청난 숙제를 내주었다.

선생님이 상근이에게 준 종이에는 숫자와 알파벳 소문자로 되어있는 글자가 N줄있다. 상근이는 여기서 숫자를 모두 찾은 뒤, 이 숫자를 비내림차순으로 정리해야한다. 숫자의 앞에 0이 있는 경우에는 정리하면서 생략할 수 있다.

글자를 살펴보다가 숫자가 나오는 경우에는, 가능한 가장 큰 숫자를 찾아야 한다. 즉, 모든 숫자의 앞과 뒤에 문자가 있거나, 줄의 시작 또는 끝이어야 한다.

예를 들어, 01a2b3456cde478에서 숫자를 찾으면 1, 2, 3456, 478이다.

선생님이 준 종이의 내용이 주어졌을 때, 상근이의 숙제를 대신하는 프로그램을 작성하시오.

입력

첫째 줄에 종이의 줄의 개수 N이 주어진다. (1 ≤ N ≤ 100)
다음 N개의 줄에는 각 줄의 내용이 주어진다. 각 줄은 최대 100글자이고, 항상 알파벳 소문자와 숫자로만 이루어져 있다.

출력

종이에서 찾은 숫자의 개수를 M이라고 하면, 출력은 M줄로 이루어져야 한다. 각 줄에는 종이에서 찾은 숫자를 하나씩 출력해야 한다. 이때, 비내림차순으로 출력해야 한다. 비내림차순은 내림차순의 반대인 경우인데, 다음 수가 앞의 수보다 크거나 같은 경우를 말한다.

예제 입력

4
43silos0
zita002
le2sim
231233

예제 출력

0
2
2
43
231233

문제 검토

범위를 보니 완탐이 가능해보인다.

풀이(python)

Python

#브루트포스
#O(n2) 가능
num=''
numOn=False
answer=[]
n = int(input())
s = [input() for _ in range(n)]
#O(n^2)
for x in s:
    for y in x:
        #알파벳이고 임시 숫자에 넣고 있던 중이면 모아놓은 숫자를 append
        if numOn and y.isalpha():
            answer.append(int(num))
            num=''
            numOn=False
            continue
        #알파벳이 아니면 임시 변수에 넣음
        elif not y.isalpha():                
            num+=y
            numOn=True
    #숫자로 끝나서 못한 append를 해줌
    if num:
        answer.append(int(num))
        num=''
        numOn=False
#정렬        
answer=sorted(answer,key=lambda x:x)
for x in answer:
    print(x)

알파벳 하나 하나 완탐을 했다.

걸린 시간

14:12

총평

문제에 들어가기 전에 계획을 최대한 디테일하게 짰고 시간복잡도를 계산하고 들어갔다.
그랬더니 원트에 성공할 수 있었다.

쉬운 문제지만 문제 푸는 전략을 처음 대입해보아서 괜찮은 문제였다.