99클럽 코테 스터디 20일차 TIL (챌린저): [백준][Java] 1083 소트 - 골드4

 

문제 보기

https://www.acmicpc.net/problem/1083

 

 

풀이

로직은 쉬운데 놓치기 쉬운 부분이 많아서 힘들었다.

 

내가 생각한 방법은 이렇다.

첫 start는 0으로 둔다.

start부터 start+S까지 값을 검사한다. (물론 start+S가 N을 넘어가지 않아야 함.)

그중 max 값을 뽑는다.

 

위와 같은 상황이라면 5이다.

그럼 이 max의 인덱스부터 start까지 양 옆의 숫자들을 교환한다.

여기서는 3과 5만 교환하면 끝이다.

 

 

한 번 옮겼기 때문에 남은 s의 값은 2이다.

이 값은 max의 index - start로 정한다.

이 로직대로라면 맨 앞에 올 수 있는 최고로 큰 수가 왔다는 뜻이니

start를 ++ 해준다.

다음으로 넘어가자.

이번엔 start와 max의 index가 같다.

그렇다면 로직을 수행하지 않고 바로 start를 ++ 해서 다음으로 넘어간다.

int start = 0;
while(S > 0 && start < N) {
  int index = start;
  for(int j = start + 1; j < N && j <= start + S; j++) {
    if(arr[j] > arr[index]) {
      index = j;
    }
  }
  for(int j = index; j > start; j--) {
    int temp = arr[j];
    arr[j] = arr[j - 1];
    arr[j - 1] = temp;
  }

  S -= (index - start);
  start++;
}

이 문제의 핵심 코드이다.

제일 밖의 while문은 이동력인 S를 다 소모하거나 start가 N에 다다랐을 경우 빠져나오게 된다.

첫 번째 for문에서는 start 다음부터 start+S까지 중에서 max 값을 탐색하는데 이 max index의 기본값은 start 값이다.

두 번째 for문에서는 max에서 start까지 양 옆 수를 교환하는 작업을 수행한다.

마지막으로 index-start의 값 만큼 S를 빼주는데, start 값이 max 값일 경우 0이 되기 때문에 S는 줄어들지 않는다.

start는 무조건 다음으로 이동하게 된다.

 

마지막 단계까지 확인하자.

최종적으로 5 3 4 1 2가 답이 될 것이다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    int[] arr = new int[N];
    for(int i = 0; i < N; i++) {
      arr[i] = Integer.parseInt(st.nextToken());
    }
    int S = Integer.parseInt(br.readLine());

    int start = 0;
    while(S > 0 && start < N) {
      int index = start;
      for(int j = start + 1; j < N && j <= start + S; j++) {
        if(arr[j] > arr[index]) {
          index = j;
        }
      }
      for(int j = index; j > start; j--) {
        int temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
      }

      S -= (index - start);
      start++;
    }

    for(int i = 0; i < N; i++) {
      bw.write(arr[i] + " ");
    }

    bw.flush();
    bw.close();
  }

}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/1083.%E2%80%85%EC%86%8C%ED%8A%B8

CodingTest_AutoSave/백준/Gold/1083. 소트 at main · MetroDefro/CodingTest_AutoSave