1439번: 뒤집기
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모
www.acmicpc.net
https://www.acmicpc.net/problem/1439
문제 해결을 위한 과정
예제 0001100을 보면 연속적으로 이루어진 000, 11, 00 이 존재하는 것을 알 수 있다. 문제를 잘 살펴보면 연속되어 있는 숫자는 모두 뒤집을 수 있기 때문에 연속되어있는 11을 뒤집으면 단 한 번의 행동을 통해 문자열 S의 모든 숫자를 전부 같게 만들 수 있다는 것을 알 수 있다. 따라서 이 문제는 문자열 S에서 연속되어있는 숫자들의 개수를 구한 뒤 그 최솟값을 출력을 하면 되는 쉬운 문제이다. 예시를 들어보자
1) 10101
이 경우 앞에서부터 조회하면서 1의 개수는 3개 0의 개수는 2개임을 알 수 있다. 따라서 둘중 적은 수인 2를 출력한다
2) 100011
이 경우 앞에서부터 조회하면서 연속된 1의 개수는 1, 11 로 2개이고 0의 개수는 000으로 하나이다. 따라서 적은 수인 1을 출력한다.
문제 해결을 위한 팁
이 경우 문자열에 0과 1이 아닌 다른 숫자를 붙여주면 쉽게 해결할 수 있다. num_of_zero와 num_of_one이라는 변수를 이용하여 문자열 S를 조회하며 앞과 뒤가 다른 경우 앞이 속해있는 진영의 숫자를 하나 증가시켜주면 해결할 수 있는데 문자열 S의 마지막 원소인 경우 이 방법을 적용하기 어렵기 때문에 마지막에 다른 숫자(예를 들면 2)를 붙여주어 쉽게 이 문제를 해결할 수 있다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
data = input()
data += "2" # 입력받은 문자열 뒤에 임의의 문자를 붙인다
prev = int(data[0])
num_of_zero = 0
num_of_one = 0
'''
for문을 수행하면서 prev와 다음 수인 num이 서로 다른 경우 prev가 속한 집단의 숫자를
하나 증가시켜준다. 이 결과를 통해 예시 0001100의 경우 num_of_zero는 2가 num_of_one는 1이 된다.
'''
for i in range(1, len(data)):
num = int(data[i])
if prev == 0 and num != prev:
num_of_zero += 1
elif prev == 1 and num != prev:
num_of_one += 1
prev = num
print(min(num_of_zero, num_of_one)) # num_of_zero 와 num_of_one중 최소값을 출력한다
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 18352: 특정 거리의 도시 찾기(Python) (0) | 2020.12.04 |
|---|---|
| 백준 알고리즘 15686: 치킨 배달 (Python) (0) | 2020.11.30 |
| 백준 알고리즘 3190: 뱀(Python, c++) (0) | 2020.11.29 |
| 백준 알고리즘 1914: 하노이 탑 (0) | 2020.11.28 |
| 백준 알고리즘 18406: 럭키 스트레이트 (Python) (0) | 2020.11.27 |