TIL 2022-03-09-수

1. 오늘 학습한 내용

백준 구현/문자열 9093번, 정렬 2750번 문제

• 9093번
  문제
  내가 푼 코드

• 2750번
  문제
  내가 푼 코드

2. 알게 된 내용

9093번

알고 있던 개념들을 활용해서 풀긴 했지만 그래도 처음에 가물가물해하면서 고민을 좀 했어서 여기에 남기면서 다시 복습을 하고자 한다.

• 문자열.length() : 문자열의 길이를 구함
• 문자열.charAt(인덱스번호) : 문자열 안에서 인덱스번호에 해당하는 문자 하나를 빼옴

2750번

알고있는 정렬 방법을 구현해서 혼자 힘으로 풀고 싶었지만.. 처음에 연결리스트로 구현했는데 삽입하는 과정에서 내가 원하던 그림처럼 나오지 않아서 결국 다른 분의 글을 힌트 삼아서 배열로 구현해보았다.

• 선택정렬
  시간복잡도 : O(n2)

  int[] arr; // 이미 초기화 되어 있는 배열이라고 가정

  for(int i = 0; i < arr.length - 1; i++) {
      for(int j = i + 1; j < arr.length; j++) {

          if(arr[i] > arr[j]) {
              // 값 교환
              int temp = arr[j];
              arr[j] = arr[i];
              arr[i] = temp;
          }
      }
  }

코드 및 설명 출처 : [백준] 2750번 : 수 정렬하기 - JAVA [자바]

맨 앞의 요소보다 더 작은 요소가 나타나면, 둘의 값을 바꾸는 방법으로 진행할 수 있다.

나는 정석적인 선택정렬 방식대로 정렬된 요소를 제외한 나머지 요소들 중에 가장 작은 값을 선택해서 나머지 요소들 중 맨 앞으로 옮기는 방법으로 구현하려고 했는데, 이 분의 코드는 나머지 요소들 중 더 작은 값이 나오면 맨 앞과 교환하는 방식으로 계속 진행해나가는 것 같다. 구현 방식에서 약간 차이가 있지만 그래도 이 분의 힌트 코드를 참고해가면서 나는 정석적인 선택정렬 방법으로 한번 구현해보았다.

        int min;
        for (int i = 0; i < arr.length - 1; i++) {
            min = arr[i];
            int temp_idx = i;  // 가장 작은 값이 있었던 인덱스 번호
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j] < min) {
                    min = arr[j];
                    temp_idx = j;
                }
            }
            int temp = arr[i];
            arr[i] = min;
            arr[temp_idx] = temp;

        }

선택 정렬 외에도 여러 방법이 있다고 한다.

• Arrays.sort() 메소드를 이용하는 방법

  • 자체 정렬 알고리즘을 구현 할 필요 없이 sort() 안에 배열만 넣어주면 자동으로 해당 배열이 정렬되어 나온다.
  • 시간 복잡도 : 평균 O(nlogn)

• 카운팅 정렬

  • 값을 비교하면서 정렬하는 것이 아니라 각 입력받은 값을 index 으로 하여 해당 값의 출현 빈도수를 체크하고, 출력하는 방법을 사용
  • 시간 복잡도 : O(n)
  • 자바 [JAVA] - 카운팅 정렬 (Counting Sort / 계수 정렬)
    • 간략 요약 (자세한 내용은 꼭 위의 글 참고할 것! 설명 잘 나와있음)
      카운팅 정렬 : 데이터의 값이 몇 번 나왔는지를 세어서 새로운 배열을 만들고, 그 몇번 나왔는지를 누적합으로 변환시켜서 그 값을 이용해 정렬하는 방식이다

• 열거체 (알고리즘 책에서 문제 풀다가 나온 내용)
  조금 난감하고 머리가 안 돌아가서 고민하다가 해설 코드랑 다른 분의 코드를 조금 참고했는데, 해설 코드에서는 enum 열거체를 사용한 것을 보고.. enum을 어떻게 썼는지 간단히 리뷰하겠다.

• 열거체 선언

  ```java
  enum Season { //class 외부에서 선언
      봄, 여름, 가을, 겨울
  }
  ```

  선언은 이런 식으로 무슨 종류들이 있는지를 나열하면 된다.
  - 열거체 사용 방법 (더 참고하기)

3. 느낀 점

• 9093번
  처음에는 문제를 접하자마자 '이걸 내가 어떻게 풀지'라고 생각하면서 고민을 많이 했었는데 내 힘으로도 쉽게 풀 수 있는 문제였다! 너무 쫄지 말고 내가 아는 개념들을 잘 활용해보려고 노력해보자!

• 2750번
  처음에는 쉬워보였는데.. 막상 해결하려고 보니까 조금 난감해서 결국 다른 분의 설명을 조금 참고하면서 해결했다. 그리고 카운팅 정렬을 잊고 살고 있었는데 다시 복습을 하게 되었다. 참고한 글을 쓰신 분께서 카운팅 정렬을 잘 알고 있으라고 써주셔서, 다시 꼼꼼히 읽어봤다. 다음에 써먹을 수 있으면 좋겠다! (아직 자신은 없지만... 그래도 원리 참고하면서라도 시도해보자!)