99클럽 코테 스터디 1일차 TIL + 오늘의 학습 키워드

오늘의 학습 키워드

• 메모리초과
• 2차원 배열 1차원 배열로 줄이기

공부한 내용

1. long과 integer를 구분하면서 구현해야 한다.

• 처음엔 left와 right이 long 변수인지 모르고 parseInt로 두었다가 에러를 확인하여 수정했었다.
• 배열의 index값으로는 반드시 integer 만 들어와야 하기 때문에 long간의 연산을 마친 후에는 (int) 를 앞에 붙여 정수화해준다.

2. 2차원을 1차원 배열로 바꾸면서 O(n^3) 의 복잡도를 지니지 않도록 주의한다.

오늘의 회고

문제설명

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

1. 첫번째 해결책

2차원 배열을 먼저 1행 1열부터 i행 i열까지 채워야 하는게 우선이라고 생각해서 총 3번의 반복문으로 original 이라는 2차원 배열을 채웠다. 그 이후 또다시 한 행별로 존재하는 배열들을 1차원으로 넣기위해 2번의 반복문으로 구성하였다. 예제로 주어진 테스트케이스에서는 성공했으나 나머지 테스트케이스에서는 메모리초과 에러가 발생했다.. ㅠㅠ

public class n2배열자르기 {
  public static int[] solution(int n, long left, long right) {
      int[] answer = new int[(int)(right-left+1)];
      int[][] original = new int[n][n]; //n행 n열

      for(int i=1; i<=n; i++){
          for(int j=0; j<=i-1; j++){
              for(int k=0; k<=i-1; k++){
                  if(original[j][k] == 0){
                      original[j][k]=i;
                  }
              }
          }
      }

      int[] arr = new int[n*n];
      for(int i=0; i<n; i++){
          for(int j=0; j<n; j++){
              int index = i*n+j;
              arr[index] = original[i][j];
          }
      }

      for(long i=left; i<=right; i++){
          answer[(int)(i-left)] = arr[(int)(i)];
      }

      return answer;
  }
  public static void main(String[] args) throws IOException{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(br.readLine());
      long left = Long.parseLong(br.readLine());
      long right = Long.parseLong(br.readLine());

      int[] ans = solution(N, left, right);
      for (int i : ans) {
          System.out.print(i + " ");
      }
  }
}

2. 수정한 이후

1번의 에러 후에 다시 생각한 방법은 어차피 원래 배열의 row행 col열 중 최댓값이 i와 동일하면 i를 넣게 되니까 앞선 3번의 반복문을 1번의 반복문으로 줄일 수 있었다.

이런식으로 구현한 두번째 수정된 코드는 다음과 같다.

public class n2배열자르기 {
  public static int[] solution(int n, long left, long right) {
      int[] answer = new int[(int)(right - left + 1)];

      for (long i = left; i <= right; i++) {
          int row = (int)(i / n);
          int col = (int)(i % n);
          answer[(int)(i - left)] = Math.max(row, col) + 1;
      }

      return answer;
  }
  public static void main(String[] args) throws IOException{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(br.readLine());
      long left = Long.parseLong(br.readLine());
      long right = Long.parseLong(br.readLine());

      int[] ans = solution(N, left, right);
      for (int i : ans) {
          System.out.print(i + " ");
      }
  }
}

• 무엇을 새롭게 알았는지

  문제에 주어진 조건들을 하나씩 모두 구현하는게 아니라 최대한 그 복잡도를 줄이는 방향으로 뭉쳐서 구현하는것도 필요하구나! 라는 것을 깨달았다.