글 읽기 - Naive한 퀵소트로 해결했습니다만 문제가 없는 구현인가요?

jhthelefthanded 5년 전 0

안녕하세요. 정답 처리는 받았습니다만 확신이 들지 않아서 이곳에 글 남깁니다.

기본적으로 (사랑합니다 출제위원님) Naive한 퀵소트에서 나누는 기준을 단어의 길이로 하되, 단어의 길이가 같은 경우에는 단어의 사전적 순서를 기준으로 정렬을 하도록 구현을 했거든요.

그런데 이렇게 되면 제대로 정렬되는 것을 보장받을 수 있나요? 저도 제출하고나니 길이로 한번씩 정렬하는 동안 사전식 순서로 정렬되는 게 엉켜버릴 것 같아 식겁했는데 통과가 되어버렸네요8ㅅ8...

import sys

wordset = set([])
for i in range(int(input())):
    wordset.add(sys.stdin.readline().rstrip())

wordlist = list(wordset)
    
def quicksort(array, p, r):
    if p < r:
        q = partition(array, p, r)
        quicksort(array, p, q - 1)
        quicksort(array, q + 1, r)

def partition(array, p, r):
    x = array[r]
    i = p - 1
    for j in range(p, r):
        if len(array[j]) < len(x):
            i += 1
            array[i], array[j] = array[j], array[i]
        elif len(array[j]) == len(x):
            if array[j] < x:
                i += 1
                array[i], array[j] = array[j], array[i]
    array[i + 1], array[r] = array[r], array[i + 1]
    return i + 1

quicksort(wordlist, 0, len(wordlist) - 1)

for i in wordlist:
    print(i)

jh05013 5년 전 0

19~25줄은 다음과 같습니다. 단순히 비교 기준을 조건문에 넣은 것이므로 아무 문제가 없습니다.

if len(array[j]) < len(x) and (len(array[j]) == len(x) and array[j] < x):
    i += 1
    array[i], array[j] = array[j], array[i]

jh05013 5년 전 0

오타 정정합니다.

if len(array[j]) < len(x) or (len(array[j]) == len(x) and array[j] < x):
    i += 1
    array[i], array[j] = array[j], array[i]

jhthelefthanded 5년 전 0

악 정말 감사드립니다ㅠㅠㅠㅠ 바보같이 공통된 부분 묶기만 하면 답이 나오는군요!!!

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

문제

문제

출처

ICPC

Naive한 퀵소트로 해결했습니다만 문제가 없는 구현인가요?

jhthelefthanded 5년 전 0

jh05013 5년 전 0

jh05013 5년 전 0

jhthelefthanded 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말