[문제] SWEA 1289번 원재의 메모리 복구

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV19AcoKI9sCFAZN

SW Expert Academy

내 생각

 

1. 첫 풀이 (간단하게 푼 줄 알았으나 그렇지는 않았다. 코드가 간결하지는 않다는 뜻이다.)

change() 함수를 만들어서 특정 index 부터 num에 해당하는 수로 다 바꿔버리도록 했다.

isSameArr()는 현재 배열이 원본 배열과 동일한지 검사하는 함수다.

func()이 답을 구하는 함수이다.

이 때, 원본 배열과 초기 배열에서 값이 처음으로 다른 index 부터 change하면 되니까 저런 식으로 문제를 풀어보았다.

import java.io.*;

public class Solution {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(in.readLine());	// 테스트케이스 수
		//입력받기
		for (int i = 0; i < T; i++) {
			String s = in.readLine();
			int[] arr = new int[s.length()];
			for (int j = 0; j < s.length(); j++) {
				arr[j] = s.charAt(j) - '0';
			}
			sb.append("#").append(i+1).append(' ').append(func(arr)).append('\n');
		}
		System.out.println(sb);
	}

	// num: 0 또는 1
	static void change(int[] arr, int target, int num) {
		int len = arr.length;
		for (int i = target; i < len; i++) {
			arr[i] = num;
		}
	}
	// 두 배열이 동일한지 확인
	static boolean isSameArr(int[] arr1, int[] arr2) {
		int len = arr1.length;
		for (int i = 0; i < len; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}
	// 초기 상태에서 arr 까지 변경되는데 걸리는 최소 회수
	static int func(int[] arr) {
		int len = arr.length;
		int ans = 0;

		int[] tmp = new int[len];

		for (int i = 0; i < len; i++) {
			if (arr[i] == tmp[i]) {
				continue;
			}
			change(tmp, i, arr[i]);
			ans++;
			if (isSameArr(arr, tmp)) {
				break;
			}
		}
		return ans;
	}
}

 

2. 두번째 풀이

초기 메모리는 원본 메모리 bit 수 만큼 0으로 채워있다. 초기 메모리 bit 를 나타내는 것을 point 변수에 담는다.

원본 배열을 순회하면서, point와 해당 원본 배열의 idx 값이 다르다면, point를 그 값으로 바꾸고, 변경횟수를 1만큼 증가시키면 된다.

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

public class Solution{
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(in.readLine());
		
		for(int j=0;j<T;j++) {
			String s = in.readLine();
			int len = s.length();
			int[] arr = new int[len];
			
			for(int i=0;i<len;i++) {
				arr[i] = s.charAt(i) - '0';
			}
			int point = 0;
			int ans = 0;
			for(int i=0;i<len;i++) {
				if(point != arr[i]) {
					point = arr[i];
					ans++;
				}
			}
			sb.append("#").append(j+1).append(' ').append(ans).append('\n');
		}
		System.out.println(sb);
	}
}

 

3. 세번째 풀이 - 재귀적으로 풀어보기

static void change(int[] arr, int point, int cnt) {
		if(cnt == arr.length) {
			return;
		}
		if(arr[cnt] != point) {
			point = arr[cnt];
			totalCnt++;
		}
		change(arr, point, cnt+1);
	}