LeetCode Weekly Contest 239

A. Minimum Distance to the Target Element

nums[i]==target이면서 abs(i-start)의 값이 최소인 값을 리턴하는 문제이다. 그대로 구현해주면 된다.

class Solution {
public:
  int getMinDistance(vector<int>& nums, int target, int start) {
    int ret=1e9;
    for(int i=0;i<nums.size();i++) {
      if(nums[i]==target && abs(i-start)<ret) ret=abs(i-start);
    }
    return ret;
  }
};

---

B. Splitting a String Into Descending Consecutive Values

주어진 s의 길이가 1 ≤ s ≤ 20이므로 완전탐색하여 조건을 만족하는지 확인할 수 있다.

그러나 길이가 20인 문자열에서 중간을 잘랐을 때 long long 범위를 넘어서면 안되므로 처음 dfs를 돌리기 전에 prefix가 0인 것들을 제외한 나머지 길이가 long long 범위를 넘어서는지 확인했다.

dfs함수의 경우 두 문자열을 인자로 받게 하여 현재 문자열인 cur를 잘랐을 때 이전 문자열 prev와 1의 차이가 나는지 확인하면서 재귀호출을 하도록 작성했다.

class Solution {
public:
  bool dfs(string prev, string cur) {
    if(cur.size()==0) {
      return true;
    }
    bool ok=false;
    for(int i=1;i<=cur.size();i++) {
      string tmp=cur.substr(0,i);
      long long a=stoll(prev), b=stoll(tmp);
      if(a-b==1) {
        if(dfs(tmp,cur.substr(i))) {
          ok=true;
        }
      }
    }
    return ok;
  }
    
  bool splitString(string s) {
    for(int i=1;i<s.size();i++) {
      string a=s.substr(0,i), b=s.substr(i);
      // stoll의 out of range를 막기위해 prefix가 0인 것들을 제외한 나머지 길이가 long long 범위를 넘지 못하게 제한
      int zero_a=0, zero_b=0;
      for(int j=0;j<a.size();j++) {
        if(a[j]=='0') zero_a++;
        else break;
      }
      for(int j=0;j<b.size();j++) {
        if(b[j]=='0') zero_b++;
        else break;
      }
      if(a.size()-zero_a>18 || b.size()-zero_b>18) continue;
      if(dfs(a,b)) return true;
    }
    return false;
  }
};

---

C. Minimum Adjacent Swaps to Reach the Kth Smallest Number

class Solution {
public:
  int getMinSwaps(string num, int k) {
  string num2=num;
  // kth premutation
  while(k--) {
    next_permutation(num2.begin(),num2.end());
  }
  // counting swap
  int i=0, j=0; // 
  int answer=0;
  while(i<num.size()) {
    j=i;
    while(num[j]!=num2[i]) j++;
    while(i<j) {
      swap(num[j],num[j-1]); // adjcent swap
      j--;
      answer++;
    }
    // cout<<num<<endl;
    i++;
  }
  return answer;
  }
};

---

D. Minimum Interval to Include Each Query