[백준_20365] 블로그2 ( 그리디 - 자바스크립트 )

문제

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

20365번: 블로그2

 

How to Solve ?

 

1. 문제를 이해 했는가 ?

 

특정 색깔로 칠해진 문자열을 주었을 때, 몇 번의 획을 통해 색을 칠할 수 있는지 물어 본 문제이다.

 

즉 ,내가 이해 하기로 예시에서 제공한 방법은 크게 2가지 인데

 

1)  획을 서로 번갈아가면서 긋기

 

1. ==  [2]

2. =

3. =

4. =

5. ==

6. =

 

 

2) 큰 획 + 수정

 

1.  ==== == =  [7]

2.  ==== === =[8]

3.  == === ===

4.  == ==== ==

 

 

 위와 같이 큰 획을 긋고 필요에 따라 변경 하는 방법을 채택하였다.

 

나는 여기서 영감을 얻고  [ 빨간색으로 1획 + 수정, 파란색으로 1획 + 수정 , 교차 ]  로 나누어 이 중에서 최소 값을 출력 하는 것을 목표로 코드를 짰다.

 

[2] 코드

 

위의 내용과 코드는 같지만, 조금 디테일을 잡은 부분이 있는데 그것은 바로 큰 1획을 그을 때 선의 끝 중에 1개가 색이 다르면 그 부분은 미리 처리를 해주고 넘어 갔다.

 

왜냐하면  BBBBBBR 이 있을 때,

 

 ==== == =   => ==== == = =

로 넘어가기 위해서는 [ 파란색 전체 1획 + 빨간색 덧칠 ], [ 7까지 파란색 1획 + 빨간색 1번 칠 ] 이렇게 두 가지 방법이 있는데 사실상 전자로 해도 상관은 없지만,  굳이 불 필요한 색을 칠 할 필요는 없었고 코드를 짤 당시에는 "획"에서 잠깐 벗어나 몇 번의 색을 칠하는지로 착각을 했었던 것 같다. 그래도 예외 사항을 처리 함에 있어서 불 필요한 상황을 처리 해주는 것은 좋은 습관이라 생각한다.

 

 

function strokeWithRed() {
  let count = 0;
  const redString = Array(n).fill("R");

  if (s[0] === "B" && s[n - 1] === "R") {
    redString[0] = "B";
    count += 1;
  }

  if (s[n - 1] === "B" && s[0] === "R") {
    redString[n - 1] = "B";
    count += 1;
  }

  for (let i = 0; i < n; i++) {
    if (s[i] !== redString[i]) {
      count += 1;
    }
  }
  return count;
}

function strokeWithBlue() {
  let count = 0;
  const redString = Array(n).fill("B");

  if (s[0] === "R" && s[n - 1] === "B") {
    redString[0] = "B";
    count += 1;
  }

  if (s[n - 1] === "R" && s[0] === "B") {
    redString[n - 1] = "B";
    count += 1;
  }

  for (let i = 0; i < n; i++) {
    if (s[i] !== redString[i]) {
      count += 1;
    }
  }
  return count;
}

function strokeWiteMixed() {
  let count = 1;
  let checked = s[0];

  for (let i = 0; i < n; i++) {
    if (s[i] !== checked) {
      checked = s[i];
      count++;
    }
  }
  return count;
}

function solve() {
  let answer = Math.min(strokeWithRed(), strokeWithBlue(), strokeWiteMixed());

  console.log(answer);
}

const n = 8;
let s = "BBR BR BBR";
solve();

[3] 리팩토링

그리디라는 개념이 크게 와닿지 않아서, 스터디원들과 함께 이야기를 나누어보았다.

 

나는 세가지의 색으로 나누어 접근을 하는 방식을 이용 했기에, '구현'에 가까운게 아닐까? 라는 의문을 가졌는데 아래와 같은 방법으로 바꾼다면 각 색깔에서 할 수 있는 '방법'을 정의하여 '그리디' 다운 풀이법이 나올 수 있다.

 

이제서야 느낀 그리디의 정의가 무엇일까? 생각해보면 내가 그 배열의 인덱스라면 할 수 있는 최선의 행동이 뭘까? 찾아내는 과정이 아닐까 생각한다.

function solve() {
 let base = s[0];
 let cnt = 1;
 
 for ( let i = 1; i < s.length; i++ ) {
 	
    if ( s[i] !== base && s[i] !== s[i-1) {
    	cnt += 1
    }
 }
}

const n = 8;
let s = "BBR BR BBR";
solve();

느낀점

 

"탐욕법이 뭐냐?" 질문하면 내가 답할 수 있는 답이라곤, < 현재 상황에서 최선을 다 하면 얻을 수 있는 것 > 정도라고 생각한다.

하지만, 뭔가 여러 문제를 풀면서  DP / BFS 와 같이 특정 방법을 적용 해야만 푸는 경우에는 "아 이건 이거구나" 라고 와닿는 반면에 이런 문제를 풀면 내가 세워놓은 정의와 엇나가는 문제들을 많이 만나게 되는 것 같다.

 

실제로도 이번 문제를 풀으면서도, 그리는 사람의 입장이 되어 어떻게 하면 최소한의 "획"을 통해 그려 낼 수 있을까로 생각하며 풀어서 그리디 답게 푼게 맞는거 같기도 하면서, 또  어떨 때는 변수의 입장에서 처리 해야 하는 상황도 생기는 것 같고.  어정쩡한 기분이 든다.