글 읽기 - 테스트 케이스는 잘 되는데 제출하면 틀렸다고 나옵니다 ㅠㅠ

gmlwnsck6779 3년 전 0

틀린 부분을 알려주시면 감사하겠습니다 ㅠㅠ

A = [' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
N = int(input())
R = list(map(int,input().split()))
CH = input()
O = []
C = 0
for i in R:
  O.append(A[i])

for i in O:
  if i not in CH:
    C = -1
    break

if C == -1:
  print('n')
else:
  print('y')

pmn0001 3년 전 0

10~13번째 줄에서 중복으로 검사되지 않나 싶어요

gmlwnsck6779 3년 전 0

이렇게 바꾸었더니 이제는 시간초과가 되네요 ㅠㅠ

리스트 한 곳에 알파벳을 다 때려 박으니까 시간 초과가 발생하나 싶어서 A B 로 나누었는데도 그대로네요 ㅠㅠ

어디가 문제인걸까요 ㅠㅠ

A = [' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
B = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
N = int(input())
R = list(map(int,input().split()))
CH = list(input())
O = []
C = 0

for i in R:
  if i < 27:
    O.append(A[i])
  else:
    O.append(B[i-27])

for i in O:
  if i in CH:
    CH.remove(i)
  else:
    C = -1
    break

if C == -1:
  print('n')
else:
  print('y')

pmn0001 3년 전 0

주어진 문제의 길이는 최대 10만이에요

if i in ch: 같은 문법을 사용하시면 O(n^2) 의 시간복잡도를 가지게 됩니다.

10만의 제곱은 100억이라 연산하는데 대충 10초가 걸리게 돼서 시간초과가 나실겁니다.

이 문제는 O(n) 으로 해결가능합니다.

힌트1. 주어진 문자의 종류는 공백, 소문자, 대문자로 한정되어있어요.

힌트2. 두번째 줄 입력에서 어떤 문자를 몇 번 입력받는지 count 해보세요

힌트3. 세번째 줄 입력에서 어떤 문자가 몇 번 쓰였는지 count 해보세요

두 count가 같다면 암호해독에 성공합니다

pmn0001 3년 전 0

*추가적으로 list의 remove 함수 또한 시간복잡도가 커서 오래걸리는 함수입니다.

gmlwnsck6779 3년 전 0

힌트 주신거 보고 곰곰히 생각해봤는데 도저히 모르겠어서 가장 무식한 방법으로 했어요 ㅠㅠ

이러니까 맞더라고요 ...

혹시 외람되지만 서울과기대 재학중이신걸로 올려놓으셨던데 학교 어떤지 질문드려도 될까요 ??!!!

import sys
input = sys.stdin.readline

A = [' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
B = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

N = int(input()) #입력받는 숫자의 개수
E = list(map(int,input().split())) #입력받는 숫자
R = list(input()) #비교해야할 문자열
T = [] #입력받은 숫자를 문자열로 변환한 값
K = 0 #단순 판별 변수

#입력받은 숫자를 문자열 값으로 변환
for i in E:
  if i < 27:
    T.append(A[i])
  else:
    T.append(B[i-27])
T.sort()
R.sort()

if R[0] == '\n':
  R.remove('\n')

if R == T:
  print('y')
else:
  print('n')

pmn0001 3년 전 1

전에 있던 for i in ch 없이 잘 만드셨네요

학교 어떤지라는게 무슨 질문일까요? 머가 궁금하신지 잘 모르겠습니다

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

문제

문제

출처

ICPC

테스트 케이스는 잘 되는데 제출하면 틀렸다고 나옵니다 ㅠㅠ

gmlwnsck6779 3년 전 0

pmn0001 3년 전 0

gmlwnsck6779 3년 전 0

pmn0001 3년 전 0

pmn0001 3년 전 0

gmlwnsck6779 3년 전 0

pmn0001 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말