[알고리즘] 백준 1972 파이썬 - 놀라운 문자열

 

1972번: 놀라운 문자열

문제

대문자 알파벳으로만 이루어져 있는 문자열이 있다. 이 문자열에 대해서 ‘D-쌍’이라는 것을 정의할 수 있는데, 이 문자열에 포함되어 있는, 거리가 D인 두 문자를 순서대로 나열한 것을 이 문자열의 D-쌍이라고 한다. 예를 들어 문자열이 ZGBG라고 하자. 이 문자열의 0-쌍은 ZG, GB, BG가 되고, 이 문자열의 1-쌍은 ZB, GG가 되며, 이 문자열의 2-쌍은 ZG가 된다. 문자열의 길이가 N이라고 할 때, 0-쌍부터 (N-2)-쌍까지가 정의됨을 알 수 있다.

만일 정의되는 D에 대해, 어떤 문자열의 모든 D-쌍들이 서로 다를 때, 이 문자열을 D-유일하다고 한다. 위의 예를 보면, 0-쌍들은 ZG, GB, BG로 모두 다르다. 따라서 이 문자열은 0-유일하며, 마찬가지로 1-유일하고, 2-유일하다. 하지만 만일 문자열이 AAA라고 하자. 이 문자열은 0-유일하지 않으며, 다만 1-유일하다.

만일 어떤 문자열이 정의되는 모든 D에 대해 D-유일하면, 이 문자열을 정말이지 ‘놀라운 문자열’이라고 한다. 문자열이 주어질 때, 이 문자열이 놀라운 문자열인지 아닌지를 구하는 프로그램을 작성하시오.

 

문제풀이

while(1):
    x=input().rstrip()
    #01
    if x=="*":
        break
	#02
    for d in range(1,len(x)-1):
        tmp=set()
        #03
        for i in range(len(x)-d):
            s=x[i]+x[i+d]
            if s in tmp:
                print(x+" is NOT surprising.")
                break
            else:
                tmp.add(s)
        else:
            continue
        break
    else:
        print(x+" is surprising.")

- #01 : 입력받은 값이 *이면 while문을 종료한다.

- #02 : d 값 즉 0-유일, 1-유일을 구현하기 위해 필요한 for문이다.

- #03 : i값을 통해 s에 0유일 값부터 저장하기 시작한다. 각각 s값을 tmp에 존재하지 않으면

           추가하고 만약 존재하다면 놀라운 문자열이 아니므로 해당 문구 출력 후 break 한다.

           마지막까지 문제없이 실행되면 놀라운 문자열이라고 출력해준다.