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
맨 앞의 원소와 맨 뒤의 원소가 다르면 -> 맨 앞의 원소로 정렬 횟수 = 맨 뒤의 원소로 정렬
이라면 무조건 맨 앞의 원소로 정렬하는게 더 효율적인 것 같다.
Author And Source
이 문제에 관하여(Greedy) 문자열 뒤집기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mongle/Greedy-문자열-뒤집기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)