[알고리즘] SW Expert Academy 10033. 카드 뒤집기

문제풀이(사고의 흐름)

---

문제를 보고 처음에는 어떻게 풀어야할지 바로 감이 오지 않았다. 문자열과 문자열을 바꿀수 있는 동작을 주고, 동작이 최대 몇번 수행되어야 하는지 조건이 주어졌지만, 바로 풀이 코드가 떠오르지 않았다. 이런 상황에서는 샘플을 만들고 이를 조건대로 수행하며 법칙을 찾아내는 편이다. 그래서 예제 문자열을 조건에 따라 동작을 수행하여 보았다.

 

BWBWBW // 시작 문자열
WBBWBW // 동작수행 1
WBWBBW // 동작수행 2
WWBBBW // 동작수행 3
WWBBWB // 동작수행 4
WWBWBB // 동작수행 5
WWWBBB // 동작수행 6

 

 

이렇게 샘플을 한번 돌려보니, 바로 직감이 떠올랐다. "모든 수행의 끝에는 결국 모든 W는 왼쪽으로 가고, 모든 B는 오른쪽으로 가는구나!". 그리고 다시 동작 조건과 그 결과를 해석해 보니, 간단한 풀이법이 떠올랐다.

 

BW를 찾고, 이를 WB로 바꾼다. 

-> W가 B의 오른쪽에 있다면, 왼쪽으로 옮긴다.

-> 결국 모든 W는 오른쪽으로 간다.

-> 각 W는 왼쪽으로 가기위해 (자신의 위치 - 자신의 왼쪽에 위치한 W의 개수) 만큼 이동해야한다.

-> 각 W의 이동개수를 더하면 정답!

 

BWBWBW
- 첫번째 W 이동 회수 = 1 (1 - 0)
- 두번째 W 이동 회수 = 2 (3 - 1)
- 세번째 W 이동 회수 = 3 (5 - 2)
정답 = 6 (1 + 2 + 3)

 

 

정답코드

---

#include <iostream>

int main(void) {
    int t, total_cnt, a_cnt;
    long long ans;
    char cards[200001];
    
    scanf("%d", &t);
	
    for (int t_i = 1; t_i <= t; t_i++) {
        scanf("%s", cards);
        total_cnt = a_cnt = ans = 0;
        for (int i = 0; cards[i]; i++) {
            total_cnt++;
            if (cards[i] == 'W') {
                a_cnt++;
                ans += total_cnt - a_cnt;
            }
        }
        printf("#%d %lld\n", t_i, ans);
    }
    return 0;
}

 

 

마무리

---

문제의 정답을 알고보니, 허무할 정도로 간단한 문제였다. 하지만 만약 문제의 조건만 보고, 어떠한 알고리즘을 써야할지(DP, 이진탐색, 최단거리탐색 등) 찾는 방식으로 접근했다면 끝까지 답을 찾지 못했을 것이다. 최근 많은 기업들이 알고리즘 시험을 보고 그 시험들이 정형화되면서, 문제를 보고 "이 알고리즘을 사용하는 문제일 것이다!" 라고 답을 정해놓고 문제를 푸는 사람들을 많이 보았다. 하지만 알고리즘은 답을 정해놓고 풀려고 하면 안된다고 생각한다. 문제의 답을 찾는 과정에서 자연스럽게 논리가 세워지고, 그 논리가 알고리즘이라고 생각한다. 알고리즘 코드를 외우고, 문제를 억지로 코드에 맞게 끼워 맞추는 것은 단순한 암기력 테스트일 뿐이다.