(Python/PCCP1회 모의고사 1번) 외톨이 알파벳

문제 설명

알파벳 소문자로만 이루어진 어떤 문자열에서, 2회 이상 나타난 알파벳이 2개 이상의 부분으로 나뉘어 있으면 외톨이 알파벳이라고 정의합니다.

문자열 "edeaaabbccd"를 예시로 들어보면,

• a는 2회 이상 나타나지만, 하나의 덩어리로 뭉쳐있으므로 외톨이 알파벳이 아닙니다.
  • "ede(aaa)bbccd"
• b, c도 a와 같은 이유로 외톨이 알파벳이 아닙니다. d는 2회 나타나면서, 2개의 부분으로 나뉘어 있으므로 외톨이 알파벳입니다.
  • "e(d)eaaabbcc(d)"
• e도 d와 같은 이유로 외톨이 알파벳입니다.
• 문자열 "eeddee"를 예시로 들어보면,
  • e는 4회 나타나면서, 2개의 부분으로 나뉘어 있으므로 외톨이 알파벳입니다.
    • "(ee)dd(ee)"
  • d는 2회 나타나지만, 하나의 덩어리로 뭉쳐있으므로 외톨이 알파벳이 아닙니다.
    • "ee(dd)ee"

PCCP 모의고사 1회 1번

 

문자열 input_string이 주어졌을 때, 외톨이 알파벳들을 알파벳순으로 이어 붙인 문자열을 return 하도록 solution 함수를 완성해주세요. 만약, 외톨이 알파벳이 없다면 문자열 "N"을 return 합니다. 제한사항 1 ≤ input_string의 길이 ≤ 2,600 input_string은 알파벳 소문자로만 구성되어 있습니다.

 

이 문제를 간단하게 요약하면 만약에 알파벳이 중간에 다른 알파벳을 끼고 나와야 외톨이 알파벳이라고 한다.

예를들면 eaea 는 a가 e사이에 껴있으므로 외톨이다.

하지만 eaaaaaaae 에서 a는 연속되어있지만 어디에 껴있지 않다. 그러므로 외톨이가 아니다.

 

여기서 내가 생각한 아이디어는 연속적으로 알파벳이 나오면 1개로 축소한다. 위에 eaaaae 이거를 eae 이렇게 말이다.

 

그럼 스택을 사용해서 스택에 넣고, 스택에 마지막 원소와 비교하여 같으면 넣지않고 다르면 넣어주면 된다.

 

stk = []
    for i in input_string:
        if len(stk) ==0 :
            stk.append(i)
        if stk[-1] != i:
            stk.append(i)
        else:
            pass

그러고 나서 eaea 처럼 똑같은 알파벳이 2개 이상이면 외톨이 알파벳이 아니므로 count함수를 사용해서 res에 넣고 정렬해주면 된다.

 

def solution(input_string):
    
    stk = []
    for i in input_string:
        if len(stk) ==0 :
            stk.append(i)
        if stk[-1] != i:
            stk.append(i)
        else:
            pass
    res = []
    for i in set(stk):
        if stk.count(i) >= 2:
            res.append(i)
    res.sort()
    return "".join(res) if len(res) != 0 else "N"