코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.
- IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
- 상세 설명 - 수원대학교(대학일자리 플러스센터)
PCCP 모의고사 #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"
문자열 input_string이 주어졌을 때, 외톨이 알파벳들을 알파벳순으로 이어 붙인 문자열을 return 하도록 solution 함수를 완성해주세요. 만약, 외톨이 알파벳이 없다면 문자열 "N"을 return 합니다.
제한사항
- 1 ≤ input_string의 길이 ≤ 2,600
- input_string은 알파벳 소문자로만 구성되어 있습니다..
입출력 예
| input_string | result |
|---|---|
| "edeaaabbccd" | "de" |
| "eeddee" | "e" |
| "string" | "N" |
| "zbzbz" | "bz" |
입출력 예 설명
입출력 예 #1
- 문제 예시와 같습니다.
외톨이 알파벳인 e, d를 알파벳순으로 이어 붙여 문자열을 만들면 "de"가 됩니다.
입출력 예 #2
- 문제 예시와 같습니다.
입출력 예 #3
- 모든 문자들이 한 번씩만 등장하므로
외톨이 알파벳이 없습니다.
입출력 예 #4
외톨이 알파벳인 z, b를 알파벳순으로 이어 붙여 문자열을 만들면 "bz"가 됩니다.
코드
from collections import defaultdict
def solution(input_string):
sH = defaultdict(int)
answer = []
stack = []
for x in input_string:
if not stack:
stack.append(x)
sH[x] += 1
else:
if stack[-1] != x:
stack.clear()
stack.append(x)
sH[x] += 1
else:
stack.append(x)
for key in sH:
if sH[key] > 1:
answer.append(key)
if answer:
return ''.join(sorted(answer))
else:
return "N"
풀이
- 먼저
defaultdict(int)를 이용해 모든key값을0으로 초기화해 sH에 저장 stack이 비어있다면,stack에x삽입하고sH[x] += 1stack이 비어있지 않고 마지막으로 삽입된 값이x와 같지 않다면,stack을 비우고stack에x삽입하고sH[x] += 1stack이 비어있지 않고 마지막으로 삽입된 값이x와 같다면stack에x삽입for문이 종료된 후sH[key] > 1라면, 외톨이 알파벳이므로answer에key삽입- 외톨이 알파벳이 하나라도 존재한다면 외톨이 알파벳을
answer에 모두 삽입하고,sorted를 통해 정렬한 후join을 이용해return - 존재하지 않는다면
return "N"
즉, 이 문제는 붙어있거나 1개만 존재한다면 sH[key]의 value는 1이 되고, 외톨이 알파벳이라면 value는 1보다 크도록 설정되어 있다.
끄적끄적