[Algorithm/JS] 백준 1439번 뒤집기

🔗 문제 바로가기 (opens new window)

Question

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

예를 들어 S=0001100 일 때,

전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

Input

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

Output

첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

Example

Input 1

0001100

Output 1

1

Input 2

11111

Output 2

0

Input 3

0000001

Output 3

1

더 많은 예제는 상단 url 참고

Solution

알고리즘: Greedy 탐욕법

계획 세우기

입력값의 연속된 0의 그룹과 1이 그룹을 계산해 두 그룹의 수가 더 많은 그룹의 수를 출력

ex) 입력값이 11001100110011000001 일 때 아래와 같이 그룹지을 수 있다. 11 00 11 00 11 00 11 0000 1 1로 구성된 그룹이 5개, 0으로 구성된 4그룹

1. 입력값(input)을 한 글자씩 쪼개 배열로 받아온다.
2. 반복문을 사용할 것 → 반복문 시작은 1부터 : input 배열의 첫번 두번째 요소부터 시작하기 위함
3. 이전 인덱스 값과 현재 인덱스 값을 비교한다. 이전 인덱스의 값을 저장하기 위한 pre 변수 선언 → 초기 값은 input 배열의 첫번째 요소
4. 두 값이 다르다면 그룹으로 분리되는 지점이므로 pre 변수를 현재 값으로 교체해준다.
5. 분리 지점에서 현재 값이 0 이라면 zero 변수 카운트, 1이라면 one 변수 카운트
6. 두 카운트 변수중 작은 변수 출력

나의 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? 'dev/stdin' : '../input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('');

let pre = input[0];
let one = 0;
let zero = 0;

for (let i = 1; i < input.length; i++) {
  let cur = input[i];
  if (pre !== cur) {
    pre = cur;
    if (cur === '1') one++;
    else zero++;
  }
}
console.log(Math.min(one, zero));

계획과 풀이 비교

첫 그룹의 수가 카운트 되지 않아 실제 그룹 수보다 1이 작게 출력되는 것을 확인했다.

사실 입력값이 0과 1이 돌아가면서 나오는 수이기 때문에 답에 영향이 있진 않지만 정확한 풀이가 아니기 때문에 아래 코드를 추가했다.

변수를 선언한 다음 반복문 실행 전 pre 변수의 초기 값이 0이라면 zero를 카운트 하고, 1이라면 one 변수를 카운트한다.

if (pre === '0') zero++;
else one++;

최종 풀이

const fs = require('fs');
const filePath = process.platform === 'linux' ? 'dev/stdin' : '../input.txt';
const input = fs.readFileSync(filePath).toString().trim().split('');

let pre = input[0];
let one = 0;
let zero = 0;

if (pre === '0') zero++;
else zero++;

for (let i = 1; i < input.length; i++) {
  let cur = input[i];
  if (pre !== cur) {
    pre = cur;
    if (cur === '1') one++;
    else zero++;
  }
}
console.log(Math.min(one, zero));