[Python] 백준/BOJ 27970번: OX (Silver 1)

💻 Problem

문제 보러 가기

 

O와 X로 이루어진 문자열이 주어진다. 모든 문자를 X로 만들 때까지 다음 연산을 반복할 때, 시행하는 연산의 횟수를 구하시오.

• 문자열의 가장 왼쪽에 있는 O를 X로 바꾸고, 그보다 왼쪽에 있는 X를 전부 O로 바꾼다.

 

💡 Approach

처음에 예제만 봤을 때는 연산이 조금 헷갈렸어서 예제 1의 연산 과정을 정리해 봤다.

연산 횟수	연산 결과	설명
0	OXO	처음 입력받은 문자열이다
1	XXO	가장 왼쪽에 있는 O(i=0)를 X로 바꿨다 i=0이기 때문에 왼쪽에 요소가 없다
2	XXX → OOX	가장 왼쪽에 있는 O(i=2)를 X로 바꿨다 i=2보다 왼쪽에 있는 X를 전부 O로 바꿨다
3	XOX	가장 왼쪽에 있는 O(i=0)를 X로 바꿨다 i=0이기 때문에 왼쪽에 요소가 없다
4	XXX → OXX	가장 왼쪽에 있는 O(i=1)를 X로 바꿨다 i=1보다 왼쪽에 있는 X를 전부 O로 바꿨다
5	XXX	가장 왼쪽에 있는 O(i=0)를 X로 바꿨다 i=0이기 때문에 왼쪽에 요소가 없다

 

처음에 생각한 방식은 이렇다.

1. 가장 왼쪽에 있는 O 위치(target)를 찾는다.
   1. 없다면 0 출력 후 종료한다.
2. 연산을 반복한다.
   1. target 위치의 문자(가장 왼쪽 O)를 X로 바꾼다.
   2. 그보다 왼쪽에 있는 문자 전부를 O로 채운다.
   3. 연산 횟수를 증가시킨다.
   4. 다음 target을 찾는다.
      • 기존 target이 0보다 크다면, 위에서 왼쪽 전부를 O로 만들었으니 가장 왼쪽 O는 index 0이다.
      • 기존 target이 0이었다면, 해당 위치를 X로 바꿨으니 1부터 오른쪽으로 스캔하면서 0을 찾으면 target을 갱신한다.
        • 더 이상 O가 없으면 종료한다.
        • 종료는 target==0일 때만 발생한다. (스캔할 때 끝까지 O를 못 찾으면 종료하기 때문)

 

그렇게 구현한 코드가 아래 코드이다.

시간 초과였지만 여기에다가 리팩토링하는 방식일 줄 알았다..

아예 수학적으로 접근해야 되는 줄은 ㅠ

import sys
input = sys.stdin.readline

pattern = list(input().rstrip())
target = 0 # 가장 왼쪽에 있는 O
cnt = 0 # 연산 횟수

# 가장 왼쪽에 있는 O를 찾는다
target = -1
for i in range(len(pattern)):
    if pattern[i] == 'O':
        target = i
        break

# 입력받은 문자열에 O가 하나도 없다면 바로 종료한다
if target == -1:
    print(0)
    exit()

while True:
    # 문자열의 가장 왼쪽에 있는 O를 X로 바꾸고
    pattern[target] = 'X'
    # 그보다 왼쪽에 있는 X를 전부 O로 바꾼다
    pattern[:target] = ['O'] * target

    cnt += 1

    # 위에서 target보다 왼쪽에 있는 X를 전부 O로 바꿨으니
    # 가장 왼쪽에 있는 O는 0번째이다
    if target > 0:
        target = 0

    # target이 0이었다면 0번째 자리는 X로 바뀌었다
    # 0보다 오른쪽에서 다음 target을 찾아야 한다
    elif target == 0:
        scan = 1

        while scan < len(pattern) and pattern[scan] != 'O':
            scan += 1

        if scan < len(pattern):
            target = scan
        
        # 더 이상 O가 없으면 종료한다
        else:
            print(cnt % (1_000_000_007))
            exit()

 

잘 모르겠어서 찾아보니 다들 제곱으로 풀고 있었다.. 오잉

O를 1, X를 0으로 두고 이진수라고 생각하면 .. 그걸 10진수로 바꾼 값이 정답이었다.

(참고로 뒤집힌 모습이라 입력이 OXX라면, XXO를 10진수로 바꿔야 한다.)

 

이게 가능한 이유는 이 문제에서 주어진 연산이 이진수에서 1을 빼는 과정과 동일하기 때문이다.

이진수에서 1을 빼는 방법은 이렇다.

 

• 가장 오른쪽에 있는 1을 0으로 바꿈
• 그보다 오른쪽의 모든 0을 1로 바꿈

예를 들어, 이진수 100에서 1을 빼보자.

이진수 100은 10진수 4이므로 1을 빼면 10진수 3이 되어야 한다. (10진수 3 = 이진수 011)

가장 오른쪽에 있는 1(i=0)을 0으로 바꾸고 그보다 오른쪽의 모든 0(i=1,2)을 1로 바꾸면 011이 된다.

 

 

✏️ Solution

import sys
input = sys.stdin.readline

pattern = list(input().rstrip())
s = ''

for p in pattern:
    if p == 'O':
        s += '1'
    else:
        s += '0'

print(int(s[::-1], 2) % (1_000_000_007))

입력받은 문자열에서 O면 1, X면 0으로 바꿔줬다.

2진수 표현과 반대로 되어있기 때문에 문자열을 뒤집은 값(s[::-1])을 int()를 써서 10진수로 변환했다.

 

import sys
input = sys.stdin.readline

s = input().rstrip().replace('O', '1').replace('X', '0')

print(int(s[::-1], 2) % (1_000_000_007))

반복문으로 문자를 숫자로 바꿔줬던 부분을 replace 함수로 바꿨다.

이렇게 바꾸니 코드도 더 짧고 시간도 조금 더 빨라졌다.