글 읽기 - [Python] 반례 부탁드리겠습니다!

toycartoon 1년 전 0

코드에서 혹시 제가 잘못하거나 반례인 부분이 있는지 찾아주시면 감사하겠습니다

hg = {'aespa': 'a', 'baekjoon': 'b', 'cau': 'c', 'debug': 'd', 'edge': 'e', 'firefox': 'f', 'golang': 'g', 'haegang': 'h',
      'iu': 'i', 'java': 'j', 'kotlin': 'k', 'lol': 'l', 'mips': 'm', 'null': 'n', 'os': 'o', 'python': 'p', 'query': 'q',
      'roka': 'r', 'solvedac': 's', 'tod': 't', 'unix': 'u', 'virus': 'v', 'whale': 'w', 'xcode': 'x', 'yahoo': 'y', 'zebra': 'z'}

s = input()

a = ""
c1 = 0
for c2 in range(len(s) + 1):
    if s[c1:c2] in hg:
        a += hg[s[c1:c2]]
        c1 = c2

if c1 != len(s):
    print("ERROR!")
else:
    print("IT's HG!")
    print(a)

cinador 1년 전 1

17번째 줄에 오타 있습니다. (IT's -> It's)

toycartoon 1년 전 0

해당 부분 수정해서 제출했더니 시간초과가 발생했습니다.. 줄일 수 있는 부분이 있을까요?

cinador 1년 전 2

주어지는 입력의 문자수가 최대 8백만이기 때문에 최적화가 필요한 것으로 보입니다. 이 코드는 모든 부분 문자열에 대해 hg내에 있는 원소와 대조하고 있습니다.

예를 들어 주어진 문자열이 음성기호로만 이루어져 있고 첫 문자가 c라면 c 다음에는 무조건 au가 와야 됩니다.

따라서 문자를 훑어가면서 처음 등장한 알파벳에 해당하는 음성기호가 등장하면 다음 구간으로 넘어가고 아니라면 문자열은 음성기호가 아니라고 판단할 수 있습니다.

예)

cauaespaunix

처음 등장한 알파벳 c -> 다음에 cau가 등장하는 지 확인 -> 등장하므로 cau 다음 알파벳인 a로 넘어감-> aespa가 등장하는지 확인 -> 등장하므로 다음 알파벳인 u로 넘어감...

문자열 끝까지 도달했다면 음성기호 맞음

//////////////////////////////

cauaespauniy

u 부분에서 unix가 아니므로 음성기호 아님

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

문제

문제

출처

ICPC

[Python] 반례 부탁드리겠습니다!

toycartoon 1년 전 0

cinador 1년 전 1

toycartoon 1년 전 0

cinador 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말