[SWEA/C++] 1289. 원재의 메모리 복구하기(D3)

풀이 시간: 1시간 - 처음에 bit 값을 그대로 받으려다가 string 라이브러리로 바꾸는 과정에서 시간 소요

시간 복잡도: O(T*N) - N은 str 문자열의 길이

공간 복잡도: O(1) - 전부 상수 값이므로

문제

원재가 컴퓨터를 만지다가 실수를 저지르고 말았다. 메모리가 초기화된 것이다.

다행히 원래 메모리가 무슨 값이었는지 알고 있었던 원재는 바로 원래 값으로 되돌리려고 했으나 메모리 값을 바꿀 때 또 문제가 생겼다.

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

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

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

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 메모리의 원래 값이 주어진다.

메모리의 길이는 1이상 50이하이다.

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

초기값(모든bit가 0)에서 원래 값으로 복구하기 위한 최소 수정 횟수를 출력한다.

문제 풀이

문제 접근은 다음과 같이 했다.

 

1. 먼저 메모리를 string으로 받아서 저장하여 각 위치에 접근이 쉽도록 하였다.

 

2. flag 변수를 활용하여 그 이전 값이 1인지 0인지 검증할 수 있도록 했다.

 

3. 문자열을 처음부터 하나씩 탐색하는데, 이때 첫 번째 문자열이 1일 경우에만 flag와 cnt 값을 변경한다.

• 그 이유는 메모리 초깃값이 모든 bit가 0이기 때문에, 첫 번째 문자열이 0일 경우는 고려하지 않아도 되기 때문이다.

4. 첫 번째 문자열 외의 값은 그 이전 값이 0이고 현재 문자열이 1 일 경우 cnt를 증가해주고, 그 반대의 경우에도 cnt를 1 증가해주었다.

 

전체 코드

#include <iostream>
#include <string>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        string str; // 문자열을 string으로 저장
        int cnt = 0, flag = 0; // 개수 저장할 cnt 값, 현재 0인지 1인지 구분하는 flag 값
        cin >> str;
        for (int j = 0; j < str.length(); j++) {
            if (j == 0) { // 첫 번째 문자열 값 처리
                // 1일 경우 flag를 1로 바꾸고 cnt 값을 1 증가, 0일 경우 아무 것도 하지 않음(초깃값이 모든 bit가 0 이므로)
                if (str[j] == '1') { flag = 1; cnt++; }
                else continue;
            } else { // 첫 번째 문자열 외의 값 처리
                // flag가 0(이전 값이 0), 현재 문자열이 1일 경우, flag와 cnt 값 변경
                if (flag == 0 & str[j] == '1') { flag = 1; cnt++; }
                // flag가 1(이전 값이 1), 현재 문자열이 0일 경우, flag와 cnt 값 변경
                if (flag == 1 & str[j] == '0') { flag = 0; cnt++; }
            }
        }
        cout << "#" << i << " " << cnt << "\n";
    }
}

 

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

SW Expert Academy