[Leetcode] 1625. Lexicographically Smallest String After Applying Operations

BFS 를 해보려고 찾다가 발견해서 풀어본 문제. 정수로 이루어진 문자열 s 에 대해 회전 또는 더하기 두 개의 연산이 가능하다. 연산의 횟수 또는 순서는 정해져있지 않으며, 가장 작은 값을 찾아내면 되는 문제.

어떤 연산을 몇 번 쓸지 정해져있지 않다는 점에서 greedy 로 볼 수 있지만 문자열의 길이가 달라지지 않고 연산으로 바뀔 수 있는 값이 한정적이기 때문에 방문 체크를 해가면서 BFS 를 돌리면 된다. 연산의 종류도 크지 않아 큐를 따로 만들지 않고 그냥 .shift() 연산을 때렸다.

function findLexSmallestString(s: string, a: number, b: number): string {
    const q = [s]
    const visited = new Set(q)

    let minS = s;

    while(q.length > 0) {
        const currentS = q.shift();

        if (currentS < minS) {
            minS = currentS
        }

        const sArr = currentS.split('');

        for (let i = 1; i < sArr.length; i += 2) {
            sArr[i] = String((Number(sArr[i]) + a) % 10);
        }

        const sString = sArr.join('')

        if (!visited.has(sString)) {
            visited.add(sString);
            q.push(sString)
        }

        const k = b % s.length;

        const sRotate = currentS.slice(s.length - k) + currentS.slice(0, s.length - k);

        if (!visited.has(sRotate)) {
            visited.add(sRotate);
            q.push(sRotate);
        }
    }

    return minS;
};

BFS로 어렵지 않게 문제를 풀었다. 그런데 실행시간이 3ms 인 사람들이 10% 정도 있다. 이 사람들은 어떻게 해결을 한 걸까...?

혹시 큐를 진짜로 Queue 로 만들면 시간초가 줄어드나 싶어서 클래스를 직접 짰다.

class Node {
    value = '';
    next: Node | null = null;

    constructor(value: string) {
        this.value = value;
    }
}

class MyQueue {
    size = 0;
    head: Node | null = null;
    tail: Node | null = null;

    put(value: string) {
        const node = new Node(value);

        if (this.head == null) {
            this.head = node;
        }

        if (this.tail == null) {
            this.tail = node;
        } else {
            const prevNode = this.tail;
            prevNode.next = node;
            this.tail = node;
        }

        this.size += 1
    }

    get() {
        if (this.head != null) {
            const nextHead = this.head.next;
            const value = this.head.value;
            this.head = nextHead;

            this.size -= 1

            return value;
        }
    }

    length() {
        return this.size;
    }
}

function findLexSmallestString(s: string, a: number, b: number): string {
    const q = new MyQueue()
    const visited = new Set([s])

    q.put(s);

    let minS = s;

    while(q.length() > 0) {
        const currentS = q.get();

        if (currentS < minS) {
            minS = currentS
        }

        const sArr = currentS.split('');

        for (let i = 1; i < sArr.length; i += 2) {
            sArr[i] = String((Number(sArr[i]) + a) % 10);
        }

        const sString = sArr.join('')

        if (!visited.has(sString)) {
            visited.add(sString);
            q.put(sString)
        }

        const k = b % s.length;

        const sRotate = currentS.slice(s.length - k) + currentS.slice(0, s.length - k);

        if (!visited.has(sRotate)) {
            visited.add(sRotate);
            q.put(sRotate);
        }
    }

    return minS;
};

전혀 차이가 없다...?!