[#20210] 파일 탐색기

문제

#20210 파일 탐색기
Gold2
적용 알고리즘: X (String)

---

풀이 방법

코드 흐름

코드

미완성. 뒤지게 어렵다

from collections import deque

n = int(input())

all_words = []

# 문자는 문자 하나로, 숫자는 붙여서 (일단은 문자 형태로) 저장
for _ in range(n):
    word = input()
    temp = []
    num = ""
    for i in range(len(word)):

        if ('A' <= word[i] <= 'z' and num != ""):
            temp.append(num)
            num = ""

        if ('A' <= word[i] <= 'z'):
            temp.append(word[i])
        else:
            num += word[i]

    if (num != ""):
        temp.append(num)
    all_words.append(temp)

print(all_words)
print()
all_words.sort()
for i in range(len(all_words)):
    print(all_words[i])

num_temp = []
idx = 0
next = []
while(True):
    # 특정 인덱스의 문자가 숫자인 단어 골라내기
    for i in range(all_words):
        if ('0' <= all_words[i][idx][0] <= '9'):
            num_temp.append(all_words[i])
        else:
            next.append()
    
    # 특정 인덱스에서 숫자로 걸린 애들 끼리 서열 정하기
    for j in range(len(num_temp)):
        num_temp.sort()
        

시간초과 나길래 이분탐색 씀. 근데 틀렸대. 왜??????????
내 논리는 무결점이라고

def string_split(text):
    word = text
    temp = []
    num = ""
    for i in range(len(word)):

        if ('A' <= word[i] <= 'z' and num != ""):
            temp.append(num)
            num = ""

        if ('A' <= word[i] <= 'z'):
            temp.append(word[i])
        else:
            num += word[i]

    if (num != ""):
        temp.append(num)
    return temp


# compare 함수
# a가 우선순위가 더 빠르면 1, b가 우선순위가 더 빠르면 2, 동일할 경우 0출력
def string_compare(a, b):
    idx = 0
    
    list_a = string_split(a)
    list_b = string_split(b)

    # print(list_a)
    # print(list_b)

    while(True):

        if (idx == len(list_a)):
            return 2
        if (idx == len(list_b)):
            return 1

        # 이게 된다면 둘중 하나는 숫자
        # 두개 다 숫자인 것을 골라내야 함. 나머지 경우 문자열 자체로 판별 가능
        # 두개 다 숫자인 경우
        if (list_a[idx] < 'A' and list_b[idx] < 'A'):
            a_num = int(list_a[idx])
            b_num = int(list_b[idx])
            if (a_num < b_num):
                return 1
            elif (a_num > b_num):
                return 2
            else:
                a_len = len(list_a[idx])
                b_len = len(list_b[idx])

                if (a_len < b_len):
                    return 1
                elif (a_len > b_len):
                    return 2
                else:
                    idx += 1
        # 문자인 경우 그냥 비교해서 반출하면 됨
        else:
            if (list_a[idx] < list_b[idx]):
                return 1
            elif (list_a[idx] > list_b[idx]):
                return 2
            else:
                idx += 1

# input = sys.stdin.readline()

# n = int(sys.stdin.readline())
# words = [sys.stdin.readline() for _ in range(n)]

n = int(input())
words = [input() for _ in range(n)]
fix = []
fix.append(words[0])

"""
for i in range(1, len(words)):
    for j in range(len(fix)):
        prior = string_compare(fix[j], words[i])
        if (prior == 2 or prior == 3):
            fix.insert(j, words[i])
            break
        if (j + 1 == len(fix)):
            fix.insert(j + 1, words[i])
            break

for text in fix:
    print(text)
"""


# 이분탐색
for i in range(1, len(words)):
    low = 0
    high = len(fix) - 1
    prior = -1
    mid = 0
    while (low <= high):
        mid = (low + high) // 2
        prior = string_compare(fix[mid], words[i])
        if (prior == 1):
            low = mid + 1
        if (prior == 2):
            high = mid - 1
        if (prior == 0):
            break
    if (prior == 1):
        fix.insert(mid + 1, words[i])
    else:
        fix.insert(mid, words[i])

for text in fix:
    print(text)

체감 난이도: /5