BOJ_1439 뒤집기

• TOC {:toc}

이 글은 백준 온라인 저지의 1439번 문제를 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.07.12 (Python)

S = input()
count = 0
for i in range(1, len(S)):
    # 현재 문자가 첫 문자와 다르고
    # 이전 문자는 첫 문자와 같으면
    if S[i] != S[0] and S[i - 1] == S[0]:
        # 개수를 1 증가시킨다.
        count += 1

print(count)

아이디어 & 풀이

문자열은 한 개 이상의 1의 모음과 한 개 이상의 0의 모음이 번갈아 가면서 존재하는 형태이다.

• e.g., 00011101001010011 → 000 / 111 / 0 / 1 / 00 / 1 / 0 / 1 / 00 / 11

모든 숫자를 같게 만들려면 0의 모음을 1의 모음으로 바꾸던가 그 반대를 해 주면 된다.

• 하나의 숫자 모음을 바꿀 때 뒤집는 횟수가 1 증가하고,
• 처음 시작하는 수의 모음은 그렇지 않은 수의 모음의 개수보다 항상 크거나 같다.
  • 위의 예시에서 문자열이 1의 모음으로 끝나면 0의 모음과 1의 모음의 개수가 같고,
  • 0으로 끝나면 0의 모음의 개수가 더 크다.

그러므로 뒤집기 횟수를 최소로 하려면 처음 시작하는 수가 아닌 수의 모음 뒤집어야 한다.

• 위의 예시에서는 1의 모음을 0의 모음으로 바꾸는 횟수이다.
• 0의 모음에서 1의 모음으로 넘어갈 때마다 개수를 1씩 증가시키면 된다.
  • 이전 원소는 0이고, 현재 원소는 1일 때, 1의 모음이 나타나는 것으로 볼 수 있다.

참고 답안

# 풀이 1-1
S, count = input(), 0
for i in range(1, len(S)):
    if S[i] != S[i - 1]:
        count += 1

print((count + 1) // 2)

# 풀이 1-2
print((input().count("10") + input().count("01") + 1) // 2)

2022.04.06 (JS)

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim();

function main() {
    const N = input.length;
    let count = [0, 0];
    count[parseInt(input[0])] += 1;

    for (let i = 1; i < N; i += 1) {
        if (input[i] !== input[i - 1]) {
            count[parseInt(input[i])] += 1;
        }
    }
    return Math.min(...count);
}

console.log(main());

아이디어 & 풀이

0의 모음과 1의 모음은 번갈아 나오기 때문에 둘의 개수 차이는 없거나 한 개이다.

• e.g. 1, 000 / 111 / 0 / 1 / 00 / 1 / 0 / 1 / 00 / 11 → 0의 모음: 5개, 1의 모음: 5개
• e.g. 2, 000 / 111 / 0 / 1 / 00 / 1 / 0 / 1 / 00 → 0의 모음: 5개, 1의 모음: 4개

그러므로 0과 1에 상관없이 일단 모든 숫자 모음의 수를 센 다음에 2로 나누어도 최소 뒤집기 횟수를 구할 수 있다.

• e.g. 1, 10 // 2 → 5
• e.g. 2, 9 // 2 → 4

모든 숫자 모음의 개수는 숫자가 바뀌는 지점의 수 + 1과 같다.

• 구역의 개수 = 경계의 개수 + 1로 생각하면 된다.
  • 숫자 모음: 구역, 숫자가 바뀌는 지점: 경계
• 풀이 1-1 에서는 모든 문자를 순회하면서 이전 문자와 다음 문자를 비교했다.
• 풀이 1-2 에서는 count를 이용해 경계인 01과 10의 개수를 세서 더했다.