출처
: Programmers
문제
문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다.
- 먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다.
- 이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다.
s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 종료합니다.- 만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료합니다. 문자열
s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요.
(생략)
나의 풀이
시도했으나 실패한 것
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def solution(s):
input_str = s
sum_cnt = 0
first = input_str[0]
seperated = input_str[1:]
len_seperated = len(seperated)
# 문자열 길이 = 1인 경우 종료
# (종료 이후 sum_cnt + 1 해야함)
while(len_seperated >= 1):
# x인 거, 아닌 거 개수 세기
x_part = 1
not_x_part = 0
for i in range(len_seperated):
# 한 글자 읽기
temp_pick_chr = seperated[i]
if (temp_pick_chr == first):
x_part += 1
else:
not_x_part += 1
is_need_break = 1
# x_part == not_x_part 체크
# 여기서, 문자열 분리 해야함
# ㄴ "i" 번째
if (x_part == not_x_part):
is_need_break = 0
print(f"(pre) seperated: {seperated}")
sum_cnt += 1
'''
b a n a n a
0 1 2 3 4 5
'''
seperated = seperated[i+1:]
first = seperated[0]
len_seperated = len(seperated)
print(f"(aft) seperated: {seperated}")
break
else:
if (i + 1 == len_seperated):
is_need_break = 1
sum_cnt += 1
# is_need_break=1 하는 순간
# - 두 횟수가 다른 상태
# AND
# - 남은 부분이 없다면
if (is_need_break == 1):
break
print(f"sum_cnt: {sum_cnt}")
answer = []
return answer
성공한 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
'''
문자열 s = "banana"
==> x = "b"
'''
'''
그냥 읽는 족족
하나씩 계속 slice 하자!
'''
def solution(s):
sum_cnt = 0
seperated = s[:]
# 종료조건
# : 빈 문자열일 때
while(seperated != ""):
# 같을 때 카운트
same_x = 0
# 다를 때 카운트
not_same_x = 0
# 첫 번째 문자 저장
first = seperated[0]
i = 0
# 두 개의 카운트가 같을 때는
# => break
# 서로 다를 때는
# AND 마지막 문자 참조한 경우에
# => return (sum_cnt+1)
# 이므로 loop 종료는 꼭 보장됨
while(True):
temp_pick_chr = seperated[i]
if (temp_pick_chr == first):
same_x += 1
else:
not_same_x += 1
# 두 카운트가 동일해진 순간에
if (same_x == not_same_x):
sum_cnt += 1
# 지금까지 참조한 문자열을
# 그 이후 문자열과 분리시킴
seperated = seperated[i+1:]
# loop 종료
break
else:
if (i + 1 == len(seperated)):
sum_cnt += 1
answer = sum_cnt
print(sum_cnt)
# 여기서 break는
# 두 번 필요하기 때문에
# 바로 return을 함
return answer
i += 1
print(sum_cnt)
answer = sum_cnt
return answer
며칠 전에 처음 시도했었다.
그러나
모든 테스트 케이스를 만족시키진 못해서
계속 수정하느라 코드가 불어났고
감당 못할 정도가 돼서 그만두었다.
그리고,
오늘(24일) 다시 시도해보았고
첫 시도에는 또 코드가 불어나서
다 지우고 다시 작성했다.
오히려 지우고 시작하니까 정리가 된 느낌이다.
이 문제는 구현이기 때문에
기본 아이디어는 문제에 그대로 있다.
다만, 내가 이렇게 해맨 이유는 이렇다.
문제에서 첫 번째 문자를 읽을 때,
이 문자를 제외하고 서로 비교하여 세는 줄 알았다.
세심하게 읽지 못한 잘못이다.
사소한 누락이 큰 차이를 불러온 셈이다…
다른 사람들의 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from collections import deque
def solution(s):
ans = 0
q = deque(s)
while q:
a, b = 1, 0
x = q.popleft()
while q:
n = q.popleft()
if n == x:
a += 1
else:
b += 1
if a == b:
ans += 1
break
if a != b:
ans += 1
return ans
(출처: 프로그래머스 스쿨 다른사람 풀이)
조금 입이 떡 벌어지는 정도로는
이 풀이 말고 첫 번째 풀이가 더 그렇지만,
구현의 수단, 방법에 있어서는
이 풀이가 일반적으로는 더 배울 만한 것 같다.
결국, 한 글자씩 읽는 것이므로
계속 leftpop()해도 괜찮은 것이다…!