SciComLove (2023)

https://www.acmicpc.net/problem/27913

SciComLove (2023) 문제를 재미있게 풀어서 풀이를 남기려고 한다.
왜냐하면 파이파이로도 파이썬3으로도 속도 1등을 해서다.
내가 제출한 시점에 나와 같은 정성스러운 아이디어로 푼 사람이 없어서 그런 것 같다.
아주 다양한 아이디어로 풀 수 있는 재미있는 문제였다.

문제 요약

• 길이 $N$인 문자열은 “SciComLove”가 무한 반복되는 문자열의 접두사이다.
  • 예: $N=15$ → "SciComLoveSciCo"
• $Q$번의 과정이 순차적으로 수행된다.
• 각 과정 $i$에서 주어진 위치 $X_i$($1 \le X_i \le N$)의 문자를
  • 대문자이면 소문자로,
  • 소문자이면 대문자로
    바꾼다.
• 각 과정을 마친 후 문자열에 남아 있는 대문자의 개수를 출력한다.

입력

1. 첫째 줄에 정수 $N$, $Q$
2. 둘째 줄부터 $Q$개 줄에 정수 $X_1, X_2, \dots, X_Q$ (각 줄마다 하나씩)

출력

• 각 과정이 끝난 직후의 대문자 개수를 한 줄에 하나씩 출력한다.

제한

• $1 \le N \le 2\times10^5$
• $1 \le Q \le 2\times10^5$
• $1 \le X_i \le N$ ($1 \le i \le Q$)
• 시간 제한: 2초, 메모리 제한: 1024 MB

서브태스크

번호 배점 추가 조건

1	10	$N$은 10의 배수, $Q=1$, $X_1=1$
2	15	$N\le100$, $Q\le100$
3	20	모든 과정에서 대문자를 소문자로만 바꾼다.
4	25	모든 $X_i$가 서로 다르다. ($X_i \neq X_j$ for $i<j$)
5	30	추가 제한 조건이 없다.

---

아이디어 1: 구현

사실 처음부터 구현으로 풀 생각이 없었고 가장 마지막에 만든 코드지만
설명 순서상 가장 기본적이고 간단한 코드라서 제시하겠다.

def sol():
    n,q=map(int,input().split())
    rpt,mod=divmod(n,10)
    w="SciComLove"
    a=w*rpt+w[:mod]
    s=3*rpt+sum(1 for c in w[:mod] if c.isupper())
    res=[0]*q
    for i in range(q):
        c=int(input())-1
        if a[c].isupper():
            s-=1
            a[c].lower()
        else:
            s+=1
            a[c].upper()
        res[i]=s
    print('\n'.join(map(str,res)))
sol()

말 그대로 구현 코드인데 그래도 완전 나이브하게 짜지는 않았다.
먼저 기본 단어인 w를 활용해 길이 n인 a를 만든다.

초기 대문자 수는 하나하나 세지 않고 (기본단어 반복횟수 * 3 + 나머지의 대문자 수)로 구했다.

그리고 q번 쿼리를 입력 받으면서 ,
대문자면 합계에서 1을 빼고 소문자로 바꾸고
소문자면 합계에 1을 더하고 대문자로 바꾼다.

이 과정에서 합계값을 기록하고 모아서 출력한다.

부분점수 55점을 받고 멈춘 이 코드는 시간이 무려 4892ms가 나왔다.

인풋을 빠른 것으로 바꾸어 봐도 140ms에 55점이다.

아이디어 2: 구현 개선(바이트)

문자열을 처리하는 게 느린 거니까 개선해 보겠다. 역시 지금 짠 코드이며 아이디어만 갖고 있었다.
바로 바이트 입력을 이용하는 것이다.

def sol():
    n,q,*qry=map(int,open(0,'rb').read().split())
    rpt,mod=divmod(n,10)
    w=b"SciComLove"
    a=bytearray(w*rpt+w[:mod])
    s=sum(ch<97 for ch in a)
    res = []
    for c in qry:
        i = c - 1
        if 65 <= a[i] <= 90:
            s -= 1
        else:
            s += 1
        a[i] ^= 32
        res.append(s)
    open(1,'w').write('\n'.join(map(str, res)))
sol()

코드의 특징을 간단하게 요약하면 다음과 같다:

---

코드의 핵심 특징

1️⃣ "SciComLove" 문자열 반복 생성

• 길이 $n$에 맞게 "SciComLove"를 반복하여 문자열 생성.
• 바이트 배열(bytearray)로 처리하여 효율적 변환 가능.

2️⃣ 대소문자 토글과 대문자 개수 관리

• 쿼리마다 1-based 인덱스의 문자를 대소문자 반전(^=32) 처리.
• 반전에 따라 대문자 개수 실시간 업데이트.

3️⃣ 빠른 처리 구조

• bytearray와 비트 연산을 통해 대소문자 변환 속도를 극대화함.
• 매 쿼리마다 대문자 개수를 저장 후 출력.

4️⃣ 파일 디스크립터 직접 사용

• open(0,'rb')로 표준 입력에서 바이트 단위 데이터 처리.
• open(1,'w')로 표준 출력에 결과 작성 (파일 대신 파일 디스크립터 사용).

아이디어 3: 문자열 말고 비트 연산

def sol():
    n,q,*qry=map(int,open(0).read().split())
    rpt,mod=divmod(n,10)
    w=[1,0,0,1,0,0,1,0,0,0]
    a=w*rpt+w[:mod]
    s=sum(a)
    res=[0]*q
    for i in range(q):
        c=qry[i]-1
        s+=-2*a[c]+1
        a[c]=1-a[c] #a[c]^=1
        res[i]=s
    print('\n'.join(map(str,res)))
sol()

코드를 간단명료하게 요약 설명하겠다.

---

코드 핵심 특징 요약

1️⃣ "SciComLove"의 대문자 여부만 저장

• "SciComLove"에서 대문자는 대문자 = 1, 소문자 = 0으로 변환 후 저장
  → [1,0,0,1,0,0,1,0,0,0] (S, C, L 대문자 → 1, 나머지는 0)

2️⃣ $n$길이만큼 a 배열 생성

• 전체 문자열의 대문자 여부 배열 a 생성 (길이 $n$)
• s는 초기 대문자 개수 (sum(a))

3️⃣ 각 쿼리 처리

• 쿼리마다 주어진 위치(c)의 대소문자 토글: a[c] = 1 - a[c]
• s를 업데이트: s += -2*a[c]+1
  → a[c]는 토글 직후의 값이므로, -2*a[c]+1은 토글 이전 상태에 따라 +1 또는 -1이 됨

4️⃣ 결과 출력

• 각 쿼리 처리 후의 s를 출력

---

간단 정리

• 문자열 전체를 바이트 배열 대신 0과 1로 변환하여 처리
• 대문자 여부만으로 문제를 단순화
• 시간복잡도는 $O(q)$, 문자열 생성은 한 번만 수행
• 간단하고 빠른 비트 기반 처리

이제 156 밀리세컨드가 나왔다.
여기서 입출력을 개선해주면 다음과 같은 최종 코드가 나온다.

def sol():
    import io
    input = io.BufferedReader(io.FileIO(0), 1 << 16).readline
    n,q=map(int,input().split())
    rpt,mod=divmod(n,10)
    w=[1,0,0,1,0,0,1,0,0,0]
    a=w*rpt+w[:mod]
    s=sum(a)
    res=[0]*q
    for i in range(q):
        c=int(input())-1
        s+=-2*a[c]+1
        a[c]=1-a[c]
        res[i]=s
    print('\n'.join(map(str,res)))
sol()

모든 코드 중 112등의 속도

파이썬(통합)에서 제일 빠르다 :)

파이썬 3에서 유의미한 속도 차이가 났다.

고수의 코드가 궁금해서 보았더니... 다시 제출하셔서 메모리 차이로 1등을 빼앗겼다...
이겨보려고 다양한 시도를 하다가 아래와 같이 짰는데 또 다른 방법이라 올려본다...

def sol():
    import io
    input = io.BufferedReader(io.FileIO(0), 1 << 16).readline
    n,q=map(int,input().split())
    s=i=k=0
    d=[3,3,4]
    w=bytearray([0]* n)
    while k<n:
        w[k]=1
        k+=d[i%3]
        i+=1
        s+=1
    res=[0]*q
    for i in range(q):
        c=int(input())-1
        s+=-2*w[c]+1
        w[c]=1-w[c]
        res[i]=s
    print('\n'.join(map(str,res)))
sol()

메모리는 더 줄이는 데 성공했는데 속도가.... 못 이기겠다.

🍆