[프로그래머스 lv.1] 문자열 나누기 (건너뛴 문제 다시풀기)

문제

문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다.

• 먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다.
• 이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다.
• s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 종료합니다.
• 만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료합니다.

문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요.

---

제한사항

• 1 ≤ s의 길이 ≤ 10,000
• s는 영어 소문자로만 이루어져 있습니다.

 

예전 풀이

생각

문제가 이해 안된다고 써놨다..

 

코드

 

 

다시 생각해보기

생각

예시로든 바나나를 보면

첫 번째 글자가 b라서 'is b' +1, 그 다음은 a로 b가 이니기 때문에 'not b' +1

이렇게 되면 b인것과 b가 아닌 것의 수가 모두 1로 같아지지므로 문자를 분리해낸다

분리 후 첫 글자인 n

'is n' +1, 그 다음 글자는 a로 n이 아니기 때문에 'not n' +1

이렇게 되면 n인 것과 n이 아닌 것의 수가 모두 1로 같아지므로 문자를 분리해낸다

이런 로직의 반복인 것 같다.

 

딕셔너리를 만든다

key로는 'same'과 'not_same'문자열을 갖는다.

주어진 문자열을 돌면서

s[0]과 같다면 same의 value에 1을 더하고

s[0]과 같지 않다면 'not_same'의 value에 1을 더한다.

만약 두 키의 벨류가 같다면 현재 i를 기준으로 나누고(슬라이싱 이용?) 뒷부분을 다시 s에 저장한다

슬라이싱 n번에 문자열은 n+1개가 된다. 즉 슬라이싱 횟수를 세야 한다. n+1에서 +1은 맨 마지막에 하기로 하고 answer에 +=1을 해준다(굳이 변수를 더 생성할 것 없이 바로 answer에)

(나머지 경우에 대해서는 for문을 계속 돌게 한다)

 

모든 for문을 다 돌았다면 마지막으로 answer에 +1을 해준다.

 

코드

1차 시도

def solution(s):
    answer = 0
    first_word = {}
    first_word['same'] = 0
    first_word['not_same'] = 0
    i = 0
    while i < len(s):
        if s[i] == s[0]:
            first_word['same'] += 1
        else:
            first_word['not_same'] += 1
        
        if first_word['same'] == first_word['not_same']:
            s = s[i:]
            answer += 1
            i += 1
        else:
            i += 1
            
    answer += 1
    return answer

- for문으로 도니 중간에 문자열을 나누고 나서 문자열의 길이등의 이유로 string index out of range 에러가 나서 while문으로 시도

- 코드 실행 중 1개 통과

- 파이썬 튜터를 돌려본 결과  슬라이싱 범위를 i+1부터로 설정해야하는 것 같다

- 그리고 새로운 문자열에 대해 검사할 때 딕셔너리를 초기화 시켜야 한다

- 문자가 하나만 남았을 경우에 대해서도 조건을 달아줘야 하는데 그 부분을 고려하지 않았다.

- 그리고 마지막 answer에 굳이 1 더해주지 않아도 되는 듯....?

 

2차 시도

def solution(s):
    answer = 0
    first_word = {}
    first_word['same'] = 0
    first_word['not_same'] = 0
    i = 0
    while i < len(s):
        if s[i] == s[0]:
            first_word['same'] += 1
        else:
            first_word['not_same'] += 1
        
        if first_word['same'] == first_word['not_same']:
            s = s[i+1:]
            answer += 1
            if len(s) == 1:
                answer += 1
                break
            else:
                first_word['same'] = 0
                first_word['not_same'] = 0
                i = 0
        else:
            i += 1

    return answer

- 코드 실행은 전부 통과 but 채점 결과는 81점. 시간 초과 문제는 아닌 것 같은데 내가 또 놓친 조건이 있나?

 

 

다른 사람 풀이

def solution(s):
    answer = 0  # 분해한 문자열의 개수
    isx, isnotx = 0, 0  # x와 같은 글자 수, 다른 글자 수
    for i in range(len(s)):
        if isx == isnotx:  # 두 횟수가 같으면 분리(answer+1)
            answer += 1
            x = s[i]
            isx, isnotx = 0, 0
            
        if s[i] == x:
            isx += 1
        else:
            isnotx += 1
            
    return answer

코드 스스로 해석하고 이해하기

- 첫 글자와 같은 것을 셀 변수 다른 것을 셀 변수를 초기화한다

- s의 길이만큼 순회하면서

- 만약 같은 것과 다른 것의 갯수가 같다면 answer에 1을 더하고 x에 현재 숫자를 인덱스로 갖는 s의 요소를 대입한다. 갯수를 세고 있는 두 변수를 0으로 바꿔준다

- 만약 현재 숫자를 인덱스로 갖는 s의 요소가 첫 번째 글자변수 x와 같다면 같은 것을 세는 변수에 +1을 해주고

- 그렇지 않다면 다른 것을 세는 변수에 +1을 해준다.

 

https://dduniverse.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%AC%B8%EC%9E%90%EC%97%B4-%EB%82%98%EB%88%84%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC-python

프로그래머스 | 문자열 나누기 [파이썬 python]