[구름 알고리즘 먼데이 챌린지] 2주차 | 문제2 공통 문자열 | 파이썬

2주차 | 문제 2. 공통 문자열

문제

문자열 s가 주어졌을 때, 아래의 기준에 따라서 문자열을 분리하고 분리된 개수를 출력하시오.

• 같은 문자끼리 하나의 집합이 된다.
• 같은 문자라도 떨어져 있다면 다른 집합이 된다.

예시로 문자열 aabbcca는 {aa}, {bb}, {cc}, {a} 로 총 4개의 분리 집합을 가지고 있다. 문자열이 주어질 때, 조건에 따라서 분리된 집합의 개수를 출력하시오.

입력

첫째 줄에 문자열의 길이 n(1≤N≤10,000)이 주어진다.

둘째 줄에 문자열 s가 주어진다. 문자열 s는 알파벳 소문자만 가지고 있다.

출력

분리된 집합의 개수를 출력하시오.

---

구름 정답 코드

n = int(input()) # 문자열의 길이
arr = input() # 문자열
cnt = 0 # 분리 횟수
for i in range(n-1):
    if arr[i+1] == arr[i]: # 다음 문자와 같은 경우
        continue
    else: # 다음 문자와 다른 경우 분리 횟수 +1
        cnt += 1

print(cnt+1)

이 문제는 집합이 아닌 집합의 “개수”를 구하는 것에 초점을 맞추어야 했다. 집합의 개수를 구하는 방법은 다음과 같다.

주어진 문자열에서 현재 문자와 다음 문자가 다를 경우 분리하므로 분리횟수 + 1 = 집합의 개수이다.
ex) 막대기 한 개를 한 번 자르면 = 2개의 막대기가 됨(자른 횟수+1)

오답

n=int(input()) # 문자열의 길이
s=input() # 문자열

c=0 # 집합의 개수
sub=[] # aa처럼 같은 문자가 있는 경우 해당 문자(a)를 저장할 리스트
for i in range(n-1):
	if s[i]==s[i+1]: # 다음 문자랑 같은 경우
		sub.append(s[i])
	else: # 다음 문자랑 다른 경우
		c+=1

if len(sub)>0: # 겹치는 문자가 있었을 경우
	c=c+len(sub) # 겹친 문자 개수만큼 c에 더해줌
else: # 겹치는 문자가 없었을 경우
	c+=1 # 마지막 문자는 for문에서 체크하지 않았으므로 +1(마지막 문자)
print(c)

집합에 초점을 맞추게 되어 집합을 구하고 그에 대한 개수를 통해 답을 구하려다보니 모든 경우의 수를 헤아릴 수 없었다.
주어진 2개의 테스트 케이스는 통과했지만, 제출 시에는 오답으로 채점되었다. 그 이유를 생각해보니 다음 문자랑 같으면 계속해서 리스트 sub에 요소를 추가하게 되어 주어진 테스트 케이스에는 맞을 지라도 다른 경우에는 잘못된 답을 출력할 수도 있었다.

중복되는 요소를 제거하기 위해 len(sub)이 아닌 set(sub)도 생각해봤지만 ooobooo 와 같은 문자열이면 sub에 저장된 o를 다 하나로 생각하게되어 더더욱 맞지 않는 코드가 되었다.

이 코드로 정답을 구하기 위해서는 조금 더 생각해보아야 할 것 같다.