PCCP 모의고사 1회차 - 1번 문제

18 Aug 2024 in Algorithm

코딩테스트 준비

해당 썸네일은 Wonkook Lee 님이 만드신 Thumbnail-Maker 를 이용하였습니다

느슨해진 알고리즘 실력을 늘리고자 다시 코테를 풀고 있다. 바로 문제로 들어가자

• 🎾 문제
• 🏂 해결법
  • 코드
• 🏉 분석 및 후기

🎾 문제

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

1. 문자열 “edeaaabbccd” 를 예시로 들어보면,

a는 2회 이상 나타나지만, 하나의 덩어리로 뭉쳐있으므로 외톨이 알파벳이 아닙니다. “ede(aaa)bbccd”

b, c도 a와 같은 이유로 외톨이 알파벳이 아닙니다.

d는 2회 나타나면서, 2개의 부분으로 나뉘어 있으므로 외톨이 알파벳입니다. “e(d)eaaabbcc(d)”

e도 d와 같은 이유로 외톨이 알파벳입니다.

1. 문자열 “eeddee” 를 예시로 들어보면,

e는 4회 나타나면서, 2개의 부분으로 나뉘어 있으므로 외톨이 알파벳입니다. “(ee)dd(ee)”

d는 2회 나타나지만, 하나의 덩어리로 뭉쳐있으므로 외톨이 알파벳이 아닙니다. “ee(dd)ee”

문자열 input_string이 주어졌을 때, 외톨이 알파벳들을 알파벳순으로 이어 붙인 문자열을 return 하도록 solution 함수를 완성해주세요. 만약, 외톨이 알파벳이 없다면 문자열 “N” 을 return 합니다.

🏂 해결법

1. 알파벳이 2번 등장했다는 것은 체크해야 된다.
2. 연속됨을 체크하기 위해 prev 라는 변수를 사용
3. 답에는 중복이 없어야 하기에 set 사용

코드

from string import ascii_lowercase as AL

def solution(input_string):
    answer = set()
    count = {s:0 for s in AL}
    prev = 'Z'

    for s in input_string:
        count[s] += 1
        if s != prev:
            if count[s] >= 2:
                answer.add(s)

        prev = s

    if not answer:
        return "N"
    
    return ''.join(sorted(list(answer)))

🏉 분석 및 후기

• 시간복잡도 : O(len(input_string)) ~= O(n) / 마지막 답을 위한 처리는 최악의 경우 26개 밖에 없기에 상수 처리 가능
• 공간복잡도 : count는 26개만 담고 있기에 상수 처리 가능 / answer 마저 최대 26개이기에 O(1)

후기는 너무 헛짓을 많이 했다. 스택으로 푸는 것인 줄 알고 접근 자체를 잘못했다. 데이터 구조부터 잘 짜 놓고 들어가면 시간을 단축할 수 있다.