본문 바로가기
알고리즘/백준 solved.ac PS

[백준][solved.ac][Silver 5][Python] 1439번 : 뒤집기

by 빛밤하늘 2021. 5. 25.
반응형

밑의 링크는 백준에서의 문제 링크입니다.

 

1439번: 뒤집기

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모

www.acmicpc.net

 

 

 

 

 

 

 

 

파이썬 코드와 결과입니다.

# readline을 사용하기 위해 import합니다.
from sys import stdin

# 첫째 줄에 1과 0으로만 이루어진 문자열 S를 입력합니다.
# S의 길이는 100만보다 작습니다.
S = stdin.readline().rstrip()

# 문자열 S에서 연속된 1로만 이루어진 구간들을 저장하는 리스트 변수를 선언합니다.
one_sections = list(filter(lambda section: section != '', S.split('0')))
# 문자열 S에서 연속된 0으로만 이루어진 구간들을 저장하는 리스트 변수를 선언합니다.
zero_sections = list(filter(lambda section: section != '', S.split('1')))

# 연속된 1로만 이루어진 구간들의 개수를 저장하는 변수를 선언합니다.
one_sections_cnt = len(one_sections)
# 연속된 0으로만 이루어진 구간들의 개수를 저장하는 변수를 선언합니다.
zero_sections_cnt = len(zero_sections)

# 연속된 1로만 이루어진 구간들의 개수와 연속된 0으로만 이루어진 구간들의 개수 중 더 작은 것의 개수를 출력합니다. 
print(min(one_sections_cnt, zero_sections_cnt))

결과

 

첫 번째 제출한 코드에서는 min 대신 실수로 max를 넣어버려 틀렸습니다 결과가 나왔습니다.

그리고 제출하고 나서 카테고리를 확인해보니 그리디 알고리즘을 의도한 문제였습니다.

저는 풀 때 파이썬 내장 함수로만 풀어서 그런 생각을 하지 못했는데

다음에 그리디 알고리즘을 염두에 두고 푸는 연습을 해봐야겠습니다.

 

 

 

※ 궁금한 부분, 이상한 점 및 오타는 댓글에 부탁드립니다.

※ 더 효율적이고 빠른 정답을 환영합니다.

반응형

댓글