Greedy) 문자열 뒤집기

문자열 뒤집기

<이것이 취업을 위한 코딩테스트다, 313p, 나동빈, 한빛미디어>

🎅첫번째 접근

두 가지 방법을 생각해봤다.
첫번째는 맨 앞의 숫자를 기준으로 순서대로 연속해있는 숫자를 뒤집어주는 경우
두번째는 외곽에서 안쪽으로 오면서 점점 숫자를 뒤집어 주는 경우
몇 가지 예시로 계산해봤더니 두 방법의 계산 횟수는 같았다.

더 코드로 작성하기 쉬운 첫번째 방법으로 구현했다.

s = "11001110101011100"

flag = False
count = 0
# 맨 앞의 숫자를 기준으로 두는게 최적이다.
head = s[0]

for x in s:
	# False인 경우 head와 현재 원소가 같으면 계산할 필요x, 달라질때 횟수 +1, True로 변경
    if flag == False:
        if x != head:
            flag = True
            count += 1
    # True인 경우 head와 현재 원소가 다르면 계산x, 같아질 때에 False로 변경
    else:
        if x == head:
            flag = False

print(count)

✍피드백

해설 코드는 문자열을 모두 0으로 변경했을 때와 모두 1로 변경했을 때의 count 횟수를 각각 구해서 더 적을 쪽을 선택하도록 구현했다.
그런데,
맨 앞의 원소와 맨 뒤의 원소가 같으면 -> 맨 앞의 원소로 정렬 횟수 = 맨 뒤의 원소로 정렬 횟수 -1
맨 앞의 원소와 맨 뒤의 원소가 다르면 -> 맨 앞의 원소로 정렬 횟수 = 맨 뒤의 원소로 정렬
이라면 무조건 맨 앞의 원소로 정렬하는게 더 효율적인 것 같다.