[알고리즘] 1289. 원재의 메모리 복구하기

 

0. 문제

 

SW Expert Academy

 

메모리 bit 중 하나를 골라 0인지 1인지 결정하면 해당 값이 메모리의 끝까지 덮어씌우는 것이다.

 

예를 들어 지금 메모리 값이 0100이고, 3번째 bit를 골라 1로 설정하면 0111이 된다.

 

원래 상태가 주어질 때 초기화 상태 (모든 bit가 0) 에서 원래 상태로 돌아가는데 최소 몇 번이나 고쳐야 하는지 계산해 보자.

 

---

1. C++

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int solve(vector<char>& input){
    int cnt = 0;
    char before = '0';

    for(int i = 0; i < input.size(); i++){
        if(input[i] != before){
            before = input[i];
            cnt++;
        }
    }
    return cnt;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int T;
    cin >> T;
    for(int tc = 1; tc <= T; tc++){
        int ret;
        string str;
        vector<char> input;

        cin >> str;
        for(char c : str){
            input.push_back(c);
        }

        ret = solve(input);

        cout << "#" << tc << " " << ret << '\n';
    }
    return 0;
}

모든 값을 다 알고 있을 필요는 없다.

 

앞서 설정한 값을 메모리 끝까지 덮어쓰기 때문에 char before로도 충분하다.

 

---

2. Java

import java.util.Scanner;
import java.io.FileInputStream;
import java.util.ArrayList;

class Solution
{
    public static int solve(ArrayList<Character> input){
        int cnt = 0;
        char before = '0';

        for(int i = 0; i < input.size(); i++){
            if(input.get(i) != before){
                before = input.get(i);
                cnt++;
            }
        }
        return cnt;
    }

    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++)
        {
            int ret;
      String str = sc.next();
      ArrayList<Character> input = new ArrayList<Character>();

      for(char c : str.toCharArray()){
          input.add(c);
      }
      ret = solve(input);

      System.out.println("#" + test_case + " " + ret);
        }
    }
}

 

선생님이 자바로 알고리즘을 푸는 것이 더 좋을 것 같다고 하셔서 앞으로는 자바로 더 많이 풀 것 같다.

 

---