Array Manipulation

https://www.hackerrank.com/challenges/crush/problem?isFullScreen=true&h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays 

Array Manipulation | HackerRank

 

• 문제

  • 

    문제 1

     

  • 

    문제2

  • n 짜리 배열에 m 번의 쿼리를 동작시켜 가장 큰 값이 있는 원소를 반환한다.
  • 쿼리같은 경우 a , b , k 값으로 이루어져 있고 a ~ b까지 원소 값을 k 만큼 증가시킨다.

---

풀이

• 문제 자체는 굉장히 쉽지만 hard 난이도 문제인 이유가 있다( 역시 , 시간 초과.... 문제의 조건을 잘 살펴보자)

• 

  조건

   
• 쿼리가 최대 2*10^5이고 n의 개수가 최대 10^7이면 최악을 경우 10^7 * 2*10^5번의 값을 바꿔 주어야 한다.
  
  • 경우 1 : 전부 계산하여 문제를 풀려고 하면 쉽지만 역시나, m 값의 범위와 , n 값을 범위를 보면 시간 초과가 난다.

    • public static long arrayManipulation(int n, List<List<Integer>> queries) {
      	long[] arr = new long[n+1];
      	long max = 0;
          for(int i=0;i<queries.size();++i){
          	int a = queries.get(i).get(0);
              int b = queries.get(i).get(1);
              int k = queries.get(i).get(2);
              for(int j=a;j<=b;++j){ //이중 for문을 통한 반복을 하게 되면 시간초과
              	arr[j] += k;
                  max = Math.max(max,arr[j]);
              }
          }
          return max;
      }

  • 경우 2 :변경 되는 값의 시작위치랑 끝위치를 중점으로 생각한다( 다른 사람 코드를 참고 하였다)
    • 변경되는 값의 시작위치(a) 을 값을 k만큼 증가 시키고 변경이 종료된 위치 + 1 번째 위치 값을 -k 감소 시킨다.
    • 1 ~ n 까지 돌면서 변수 값에 변화된 값을 저장한뒤 가장 큰값일때를 반환한다. 

• public static long arrayManipulation(int n, List<List<Integer>> queries) {
  	long[] arr = new long[n+1];
  	long max = 0;
      long now = 0;
      for(int i=0;i<queries.size();++i){
      	int a = queries.get(i).get(0);
          int b = queries.get(i).get(1);
          int k = queries.get(i).get(2);
          arr[a] += k;
          if(b < n){// 마지막 까지 일 경우에는 감소 시킬 필요 없다
          	arr[b+1] -= k;
          }
      }
      for(int i=1;i<=n;++i){
      	now += arr[i];// 해당 index였을때의 값이다.
          max = Math.max(max,now);
      }
      return max;
  }