[JAVA] 알고리즘 문제풀이 입문 6-3번(삽입정렬)

강의: https://inf.run/w779

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의

 

 

6-3번

import java.util.Scanner;

public class Main {
  public int[] solution(int n, int[] arr){
    for(int i = 1; i < n; i++){
      int tmp = arr[i];               // 삽입정렬 key값
      for(int j = i-1; j >= 0; j--){
        if(tmp < arr[j]){            //key 값보다 작으면
          arr[j+1] = arr[j];         //뒤로 한 칸 이동
        }else{                       //key값보다 크면
          arr[j+1] = tmp;            //빈 인덱스에 key값 삽입
          break;                     //탈출
        } 
      }
    }
    return arr;
  }

  public static void main(String[] args){
    Main t = new Main();
    Scanner in = new Scanner(System.in);

    int n = in.nextInt();
    int[] arr = new int[n];
    for(int i = 0; i < n; i++){
      arr[i] = in.nextInt();
    }
    in.close();

    for(int x : t.solution(n, arr))
      System.out.print(x+" ");
  }
}

 

삽입 정렬 코드를 이렇게 짜 봤는데 결과 배열에 첫 번째 인덱스 값만 저장되어 나옴.(ex 11 11 11 11 11)

강사님은 arr[j]값이 key 값보다 크면 일단 for문을 break 하고 j for문을 탈출한 뒤 키 값을 삽입해 주었다.

 

 

>>>>

import java.util.Scanner;

public class Main {
  public int[] solution(int n, int[] arr){
    for(int i = 1; i < n; i++){
      int tmp = arr[i];
      int j;
      for(j = i-1; j >= 0; j--){
        if(tmp < arr[j]){       //키 값이 더 작으면
          arr[j+1] = arr[j];    //뒤로 한 칸 이동
        }else{                  //키 값이 더 크면
          break;                //멈추고
        } 
      }                         //for문 탈출 후
      arr[j+1] = tmp;           //빈 인덱스에 key값 삽입
    }
    return arr;
  }

  public static void main(String[] args){
    Main t = new Main();
    Scanner in = new Scanner(System.in);

    int n = in.nextInt();
    int[] arr = new int[n];
    for(int i = 0; i < n; i++){
      arr[i] = in.nextInt();
    }
    in.close();

    for(int x : t.solution(n, arr))
      System.out.print(x+" ");
  }
}

 

처음에는 두 방법에 차이가 없다고 생각했지만 모든 경우에 if문/else문만 거칠 경우를 고려하지 않았다는 것을 깨달았다.

첫 인덱스 값이 두 번째 인덱스 값보다 크다면 첫 반복에서 첫 인덱스를 뒤로 밀어준 후 for 문이 끝나버리므로 key값을 빈 자리에 넣어주지 못하게 된다.

깨닫기까지 시간이 조금 걸렸고, 이 차이를 간과하고 코드를 짠 게 너무 창피하지만 

앞으로 똑같은 실수를 저지르지 말자는 의미에서 정리해봤다..