[Python 파이썬] SWEA 1289번 - 원재의 메모리 복구하기

2024년 5월 8일

문제 링크 : SWEA 1289번 - 원재의 메모리 복구하기

SW Expert Academy

 

---

 

문제 접근

 

 

파이썬 기준, 10개의 테스트 케이스를 합쳐 4초의 시간 제한을 두고 있기 때문에, 시간복잡도를 고려해야겠다고 판단했다.

 

문제를 보면, 특정 인덱스 위치 값을 0 또는 1로 결정하면 해당 위치 이후부터 끝까지 모두 결정한 값으로 덮어 씌워지도록 설정이 되어있다.

 

이를 보고 " 초기 상태(모든 bit가 0)의 0번째 인덱스부터 끝까지, 원래 메모리의 인덱스 위치와 다르면 반대 값으로 치환해주어 그 뒤의 값도 계속 바꿔나가주면 되겠구나! " 라고 잠깐 생각했지만 위험한 생각이었음을 깨달았다.

시간복잡도가 O(N^2)이 되기 때문에 시간초과가 날 우려가 있기 때문.(해당 문제에서 최대 메모리의 길이 N은 50)

 

여기서 나는 어차피 특정 인덱스 위치 값을 결정지었다면 그 뒤의 값은 해당 값으로 덮어씌워졌을테니, 굳이 나머지 인덱스들의 값을 직접 바꾸지 않고, 마지막으로 바꾼 값을 기억만 해두면 배열을 처음부터 끝까지 순회함과 동시에 원하는 결과값을 도출할 수 있으리라 판단을 내렸다. ( 시간복잡도 O(N) )

 

---

 

원재가 복구해야 할 원래 메모리가 다음과 같다고 가정해보자.

 

011010

 

현재 초기화된 메모리인 000000을 선언해주고, 앞에서부터 비교해가며 수정 횟수를 증가시켜주면 되지만(아래 그림과 같음) 나는 해당 메모리 공간마저 아끼는 방식을 택하겠다.

 

초기화된 메모리인 now_memory를 선언하지 않고 메모리 공간을 아껴볼 것

 

 

위에서도 언급했듯, 어차피 앞에서 값을 수정하면 뒤의 모든 비트들 또한 같은 값으로 수정된다.

그렇기 때문에 "마지막으로 수정했던 bit 값" 만 따로 변수에 저장해두면 굳이 같은 사이즈의 초기 메모리를 선언하지 않아도 수정 횟수를 알아낼 수 있다.

 

같은 사이즈의 배열 대신, 마지막으로 결정한 bit 값을 담을 변수를 선언

 

 

0번째 인덱스 탐색

 

 

0번째 인덱스는 마지막으로 수정한 bit와 같기 때문에 수정이 필요 없다.

 

 

1번째 인덱스 탐색

 

 

1번째 인덱스는 마지막으로 수정한 bit와 다르기 때문에, bit를 수정해 주어야 한다.

 

 

인덱스가 1인 지점에서 bit를 0에서 1로 바꾸었다는 점은, now_memory의 1번째 인덱스부터 나머지 bit들을 모두 1로 바꾸었다는 것과 동일하다.

 

bit를 수정해주었기 때문에 cnt를 1 증가시켜준다.

 

 

2번째 인덱스 탐색

 

 

2번째 인덱스는 마지막으로 수정한 bit와 같기 때문에 수정이 필요 없다.

 

 

3번째 인덱스 탐색

 

 

3번째 인덱스는 마지막으로 수정한 bit와 다르기 때문에, bit를 수정해 주어야 한다.

 

 

인덱스가 3인 지점에서 bit를 0으로 수정했다는 것은 위 그림의 now_memory와 같은 상태를 지닌다고 볼 수 있다.

수정을 했기에 cnt를 1 증가시켜준다.

 

 

4번째 인덱스 탐색

 

 

 

4번째 인덱스는 마지막으로 수정한 bit와 다르기 때문에, bit를 수정해 주어야 한다.

 

 

bit를 수정했으므로 cnt를 1 증가시켜준다.

 

 

5번째 인덱스 탐색

 

 

 

5번째 인덱스는 마지막으로 수정한 bit와 다르기 때문에, bit를 수정해 주어야 한다.

 

 

bit를 수정했으므로 cnt를 1 증가시켜준다.

 

 

배열의 마지막까지 탐색이 끝나 로직이 종료되며 최종 cnt 값이 도출하고자 하는 값이 된다.

---

 

순서도

 

1. 복구하고자 하는 메모리의 원상태를 memory 배열에 문자열 형태로 입력받는다.

2. 수정 횟수를 담을 cnt와 마지막으로 수정한 비트 값 상태를 담을 bit를 선언한다.

3. memory의 0번째 인덱스부터 마지막까지 탐색한다.
3-1. 현재 탐색 중인 memory의 인덱스 값이 bit와 같지 않다면 bit를 반대 값으로 치환해주며 cnt를 1 증가시켜준다

4. 탐색이 종료되면 cnt를 출력한다.

 

---

 

입력 예제

 

2
0011
100

 

---

 

출력 예제

 

#1 1
#2 2

 

---

 

 

주의할 점

 

시간 제한을 캐치하여 시간복잡도를 최대한 줄이도록 로직을 구성해야 한다.

---

 

전체 코드

 

def solution():
    cnt = 0
    bit = 0
    for idx in range(len(memory)):
        if int(memory[idx]) != bit:
            cnt += 1
            bit += 1
            bit %= 2

    return cnt

T = int(input())

for test_case in range(1, T + 1):
    memory = input()

    print(f'#{test_case} {solution()}')

---

 

풀이 후기

 

시간 제한을 회피하기 위한 꼼수(?)가 빠르게 떠올라 쉽게 풀 수 있었던 문제였다.