[JAVA] 알고리즘 문제풀이 입문 5-8, 6-1번

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

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

 

5-8번

import java.util.LinkedList;

import java.util.Queue;

import java.util.Scanner;

class Person{

  int id;

  int pri;

  public Person(int id, int pri){

    this.id = id;

    this.pri = pri;

  }

}

public class Main {

  public int solution(int n, int m, int[] arr){

    Queue<Person> que = new LinkedList<>();

    int answer = 1;

    for(int i = 0; i < n; i++){

      que.add(new Person(i, arr[i]));

    }

    while(!que.isEmpty()){

      Person p = que.poll();

      for(Person x : que){

        if(x.pri > p.pri){

          que.offer(p);

          p = null;

          break;

        }

      }

      if(p != null){

        if(p.id == m) return answer;

        else answer++;

      }

    }

    return answer;

  }

  public static void main(String[] args){

    Main t = new Main();

    Scanner in = new Scanner(System.in);

    int n = in.nextInt();

    int m = in.nextInt();

    int[] arr = new int[n];

    for(int i = 0; i < n; i++){

      arr[i] = in.nextInt();

    }

    in.close();

      System.out.print(t.solution(n, m, arr));

  }

}

 

 

 

6-1번

import java.util.Scanner;

public class Main {
  public int[] solution(int n, int[] arr){
    int p = 0;

    while(p < n){
      int min = arr[p];
      int m = p;
      for(int i = p+1; i < n; i++){
        if(arr[i] < min){
          min = arr[i];
          m = i;
        }
      }
      if(m!=p){
        int tmp = arr[p];
        arr[p] = min;
        arr[m] = tmp;
      }
      p++;


    }
    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+" ");
  }
}

 

선택정렬

1. 주어진 배열 중 최솟값을 찾아 맨 앞 인덱스의 값과 교체

2. 정렬된 인덱스를 제외한 나머지 인덱스로 동일하게 반복

 

 

 

 

나는 while문 안에 for문을 집어넣었는데 강사님은 이중 for문 사용하심.

while문을 쓴 특별한 이유는 없었고 확실히 이 코드에서는

바깥쪽 반복문이 기준이 되어 안쪽 반복문과 값을 비교하기 때문에

이중 for문을 사용하는게 더 간결하고 보기 좋을 것 같음.

 

 

>>

 

import java.util.Scanner;

public class Main {
  public int[] solution(int n, int[] arr){
    for(int i = 0; i < n; i++){
    int idx = i;
      for(int j = i+1; j < n; j++){
        if(arr[j] < arr[idx])  idx = j;
      }
      int tmp = arr[i];
      arr[i] = arr[j];
      arr[j] = tmp;
    }
    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+" ");
  }
}

바꾼 코드.

확실히 p, m등의 변수도 필요 없어지고

값 교체가 되지 않는 경우 값이 중복 저장되는 경우를 대비해 넣은 if 문도 사라져 간결한 코드가 되었음.

코딩을 배우고 난 뒤로 수도 없이 사용해 온 반복문인데도 아직 제대로 쓸 줄 모르는구나 싶어서 슬프지만..

 

- 인덱스가 필요한 경우에는 for문을 사용하는 것이 더욱 효율적이다.

- 더 세부적인 부분을 신경써서 코드 짜자