99클럽 코테스터디 8일차 TIL - 백준 9996

문제: https://www.acmicpc.net/problem/9996

이 문제는 처음에 한번에 못풀었고, 반례를 보고 이해한 다음에 두번째 풀이끝에 성공했다.

문제를 풀 때 반례를 가능한한 많이 고려해야하고, 또 반례를 떠올리는 법을 반복적으로 연습해야 한다고 느꼈다.

 

❌ 첫번째 풀이 - 틀린 풀이

n = int(input())
expression = input().split("*")
start = expression[0]
end = expression[1]

for _ in range(n):
  word = input()
  if word.startswith(start) and word.endswith(end):
    print("DA")
  else:
    print("NE")

 

해당 풀이는 65%에서 틀렸다는 결과가 나왔다. 도저히 반례를 떠올리기 쉽지 않아서 다른분이 올려주신 반례를 참고하니, 다음 테스트케이스에서 반례를 찾을 수 있었다.

1
aaa*a
aaa

답: NE


1

a*a
a
답: NE

 

주어진 word의 길이와 무관하게 시작하는지, 끝나는지를 체크하므로 1번 반례에서 a로 끝나므로 DA 라는 결과가 나왔다.

따라서 무조건 주어진 패턴의 * 앞 뒤의 길이를 합한것보다 크거나 같은지를 확인하는 조건을 추가해주었다.

 

✅ 두번째 풀이

n = int(input())
expression = input().split("*")
start = expression[0]
end = expression[1]

for _ in range(n):
  word = input()      # 길이 세는 조건문 추가
  if len(word) >= len(start) + len(end) and word.startswith(start) and word.endswith(end):
    print("DA")
  else:
    print("NE")