프로그래머스 | Python | Greedy | 문자열 나누기 (Lv.1)

https://school.programmers.co.kr/learn/courses/30/lessons/140108

프로그래머스

 

문제 풀이: 문자열 나누기

문제를 해결하기 위해 문자열을 차례로 탐색하면서 규칙에 따라 분리합니다.

규칙은 다음과 같습니다:

1. 첫 글자를 기준으로 그룹화:
   •   첫 글자를 x로 설정.
   •   x의 등장 횟수와 x가 아닌 글자의 등장 횟수를 셈.
2. 횟수 비교:
   •   x와 x가 아닌 글자의 등장 횟수가 같아질 때 문자열을 분리.
3. 남은 문자열 반복:
   •   분리한 문자열을 제거하고, 남은 부분에 대해 동일한 작업을 수행.
4. 남은 문자열 처리:
   •   더 이상 읽을 글자가 없거나 횟수가 다르면 해당 문자열을 분리.

---

코드 구현

def solution(s):
    answer = 0  # 분리된 문자열 개수
    count_x = 0  # x의 등장 횟수
    count_other = 0  # x가 아닌 글자의 등장 횟수

    # 문자열을 순차적으로 탐색
    while s:
        x = s[0]  # 첫 글자
        count_x = 0
        count_other = 0

        for i, char in enumerate(s):
            if char == x:
                count_x += 1
            else:
                count_other += 1

            # x와 다른 글자의 등장 횟수가 같으면 분리
            if count_x == count_other:
                answer += 1
                s = s[i + 1:]  # 분리된 부분 제거
                break
        else:
            # 남은 문자열 처리
            answer += 1
            break

    return answer

---

코드 흐름 설명

1. while s:
   •   문자열 s가 남아 있는 동안 반복.
2. 첫 글자 설정:
   •   x = s[0]으로 기준 글자를 설정.
   •   count_x와 count_other로 각 글자들의 등장 횟수를 저장.
3. 횟수 비교 및 분리:
   •   문자열을 순차적으로 탐색하며 x와 다른 글자의 횟수를 비교.
   •   두 횟수가 같아지는 순간 문자열을 분리.
4. break의 역할

if count_x == count_other:
                answer += 1
                s = s[i + 1:]  # 분리된 부분 제거
                break

break는 count_x == count_other 조건이 충족된 즉시 for 루프를 중단합니다.

• 이렇게 하면:
  1. answer를 올리고,
  2. 문자열 s를 남은 부분(s[i + 1:])으로 잘라,
  3. 다음 while 루프에서 남은 문자열을 처리.

5.for-else 동작 분석

1. for 문:
   •   문자열 s를 순회하면서 조건(count_x == count_other)이 충족되면 break를 통해 분리 작업을 수행합니다.
   •   이때 break가 발생하면 else 블록은 실행되지 않습니다.
2. else 문:
   •   for 문이 모든 글자를 탐색했지만, count_x == count_other 조건이 충족되지 않을 때 실행됩니다.
   •   남은 문자열이 더 이상 나눌 수 없는 상태로, 이 문자열 자체를 하나의 분리된 문자열로 간주하고 answer를 증가시킵니다.
   •   break는 문자열 탐색을 완료했음을 나타내고 while 루프를 종료합니다.

---

예시 입력:

s = "banana"

초기 상태

• answer = 0 (분리된 문자열 개수)
• count_x = 0 (x의 등장 횟수)
• count_other = 0 (x가 아닌 글자의 등장 횟수)
• s = "banana"

---

1번째 루프:

• x = s[0] → x = 'b' (첫 글자)
• count_x = 0, count_other = 0 (초기화)

문자열 탐색 (for 루프):

• 1번째 글자: 'b'
  • 'b' == 'b' → count_x += 1 → count_x = 1
• 2번째 글자: 'a'
  • 'a' != 'b' → count_other += 1 → count_other = 1
• count_x == count_other (1 == 1) → 문자열 분리.
  • answer += 1 → answer = 1
  • s = s[2:] → s = "nana"

---

2번째 루프:

• x = s[0] → x = 'n'
• count_x = 0, count_other = 0 (초기화)

문자열 탐색 (for 루프):

• 1번째 글자: 'n'
  • 'n' == 'n' → count_x += 1 → count_x = 1
• 2번째 글자: 'a'
  • 'a' != 'n' → count_other += 1 → count_other = 1
• count_x == count_other (1 == 1) → 문자열 분리.
  • answer += 1 → answer = 2
  • s = s[2:] → s = "na"

---

3번째 루프:

• x = s[0] → x = 'n'
• count_x = 0, count_other = 0 (초기화)

문자열 탐색 (for 루프):

• 1번째 글자: 'n'
  • 'n' == 'n' → count_x += 1 → count_x = 1
• 2번째 글자: 'a'
  • 'a' != 'n' → count_other += 1 → count_other = 1
• count_x == count_other (1 == 1) → 문자열 분리.
  • answer += 1 → answer = 3
  • s = s[2:] → s = "" (빈 문자열)

---

루프 종료

• s가 빈 문자열이므로 while s 조건이 거짓이 되어 종료.

---

최종 결과:

• answer = 3

---

핵심 알고리즘: 그리디 알고리즘

• 문자열을 탐색하면서 가능한 가장 작은 단위로 문자열을 나눔.
• 분리 시마다 나머지 문자열을 다시 처리.

---

출제 의도

1. 문자열 탐색 및 조건 처리:
   •   문자열을 순차적으로 탐색하며 조건을 만족하는 지점을 찾아 처리.
2. 그리디 접근법 활용:
   •   각 단계에서 가능한 가장 작은 크기로 문자열을 분리.
3. Python의 문자열 조작 활용:
   •   슬라이싱(s[i+1:])과 조건문을 사용해 문자열을 처리.

---

시간 복잡도

• O(n):
  •   문자열을 한 번 순차적으로 탐색.
  •   각 분리 작업은 일정 시간 소요.

공간 복잡도

• O(1):
  •   문자열 s를 인덱스로 처리하며, 추가적인 메모리 사용이 적음.

---

여기서 잠깐! for-else 구조의 동작

for-else 문이란?

• for 루프가 정상적으로 종료되면(즉, break를 만나지 않고 끝까지 실행되면) else 블록이 실행됩니다.
• 만약 for 루프가 중간에 break로 종료되면, else 블록은 실행되지 않습니다.

---

for-else 문 기본 구조

for element in iterable:
    # 반복문 내부
    if some_condition:
        break  # break가 실행되면 else는 실행되지 않음
else:
    # for 루프가 정상적으로 종료되면 실행
    # break가 실행되지 않은 경우에만 실행됨

---

for-else 동작 원리

1. for 루프 정상 종료:
   • for 루프가 iterable의 모든 요소를 순회한 뒤 종료되면 else 블록이 실행됩니다.
2. break로 종료:
   • break가 실행되면 루프가 즉시 종료되고, else 블록은 건너뜁니다.

---

예제

1. else 실행 예시

for num in range(5):
    print(num)
else:
    print("루프가 정상적으로 종료되었습니다.")

출력:

0
1
2
3
4
루프가 정상적으로 종료되었습니다.

• break가 없으므로 루프가 정상적으로 종료되고, else 블록이 실행됩니다.

2. break로 종료

for num in range(5):
    print(num)
    if num == 2:
        break
else:
    print("루프가 정상적으로 종료되었습니다.")

출력:

0
1
2

• break로 루프가 중단되었으므로 else 블록은 실행되지 않습니다.

---

for-else 실제 활용 예

소수 판별

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False  # 나누어 떨어지면 소수가 아님
    else:
        return True  # for 루프가 끝까지 실행되면 소수

설명:

•   숫자가 2부터 제곱근까지 나누어 떨어지지 않으면 else 블록이 실행되어 소수임을 반환합니다.

찾고자 하는 값 탐색

def find_value(lst, target):
    for val in lst:
        if val == target:
            print("값을 찾았습니다!")
            break
    else:
        print("값을 찾지 못했습니다.")

설명:

•   리스트를 순회하며 target을 찾으면 break로 루프 종료.
•   값을 찾지 못하면 else 블록 실행.

---

for-else의 특징

1. else는 루프의 성공 조건을 처리하는 데 유용합니다.
2. 단순한 if-else와는 다릅니다. for-else는 루프의 흐름에 의존합니다.
3. break 여부에 따라 동작이 결정됩니다.

---

for-else의 장점

• 루프 내부에서 조건 검사를 수행하고, 추가 처리가 필요한 경우 깔끔한 코드 작성 가능.
• break와 정상 종료에 따른 처리를 명확히 구분할 수 있음.