백준 20365번: 블로그2 (Python/Java)

https://www.acmicpc.net/problem/20365

20365번: 블로그2

 

 

 

접근

---

문제로 주어지는 글자의 최대 길이는 50만이다. 때문에 모든 경우의 수를 탐색해 가장 적은 작업 횟수를 구하는 방법은 당연하게도 시간 초과가 뜬다. 어떤 선택이 가장 적은 작업 횟수를 구할 수 있는지 그 최선의 방법을 확인해봐야 한다. 사실 어려운 조건이 아니라 방법을 쉽게 파악할 수 있을 것이다. 처음에서 마지막까지 전부 하나의 색깔로 칠하고 중간중간 다른 색깔이 들어가있는 것을 파악하는 것이다.

 

예제를 살펴보자. 'BBRBRBBR'을 처음부터 마지막까지 한 번에 칠한다. 최종 결과 값에 우선 1을 더한다. 이제 처음부터 끝까지 탐색하며 첫 글자와 다른 글자 구간이 몇 번 나오는지 확인하고 최종 결과 값에 구간 한번 당 1씩 더해주면 된다. 이때 'R' 한 번에  1씩 더하는 것이 아니라는 것을 주의해야 한다. 만약 'RR'처럼 연속해서 나온다면 이는 한 번에 칠해줄 수 있으니 2가 아니라 1만 더해진다는 점을 명심하자.

 

 

 

풀이

---

Python

length = int(input())
sentence = input()

result = 1
whileNum = 0
while whileNum < length:
    if sentence[0] != sentence[whileNum]:
        while sentence[0] != sentence[whileNum]:
            if whileNum < (length-1):
                whileNum += 1
            else:
                break
        result += 1
    whileNum += 1

print(result)

 

Java

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);
        int length = Integer.parseInt(scan.nextLine());
        String[] sentence = (scan.nextLine()).split("");

        int result = 1;
        for (int i = 0; i < length; i++) {
            if (!sentence[0].equals(sentence[i])) {
                for (int j = i; j < length; j++) {
                    if (!sentence[0].equals(sentence[j])) {
                        i++;
                    } else {
                        break;
                    }
                }
                result += 1;
            }

        }

        System.out.println(result);

    }

}

 

 

 

후기

---

이번 문제는 파이썬과 자바 코드를 다르게 작성했다. 피치 못하게 파이썬에서 while을 써야 했기 때문인데 이렇게 되면 풀면서도 머릿속에서 엉키는 경우가 종종 있다. 같은 원리더라도 그때그때 상황에 따라 다양한 방식으로 작성해보는 연습을 조금 더 해야겠다.