글 읽기 - [python] 좀 더 효율적인 방법을 알고 싶습니다.

time_to_bye 5년 전 0

안녕하세요. 1181번을 풀고 나서 비효율적인 방법을 개선해보고 싶어서 질문글을 남깁니다.

문제를 읽고 아래와 같이 생각하였습니다.

문자열을 담는 리스트를 만들고 그 안에 문자열 길이 별로 세분화 해서 저장한다.
문제 내에서 주어진 가장 긴 문자열이 50이니까 최대 수량만큼 문자열 담을 빈 리스트 생성 [ [], [], [], .... [] ]
입력 받을 때 문자열 길이에 해당하는 곳으로 배치
각각 정렬 한 후 출력한다.

문제점 : 빈 리스트가 너무 많이 발생 할 수 있다.

질문 입니다.!!

문제점을 개선하려면 아예 초기부터 접근을 다르게 해야 할지, 아니면 제가 작성한 코드에서 관점을 바꾸면 길이 보일지 잘 모르겠습니다.

고수님들의 좋은 답변 부탁드립니다. : )

from sys import stdin


def create_word_components(n):
    word_components = [[] for i in range(51)]
    for i in range(n):
        word = stdin.readline().strip()
        word_length = len(word)

        if word not in word_components[word_length]:
            word_components[word_length].append(word)

    return word_components


def sort_component(word_list):
    word_list = sorted(word_list, key=lambda x: x)

    return word_list


def main():
    n = int(input())
    word_components = create_word_components(n)

    result_words = []
    for i, word_component in enumerate(word_components):
        if word_component:
            result_words += sort_component(word_component)

    for word in result_words:
        print(word)


if __name__ == "__main__":
    main()

seico75 5년 전 2

저라면 읽어드린 string 앞에 문자길이를 붙여서 저장하고 sort를 하겠습니다.

"%02d"%(len(instr)) + instr 식으로 하면

01i

02iam

04wont

04wait

식으로 저장되니 길이를 포함해서 정렬이 될 것 같습니다.

그 다음에 출력할 때 word[2:] 식으로 하면...

time_to_bye 5년 전 0

@seico75

답변 감사합니다!!

chaos7061 4년 전 2

윗 분 처럼 할 경우 2차원 배열로 저장해서, lambda식 하나로 한 번에 길이 + 사전순 정렬을 해버릴 수도 있구요, (예를들어 list[0][0]...list[i][0]에는 단어를, list[0][1]...list[i][1]에는 길이를 담아서 한 줄로 sorting 가능합니다.)

저는 중복단어 제거를 위해서 처음에 set([])을 생성하고, 입력을 set.add로 받은 뒤 나중에 list로 변형해서 처리했습니다.(set은 자동으로 중복 제거를 해주기 때문에)

irregular 4년 전 1

파이썬에 있는 튜플이라는 자료형을 이용하면 좀 더 간단히 풀 수 있을 것 같습니다.

(A, B) 형태의 튜플을 정렬하면 A를 기준으로 먼저 정렬하고, A가 동일할 시에 B를 기준으로 정렬합니다.

time_to_bye 4년 전 0

@chaos7061

답변 주셔서 감사합니다. lambda를 잘 쓰면 참 좋은 것 같은데 아직 익숙치가 않은 것 같습니다.

말씀하신 방법으로도 한 번 코드 작성 해보겠습니다.! 감사합니다.!

@irregular

항상 리스트 위주로 코드를 짜다 보니 튜플을 전혀 생각을 못 했었습니다. 말씀하신대로 튜플로도 접근해보겠습니다.! 감사합니다.

jupiterbjy 4년 전 2

사족으로 set()을 쓰시면 항목이 겹치지 않습니다. 따라서 이렇게 짧게 구현이 가능합니다.

from sys import stdin

lists = set(stdin.readline().rstrip() for i in range(int(input())))
print('\n'.join(sorted(lists, key=lambda item: (len(item), item))))

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

문제

문제

출처

ICPC

[python] 좀 더 효율적인 방법을 알고 싶습니다.

time_to_bye 5년 전 0

seico75 5년 전 2

time_to_bye 5년 전 0

chaos7061 4년 전 2

irregular 4년 전 1

time_to_bye 4년 전 0

jupiterbjy 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말