boj 1972 : 놀라운 문자열

문제 주소: https://www.acmicpc.net/problem/1972

난이도: silver 3

1.문제설명

• 대문자 알파벳으로만 이루어져 있는 문자열이 있다.
• 이때 D-쌍을 정의할 수 있다.
• 문자열에 포함된 거리가 D인 두 문자를 순서대로 나열한 것을 D-쌍이라고 한다.
• 정의되는(0~N-2쌍) D-쌍들이 서로 다를때 이 문자열을 D-유일하다고 한다.
• 모든 D에대해 D-유일하면 놀라운 문자열이라고 한다.
• 문자열이 주어졌을 때 놀라운 문자열인지 판단해라

2.문제해결 아이디어.

• 현재 문자가, 집합 or 리스트에 있는지 확인해서 있으면 놀랍지않고
• 없으면 집합에 추가해준다.
• 모든 d에대해 반복이 끝나면 놀랍다고 해주면된다.

3.문제접근법

• list에서 탐색하는것보다 set에서 탐색하는게 더 빠르니 set객체를 하나 만들고
• dist를 for문으로 만들고 dist가 바뀔때마다 set를 초기화 해준다.
• 그러고 원소의 처음부터 끝까지 인덱스를 주의하며
  • 새로운 단어를 정의하고, 그 단어가 set에 포함되어있는지 확인하고 없으면 넣어준다.

def check_surprise(word):
    N = len(word)
    for dist in range(1, N):
        wordset = set()
        for i in range(0, N-dist):
            d_word = word[i]+word[i+dist]
            if d_word in wordset:
                return False
            else:
                wordset.add(d_word)
    return True

4.특별히 참고할 사항

• 출력부분에서 .안찍어서 이맞틀을 10분동안했다.

5.코드구현

import sys
input = sys.stdin.readline

def check_surprise(word):
    N = len(word)
    for dist in range(1, N):
        wordset = set()
        for i in range(0, N-dist):
            d_word = word[i]+word[i+dist]
            if d_word in wordset:
                return False
            else:
                wordset.add(d_word)
    return True



while True:
    word = input().rstrip()
    if word == "*":
        exit(0)
    else:
        if check_surprise(word):
            print(f"{word} is surprising.")
        else:
            print(f"{word} is NOT surprising.")