Abbreviation

사이트: HackerRank
난이도: 미디움
분류: Dynamic programming

문제

어떤 문자열 a와 b가 주어졌을 때, a를 변환하여 b로 변경할 수 있으면 YES를 반환하고 변환할 수 없으면 NO를 반환해라.

a의 문자중 소문자는 생략하거나 대문자로 변환할 수 있다.

a = AbcDE
b = ABDE

a = ABDE로 변환이 가능하다.

1. 나의 풀이

늘 그렇듯이 dp 문제는 설정부터 잘못잡으면 시간이 너무 오래 걸린다. 그렇게 해서 해결할 수 있다면 좋지만, 매번 해결하지 못해서 시간만 버리고 있다는 느낌이 크게 든다.

이번 문제도 어떻게든 풀어보려 했지만, 결국 시간이 너무 오래 걸려서 다른 사람의 풀이를 참조하기로 했다.

function isLowerCase(c) {
    return c.charCodeAt() >= 'a'.charCodeAt();
}

function abbreviation(a, b) {
    // Write your code here
  
  	// a 문자의 소문자들을 치환할 수 있는 b 문자열의 인덱스에 배열로 담아둔다.
    const dp = Array.from(new Array(b.length + 1), () => []);
    const _b = [];
    let bi = 0;

    for (let i = 0; i < a.length; i++) {
        const c = a[i];
        
        if (!isLowerCase(c)) {
          	// 대문자 처리를 한다.
          	// while을 수행하는 이유는 bBaa => BBA 같은 케이스가 있어서
          	// 인덱스를 제일 뒤로 미루기 위함이다.
            if (c === b[bi]) {
                while (b[(bi++) + 1] === c);
            } else {
                while (bi < b.length && b[bi++] !== c);
            }
            _b[bi - 1] = c;

        } else {
          	// b 인덱스에 치환될 수 있는 a 문자들을 담아둔다.
            dp[bi].push(c);
        }
    }
    
    let queue = [];
  	// 정상적으로 치환될 수 있는지 확인한다.
    for (let i = 0; i < b.length; i++) {
        if (_b[i] === b[i]) {
            continue;
        } else if (_b[i] && !isLowerCase(_b[i])) {
          	// 대문자이면서 b와 다른 문자일 경우 NO를 반환한다.
            return 'NO';
        }
        
      	// b 인덱스가 증가된 곳 까지 a 문자가 존재하기 때문에 그 이 후는 dp에서 가져오지 않는다.
        if (i <= bi) {
            queue = dp[i];
        }

        while (queue.length) {
            const C = queue.shift().toUpperCase();
            if (C === b[i]) {
                _b[i] = C; 
                break;
            }
        }
        
        if (_b[i] !== b[i]) {
            return 'NO';
        }
    }
    
    return 'YES';
}

2. 다른사람의 풀이

dp 변수를 2차원 배열로 관리해서 푸는 문제이다. 2차원 배열로 작성하여 푸는 문제는 대부분 문자열을 비교하는 형태의 문제가 많은 것 같다.(제일 익숙하지 않고 어렵게 느껴지는 부분이다...)

아래 로직은 제일 간단하고 잘 짜여진 로직을 들고 왔다. 처음 봤을 때는 이해가 안갔는데, 실제 코드 흐름을 따라가 보니 코드가 이해되기 시작했다.

알고리즘은 진짜 최대한 효율적으로 짠 코드를 보고 학습하는게 좋다고 생각했다. 전혀 생각지도 못한 접근 방식을 볼 수 있기 때문이다.

function isLowerCase(c) {
    return c.charCodeAt() >= 'a'.charCodeAt();
}

// dp 변수 생성
function createDP(a, b) {
    return Array.from(
        new Array(a.length + 1),
        () => Array.from(
            new Array(b.length + 1),
            () => false
        )
    );
}

function abbreviation(a, b) {
    // Write your code here
    const dp = createDP(a, b);
    dp[0][0] = true;
    
    for (let i = 0; i < a.length; i++) {
        for (let j = 0; j < b.length + 1; j++) {
            if (dp[i][j]) {
                if (a[i].toUpperCase() === b[j]) {
                    dp[i + 1][j + 1] = true;
                }
                if (isLowerCase(a[i])) {
                    dp[i + 1][j] = true;
                }
            }
        }
    }
    
    return dp[a.length][b.length] ? 'YES' : 'NO';
}

위 로직을 실행하여 흐름을 따라가보면,

// 아래와 같이 주어졌을 때
a = "bBccC"
b = "BBC"

// dp[0]의 초기 값
// 첫 인덱스 만큼은 true로 설정한다.(시작 위치이기 때문)
[true, false, false, false]

// a[0] = 'b', dp[1]의 결과 값
[
  // b는 소문자이다.
  true,
  // b의 대문자는 (b[0]='B')와 같다.
  true, 
  // 이전 값이 false 이므로 패스
  false, 
  // 이전 값이 false 이므로 패스
  false
]

// a[1] = 'B', dp[2]의 결과 값
[
  // B(대문자)이므로 false
  false, 
  // B는 (b[0]='B') 와 같다.
  true, 
  // B는 (b[1]='B') 와 같다.
  true, 
  // 이전 값이 false 이므로 패스
  false
]

// a[2] = 'c', dp[3]의 결과 값
[
  // 이전 값이 false 이므로 패스
  false, 
  // c는 소문자이므로 true
  true, 
  // c는 소문자이므로 true
  true, 
  // 이전 값이 false 이므로 패스
  false
]

// a[3] = 'c', dp[4]의 결과 값
// a[2] 내용 반복
[false, true, true, false]

// a[4] = 'C', dp[5]의 결과 값
[
  // 이전 값이 false 이므로 패스
  false, 
  // C는 대문자 이므로
  false, 
  // C는 (b[1]='B')가 아니고, 대문자 이므로
  false, 
  // C는 (b[2]='C')와 같다.
  true
]

// 따라서 dp의 값은 아래와 같다.
dp[5][3] = true;

결론

솔직히 비슷한 문제를 다시 풀어보라고 해도 잘 해결할 자신이 없다. 이런 문제 유형을 자주 접하고 풀이 방법을 해석해 보면서 빨리 내 것으로 만들어야 겠다는 생각 뿐이다.