목표
전에 풀어본 문제를 다시 풀어봐서 한가지 정답만 있는게 아니라 여러 가지의 방법으로도 문제를 풀 수 있도록 공부하는게 내 목표이다.
문제
내가 생각했을때 문제에서 원하는부분
첫째 줄에 N (1 ≤ N ≤ 100)과 M (1 ≤ M ≤ 100)이 주어진다.
둘째 줄부터 M개의 줄에는 바구니의 순서를 역순으로 만드는 방법이 주어진다. 방법은 i j로 나타내고, 왼쪽으로부터 i번째 바구니부터 j번째 바구니의 순서를 역순으로 만든다는 뜻이다. (1 ≤ i ≤ j ≤ N)
도현이는 입력으로 주어진 순서대로 바구니의 순서를 바꾼다.
모든 순서를 바꾼 다음에, 가장 왼쪽에 있는 바구니부터 바구니에 적혀있는 순서를 공백으로 구분해 출력한다.내가 이 문제를 보고 생각해본 부분
바구니 개수와 뒤집을 횟수를 입력받고
바구니 배열을 생성해서 담아주고 반복을 통해서 바구니 배열의 인덱스를 해당하는 위치에 넣어준다.
M번을 뒤집기를해준다. 그리고 바구니 순서 뒤집기 메소드를 만들어준다.전에 11달전에 Scanner 클래스를 사용해줘서 코드를 구현해서 통과한게 있었다. 이번에는 BufferedReader를 이용해서 코드를 구현해보고싶었다.
코드로 구현
package baekjoon.baekjoon_0;
import java.util.Scanner;
// 백준 10811번 문제
public class Main57 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 바구니 개수(N)와 뒤집을 획수(M) 입력 받기
int N = sc.nextInt();
int M = sc.nextInt();
// 바구니 배열 생성 및 초기화
int[] baskets = new int[N];
for(int i = 0; i < N; i++) { // 바구니에 1부터 N까지의 번호 할당
baskets[i] = i + 1; // 반복문을 통해 바구니 배열의 인덱스 i에 해당하는 위치에 i + 1 값을 할당
}
// M번의 뒤집기 연산 수행
for(int i = 0; i < M; i++) {
int start = sc.nextInt();
int end = sc.nextInt();
reverseBaskets(baskets, start - 1, end - 1); // 바구니 순서 뒤집기, 배열때문
}
// 결과 출력
for(int basket : baskets) {
System.out.print(basket + " ");
}
sc.close();
}
// 바구니 순서 뒤집기 메소드
// reverseBaskets 메소드는 주어진 바구니 배열의 일부를 뒤집는 역할을 수행하는 메소드
// baskets는 바구니 배열을 의미 , start와 end는 뒤집을 바구니의 범위
// 반복문 안에서는 temp라는 임시 변수를 사용하여 baskets[start]의 값을 저장
// 이렇게 함으로써 해당 위치의 값이 덮어씌워지지 않고 보존
public static void reverseBaskets(int[] baskets, int start, int end) {
while(start < end) {
int temp = baskets[start];
baskets[start] = baskets[end];
baskets[end] = temp;
start++;
end--;
}
}
}
코드로 구현
package baekjoon.baekjoon_0;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// 백준 10811번 문제
public class Main57_1 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int N = Integer.parseInt(input[0]);
int M = Integer.parseInt(input[1]);
int[] baskets = new int[N];
for(int i = 0; i < N; i++) {
baskets[i] = i + 1;
}
for(int i = 0; i < M; i++) {
String[] startEnd = br.readLine().split(" ");
int start = Integer.parseInt(startEnd[0]);
int end = Integer.parseInt(startEnd[1]);
reverseBaskets(baskets, start - 1, end - 1);
}
for(int basket : baskets) {
System.out.print(basket + " ");
}
br.close();
}
public static void reverseBaskets(int[] baskets, int start, int end) {
while(start < end) {
int temp = baskets[start];
baskets[start] = baskets[end];
baskets[end] = temp;
start++;
end--;
}
}
}시간복잡도 O(N + M * k + N)
1.baskets 배열 초기화: O(N)
배열의 크기가 N이기 때문에 전체 순회하는 반복문의 복잡도는 O(N)
2.M번의 연산 수행 반복문: O(M k)
총 M번 반복 수행
한 번 수행 시 reverseBaskets() 호출
이 메소드의 복잡도는 O(k) (k는 start, end 차이)
따라서 M번 수행 시 복잡도는 O(M k)
3.결과 출력 반복문: O(N)
배열 전체 순회하므로 O(N)
총 복잡도 = 1 + 2 + 3
= O(N) + O(M k) + O(N)
= O(N + M k + N)
장점
reverseBaskets() 메소드를 분리해 모듈화
해당 메소드만 독립적으로 변경할 수 있다.
단점
최악의 경우 O(M * N)의 시간복잡도 발생한다.
입력값이 커지면 연산 시간 증가량도 커진다.
입력 데이터 양이 많아지면 메모리 제약 발생할 수 있다.
마무리
오늘 문제는 11달전에 풀어본 문제였다. 하지만 전에 Scanner클래스를 이용해서 코드를 작성했기 때문에 이번에는 BufferedReader클래스를 이용해서 코드를 작성해봤다. 한번 풀어본 문제를 여러 방식으로 풀어보니깐 감회가 새로운것같다.
