글 읽기 - 파이썬 1181번질문입니다.

0124yongsang 1년 전 0

첨부한 코드로 제출 시 시간초과라고 나옵니다.

또한 25번째 줄에 해당하는 print문에 end = ""를 넣지 않을경우 ex) "but\n" 과 같이 줄바꿈 문자까지 같이 출력됩니다.

이에대한 피드백 주시면 감사하겠습니다.

def insertion_sort(arr):
    alpha = "abcdefghijklmnopqrstuvwxyz"
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if len(arr[i - 1]) > len(arr[i]):
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
            elif len(arr[i - 1]) == len(arr[i]):
                for k in range(len(arr[i])):
                    if alpha.find(arr[i - 1][k]) > alpha.find(arr[i][k]):
                        arr[i - 1], arr[i] = arr[i], arr[i - 1]
                        break
                    elif alpha.find(arr[i - 1][k]) == alpha.find(arr[i][k]):
                        pass
import sys
input = sys.stdin.readline
N=int(input())
arr=[]
for i in range(N):
    a = input()
    arr.append(a)
arr = set(arr)
arr = list(arr)
insertion_sort(arr)
for i in arr:
    print(i, end="")

zenith82114 1년 전 0

7번 줄 elif에서 알파벳 비교할 때 alpha 문자열에서 find하시는데

이러면 alpha 문자열을 앞에서부터 읽으면서 찾을 거라서 꽤 느릴 것 같네요.

그냥 직접 알파벳 비교하는 게 훨씬 빠를 것 같습니다.

그리고 print 함수는 end 디폴트가 개행문자라서 끝에 개행문자 찍히는 게 정상입니다.

0124yongsang 1년 전 0

피드백 주신 부분을 수정하여 다시 제출하였는데도 시간초과가 나오네요. 어느 부분을 고쳐야 좋을까요?

def insertion_sort(arr):
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if len(arr[i - 1]) > len(arr[i]):
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
            elif len(arr[i - 1]) == len(arr[i]):
                for k in range(len(arr[i])):
                    if arr[i - 1] > arr[i]:
                        arr[i - 1], arr[i] = arr[i], arr[i - 1]
                        break
import sys
input = sys.stdin.readline
N=int(input())
arr=[]
for i in range(N):
    a = input()
    arr.append(a)
arr = set(arr)
arr = list(arr)
insertion_sort(arr)
for i in arr:
    print(i, end="")

zenith82114 1년 전 0

7번 줄 for문의 변수 k가 안 쓰이고 있네요.

문자별 비교를 직접 하시려면 arr[i-1][k] > arr[i][k]로 해도 되는데

어차피 여기는 길이가 같음이 보장된 곳이니 그냥 루프를 빼도 될 것 같습니다.

그런데 이렇게 고쳐도 제 컴에서 2만 개짜리 입력으로 돌려보니까

2초보다는 훨씬 오래 도는 것 같은데

만약 이걸로도 시간초과가 나면 그냥 파이썬 내장 sort를 쓰셔야 할 것 같습니다.

def insertion_sort(arr):
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if len(arr[i - 1]) > len(arr[i]):
                arr[i - 1], arr[i] = arr[i], arr[i - 1]
            elif len(arr[i - 1]) == len(arr[i]):
                if arr[i - 1] > arr[i]:
                    arr[i - 1], arr[i] = arr[i], arr[i - 1]
            else: break

0124yongsang 1년 전 0

for문을 빼고 제출하였더니 시간은 2300ms정도가 나오는데 성공했다고 나오네요. 그냥 파이썬 내장 sort를 쓰는게 좋을 것 같네요. 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 1181번질문입니다.

0124yongsang 1년 전 0

zenith82114 1년 전 0

0124yongsang 1년 전 0

zenith82114 1년 전 0

0124yongsang 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말