LeetCode Weekly Contest 246

A. Largest Odd Number in String

주어진 숫자 문자열에서 연속된 부분문자열(substring)에서 가장 큰 홀수를 찾는 문제이다.

단순하게 num이 홀수인지 확인한 후 뒤에서부터 잘라가면서 홀수인지 판단하여 홀수일 때 리턴하면 된다.

class Solution {
public:
  string largestOddNumber(string num) {
    if((num.back()-'0')%2!=0) return num;
    for(int i=num.size()-1;i>=0;i--) {
      if((num.back()-'0')%2==0) num.pop_back();
      else break;
    }
    return num;
  }
};

---

B. The Number of Full Rounds You Have Played

시작 시간과 끝나는 시간 사이에 15분 경기를 얼마나 할 수 있는지 계산하는 문제이다.

15분 경기는 반드시 00분, 15분, 30분, 45분에 시작하고 끝나야 하는 것을 주의하고 끝나는 시간이 다음날까지 가능하기 때문에 startTime이 finishTime보다 크다면 finishTime에 24시간을 더한 후 계산한다.

시간을 분으로 바꾸면 $(24\times60\times2)+1$분으로 나타낼 수 있고 분이 15로 나누어 떨어지는 곳부터 15분동안 경기가 가능한지 체크하면 된다.

class Solution {
public:
  int numberOfRounds(string startTime, string finishTime) {
    int start=stoi(startTime.substr(0,2))*60+stoi(startTime.substr(3,2));
    int finish=stoi(finishTime.substr(0,2))*60+stoi(finishTime.substr(3,2));
    if(start>finish) finish+=24*60;
    vector<int> times(24*60*2+1);
    for(int i=start;i<=finish;i++) times[i]=1;
    int ans=0;
    for(int i=0;i<=finish;i++) {
      if(i%15==0 && times[i]) {
        bool able=1;
        for(int j=i;j<=i+15;j++) {
          if(!times[j]) {
            able=0;
            break;
          }
        }
        if(able) ans++;
      }
    }
    return ans;
  }
};

---

C. Count Sub Islands

grid2의 island가 grid1에 완전히 속하는지 확인하는 문제이다.

먼저, grid1과 grid2의 섬들이 겹치는 부분을 grid3로 체크했다.

다음, grid2를 BFS로 탐색하면서 해당 섬이 grid3와 겹치는지 확인하면 된다. 만약, 두 섬이 겹친다면 grid2의 섬이 grid1의 섬에 완전히 속한다고 볼 수 있다.

class Solution {
public:
  int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
    int row=grid1.size(), col=grid1[0].size();
    int dx[4]={1,0,-1,0};
    int dy[4]={0,1,0,-1};
    // make grid3
    vector<vector<int>> grid3(row,vector<int>(col));
    for(int i=0;i<row;i++) {
      for(int j=0;j<col;j++) grid3[i][j]=grid1[i][j]&grid2[i][j]; // AND
    }
    int ans=0;
    // subIsland?
    vector<vector<int>> visit(row,vector<int>(col));
    for(int i=0;i<row;i++) {
      for(int j=0;j<col;j++) {
        if(!visit[i][j] && grid2[i][j]) {
          visit[i][j]=1;
          queue<pair<int,int>> q;
          q.push({i,j});
          bool able=1;
          while(!q.empty()) { // bfs
            int x=q.front().first, y=q.front().second;
            q.pop();
            if(grid3[x][y]!=grid2[x][y]) {
              able=0;
            }
            for(int k=0;k<4;k++) {
              int nx=x+dx[k], ny=y+dy[k];
              if(nx>=0 && nx<row && ny>=0 && ny<col) {
                if(grid2[nx][ny] && !visit[nx][ny]) {
                  visit[nx][ny]=1;
                  q.push({nx,ny});
                }
              }
            }
          }
          if(able) ans++;
        }
      }
    }
    return ans;
  }
};

---

D. Minimum Absolute Difference Queries

먼저, 문제가 어려워서 링크를 보고 참고했습니다.

쿼리로 주어지는 두 인덱스 사이의 원소 두 개의 차이의 최솟값을 구하는 문제이다. 부분 집합의 모든 원소가 같은 경우 -1을 리턴하고 다른 경우 최솟값은 0이 될 수 없다.

참고한 글에서는 각 원소들의 인덱스를 따로 저장하여 쿼리의 두 인덱스 중 하나라도 포함한다면 현재 값과 이전 값의 차이를 계산하여 최솟값을 찾는 방법을 사용한다.

예를들어, 예제 테스트케이스인 4 5 2 2 7 10이 들어왔고 쿼리 $(0,2)$가 들어왔다고 가정하자.

index배열은 다음과 같이 저장되어 있을 것이다.

• index[2] = {2, 3}
• index[4] = {0}
• index[5] = {1}

for문을 통해 2 -> 4 -> 5 순으로 탐색을 진행한다.

low는 lower_bound, high는 upper_bound를 통해 인덱스를 구하게 되는데 low와 high이 같은 경우는, 범위안에 해당 원소가 들어있지 않다는 의미를 가진다.

i=2일 때, low=0, high=1이므로 low와 high이 다르다. 즉, 2가 쿼리 범위안에 들어있음을 나타낸다. 범위안에 있는 값은 prev에 저장해준다.

i=4일 때, low=0, high=1이므로 low와 high이 다르다. 즉, 4가 범위안에 있으므로 d=4-2=2가 저장된다. 현재까지 최소 거리는 2이다.

i=5일 때, low=0, high=1이므로 low와 high이 다르다. 즉, 5가 범위안에 있으므로 d=5-4=1이 저장된다. 현재까지 최소 거리가 1이므로 반복문을 종료한다.

class Solution {
public:
  vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
    vector<int> index[101];
    int i=0;
    for(auto x : nums) index[x].push_back(i++);
    vector<int> ans(queries.size());
    int j=0; // ans index
    for(vector<int> q : queries) {
      int l=q[0], r=q[1];
      int prev=-1;
      int d=INT_MAX;
      for(int i=1;i<=100;i++) {
        int low=lower_bound(index[i].begin(),index[i].end(),l)-index[i].begin();
        int high=upper_bound(index[i].begin(),index[i].end(),r)-index[i].begin();
        if(low>=high) continue;
        if(prev!=-1) {
          d=min(i-prev,d);
        }
        if(d==1) break; // 차이가 1보다 작은 값은 없기 때문에 break
        prev=i; // 범위안에 있는 원소를 저장
      }
      ans[j++]=d==INT_MAX ? -1 : d;
    }
    return ans;
  }
};