알고리즘_코딩테스트/이것이 코딩테스트다
[그리디] 문자열 뒤집기
논곰
2021. 12. 12. 00:49
"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.
소요시간: 20분
1. 문제 설명
- 0과 1로 이루어진 string에서 최소한의 뒤집기 연산을 수행해 모든 string을 0이나 1로 통일시켜라
2. 접근 방식
- for문을 한 번 돌아서 0인 경우와 1인 경우를 골라서 더 짧은 경우를 뒤집어주면 될 거 같다고 생각. 리스트에 인덱스를 기록했다.
- 투포인터 알고리즘을 활용해봤다.
-----
- 해답 코드의 경우 접근 방법은 나와 비슷했는데, 코드 상으로는 좀 달라져서 해당 코드도 확인해봤다.
3. 코드
- 내 코드
def changeString(x):
global zero, one
zero = 0
one = 0
end = 0
start = int(x[0])
def zero_one(x):
global zero, one
if x == "0":
zero +=1
elif x == "1":
one += 1
while end < len(x):
if x[start] != x[end]: # 달라지기 시작하면
zero_one(x[start])
start = end
end += 1
if x[end-1] == x[-1]:
zero_one(x[start])
answer = min(zero, one)
print(one, zero)
return answer
- 해답 코드
data = input()
count0 = 0
count1 = 0
# 첫 번째 원소 처리
if data[0] == '1':
count0 +=1
else:
count1 +=1
# 두 번째 원소부터 모든 원소 확인
for i in range(len(data)-1):
if data[i] != data[i+1]:
if data[i+1] =='1':
count0 +=1
else:
count1 +=1
print(min(count0, count1))
4. 코멘트
- 중복되는 코드가 있어 함수를 내장함수로 만들고 global 변수사용해봤는데 쉽지 않네...
- 코드를 더 줄일 수 있는 부분이 있을 거 같은데 시간을 정해놓고 풀다보니까 효율성을 같이 고려하기 쉽지 않았었던 것 같다.
- 확실히 해답 코드가 훨씬 간결하고 좋아 보인다.