[LeetCode] 2375. Construct Smallest Number From DI String

https://leetcode.com/problems/construct-smallest-number-from-di-string/description/

leetcode - Construct Smallest Number From DI String

문제 유형: 백트래킹, 비트마스킹, 문자열 처리, 그리디

문제 난이도: Medium

 

문제

You are given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing.

A 0-indexed string num of length n + 1 is created using the following conditions:

• num consists of the digits '1' to '9', where each digit is used at most once.
• If pattern[i] == 'I', then num[i] < num[i + 1].
• If pattern[i] == 'D', then num[i] > num[i + 1].

Return the lexicographically smallest possible string num that meets the conditions.

 

0-indexed 문자열 pattern이 주어집니다.

길이는 n이고, 'I'는 증가, 'D'는 감소를 의미합니다.

 

문자열 num은 n+1길이의 다음 조건을 만족하는 문자열입니다:

• num은 '1'에서 '9'까지만을 가지고, 각 수들은 최대 한 번씩만 사용가능합니다.
• pattern[i]가 'I'면, num[i] < num[i+1]여야 합니다.
• pattern[i]가 'D'면, num[i] > num[i+1]여야 합니다.

 

가능한 사전순으로 작은 num을 만들어서 반환하시오.

 

풀이

base string으로 "1" ~ "9"까지 다음의 dfs를 시도해보면 된다:

만약 이번 idx가 pattern의 길이까지 왔다면 생성에 성공했다는 뜻으로, 전역변수 ans에 따로 현재까지의 진행인 s를 저장하고 true를 리턴한다.

 

현재 숫자는 s[idx] - '0'이다.

만약 pattern[idx]가 'I'라면, 현재 숫자 ~ 9중에서 state에 비트로 저장되어있지 않고 유효한 숫자라면 추가하고 재귀를 시도한다.

만약 pattern[idx]가 'D'라면, 1 ~ 현재 숫자-1중에서 state에 비트로 저장되어있지 않고 유효한 숫자라면 추가하고 재귀를 시도한다.

 

작은 숫자들을 우선으로 시도해서 최초 성공시 리턴하므로, 반드시 사전순으로 작은 num을 만들도록 보장한다.

 

코드

C++

class Solution {
private:
    string ans;
    bool dfs(int state, int idx, string s, const string& pattern) {
        if(idx == pattern.size()) {
            ans = s;
            return true;
        }
        int curr_num = s[idx] - '0';
        if(pattern[idx] == 'I') {
            for(int next = curr_num+1; next <= 9; ++next) {
                if(next >= 1 && next <= 9 && ((state & (1 << next)) == 0)) {
                    char digit = '0' + next;
                    if(dfs(state | (1 << next), idx+1, s + digit, pattern)) return true;
                }
            }
        } else {
            for(int next = 1; next < curr_num; ++next) {
                if(next >= 1 && next <= 9 && ((state & (1 << next)) == 0)) {
                    char digit = '0' + next;
                    if(dfs(state | (1 << next), idx+1, s + digit, pattern)) return true;
                }
            }
        }
        return false;
    }
public:
    string smallestNumber(string pattern) {
        int n = pattern.size();
        int state = 0;
        for(int i = 1; i <= 9; ++i) {
            string s(1, '0'+i);
            if(dfs(state | (1 << i), 0, s, pattern)) break;
        }
        return ans;
    }
};

 

Go

var (
    ans string
)

func dfs(state, idx int, s, pattern string) bool {
    if idx == len(pattern) {
        ans = s
        return true
    }

    curr := int(s[idx] - '0')
    if pattern[idx] == 'I' {
        for next := curr+1; next <= 9; next++ {
            if (state & (1 << next)) == 0 {
                newCh := '0' + next
                if dfs(state | (1 << next), idx+1, s + string(newCh), pattern) {
                    return true
                }
            }
        }
    } else {
        for next := 1; next < curr; next++ {
            if (state & (1 << next)) == 0 {
                newCh := '0' + next
                if dfs(state | (1 << next), idx+1, s + string(newCh), pattern) {
                    return true
                }
            }
        }
    }
    return false
}

func smallestNumber(pattern string) string {
    state := 0
    for i := 1; i <= 9; i++ {
        if dfs(state | (1 << i), 0, strconv.Itoa(i), pattern) {
            break
        }
    }
    return ans
}