Baekjoon 2505 두 번 뒤집기

더 깔끔한 노션을 원한다면

Baekjoon 2505 두 번 뒤집기

문제

2505번: 두 번 뒤집기

면접에서 두 번 뒤집기에 대한 로직을 물어봐서 풀어보았다.

처음 생각 - 생각도 못함

그냥 문제 보고 멍했다!😂

문제 포인트들을 천천히 살펴보았다.

1. 꼭 두 번 뒤집어야 한다.
2. 구간[i,i]를 뒤집으면 아무런 변화가 없는데 이러한 것도 허용이 된다.
3. 입력에 대한 답은 항상 존재한다.

정리해보면 두 번 안에는 무조건 초기 상태로 돌아올 수 있다는 것이다.

1. 앞에서 ❗

1부터 N까지 자리를 찾아서 뒤집어준다.

private static boolean front(int[] origin) {
  int[] array = origin.clone();
  int cnt = 0;
  int target = 1;
  while (target != N && cnt < 3) {
    for (int i = target; i <= N; i++) {
      if (target == array[target]) {
        break;
      }
      if (array[i] == target) {
        cnt++;
        reverse(array, target, i);
        sb1.append(target + " " + i + "\n");
      }
    }
    target++;
  }
  if (cnt == 1) {
    System.out.println("1 1");
    System.out.println(sb1.toString());
    return true;
  } else if (cnt == 2) {
    System.out.println(sb1.toString());
    return true;
  } else {
    System.out.println("1 1");
    System.out.println("1 1");
    return false;
  }
}

target이 N이 될 때까지 뒤집어준다.

cnt이 3 이상이면 while을 끝내는 이유

뒤집기가 두 번 넘게 진행돼야 되는 상황이면 다른 방법으로 뒤집어야 한다.

2. 뒤에서 ❗

front 함수가 false를 return한다면 N부터 1까지 자리를 찾아서 뒤집어줘야한다.

private static void back(int[] origin) {
  int[] array = origin.clone();
  int cnt = 0;
  int target = N;
  while (target != 1) {
    for (int i = target; i >= 1; i--) {
      if (target == array[target]) {
        break;
      }
      if (array[i] == target) {
        cnt++;
        reverse(array, target, i);
        sb2.append(target + " " + i + "\n");
      }
    }
    target++;
  }
  if (cnt == 1) {
    System.out.println("1 1");
    System.out.println(sb2.toString());
  } else if (cnt == 2) {
    System.out.println(sb2.toString());
  } else {
    System.out.println("1 1");
    System.out.println("1 1");
  }
}

전체 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
  public static void main(String[] args) throws java.lang.Exception {
    P2505();
  }

  static StringBuilder sb1 = new StringBuilder();
  static StringBuilder sb2 = new StringBuilder();
  static int N;

  private static void P2505() throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());
    int[] array = new int[N + 1];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 1; i <= N; i++) {
      array[i] = Integer.parseInt(st.nextToken());
    }
    if (!front(array)) {
      back(array);
    }
  }

  private static boolean front(int[] origin) {
    int[] array = origin.clone();
    int cnt = 0;
    int target = 1;
    while (target != N) {
      for (int i = target; i <= N; i++) {
        if (target == array[target]) {
          break;
        }
        if (array[i] == target) {
          cnt++;
          reverse(array, target, i);
          sb1.append(target + " " + i + "\n");
        }
      }
      target++;
    }

    if (cnt == 1) {
      System.out.println("1 1");
      System.out.println(sb1.toString());
      return true;
    } else if (cnt == 2) {
      System.out.println(sb1.toString());
      return true;
    } else {
      return false;
    }
  }

  private static void back(int[] origin) {
    int[] array = origin.clone();
    int cnt = 0;
    int target = N;
    while (target != 1) {
      for (int i = target; i >= 1; i--) {
        if (target == array[target]) {
          break;
        }
        if (array[i] == target) {
          cnt++;
          reverse(array, i, target);
          sb2.append(i + " " + target + "\n");
        }
      }
      target--;
    }

    if (cnt == 1) {
      System.out.println("1 1");
      System.out.println(sb2.toString());
    } else if (cnt == 2) {
      System.out.println(sb2.toString());
    } else {
      System.out.println("1 1");
      System.out.println("1 1");
    }
  }

  public static void reverse(int[] array, int s, int e) {
    int n = (int) Math.ceil((e - s) / 2.0);
    for (int i = 0; i < n; i++) {
      int temp = array[s + i];
      array[s + i] = array[e - i];
      array[e - i] = temp;
    }
  }
}