[백준] #24548 도로 정보 - 파이썬

문제

현대오토에버는 국내 최초로 차량 운전 지원용 지도 생성을 위한 MMS (Mobile Mapping System) 기반 정밀지도 구축 시스템을 도입했다. 이는 고성능 레이저 스캐너 장치인 라이다 (LiDAR) 를 포함한 다양한 센서를 활용하여, 도로 및 주변 지형 등의 정보를 빠짐없이 취득하는 최첨단 3차원 공간정보 조사 시스템이다. 이 지도 정보를 활용하면 운전자에게 여러 편의 기능을 제공해줄 수 있다. 예를 들어 운전자에게 고성능 내비게이션 서비스를 제공할 수도 있고, 더 나아가 자율 주행에 필요한 도로 교통 정보를 제공해 줄 수도 있게 된다.

현대오토에버의 연구원 알정이는 오늘 정밀지도 정보 수집 차량으로부터 특정 시내의 도로를 촬영한 데이터를 전달받았다. 이 데이터에는 도로 주변의 나무, 잔디, 울타리 그리고 사람들을 촬영한 내용이 담겨 있다. 알정이는 이를 내비게이션 시스템에 사용할 수 있는 데이터로 가공할 것이다. 본격적인 작업에 앞서 알정이는 전달받은 데이터의 특성을 파악해보려고 한다.

도로 데이터를 전부 보고 있을 시간은 없으므로 알정이는 도로의 흥미로운 구간 하나를 뽑아서 보려고 한다. 도로는 나무를 나타내는 T, 잔디를 나타내는 G, 울타리를 나타내는 F 혹은 사람을 나타내는 P 로 이루어진 길이 $N$의 문자열로 표현된다. 도로 구간이란 도로의 연속된 일부분을 의미하며, 도로의 연속 부분 문자열로 표현된다. 흥미로운 구간이란, 길이가 1 이상인 도로 구간 중 그에 속한 모든 물체의 수가 3의 배수인 것을 의미한다. 예를 들어 도로 구간에 나무 3개, 울타리 3개가 담겼다면 그 도로 구간은 흥미로운 구간이지만, 나무 3개와 울타리 2개가 담겼다면 이는 흥미로운 구간이 아니다.

도로의 정보가 주어졌을 때, 흥미로운 구간이 될 수 있는 도로 구간의 개수를 구해보자.

입력

첫 번째 줄에 정수 $N$이 주어진다. ($1 \leq N \leq 100\,000$ )

두 번째 줄에 도로를 표현한 길이 $N$의 문자열이 주어진다.

출력

첫 번째 줄에 흥미로운 구간의 개수를 출력한다.

예제 입력 1 

6
TTTGGG

예제 출력 1 

3

예제 입력 2 

6
FPFPFP

예제 출력 2 

1

---

복기

1. 단순 구현인줄 알았는데, 상태를 해시맵으로 관리하면서 푸는 문제였다. 내가 특히 이런 해시맵 문제를 많이 안 풀어본거 같은데 많이 풀어야 할거 같다.

2. 예제를 보면서 이해하는게 좋다. 

• N=6 N = 6 N=6, S="TTTGGG" S = "TTTGGG" S="TTTGGG"
• 초기 상태: (0,0,0,0)(0, 0, 0, 0)(0,0,0,0), 빈도 1
• 단계별 처리:
  • T: count = (1,0,0,0), state = (1,0,0,0), result += 0, state_count[(1,0,0,0)] = 1
  • T: count = (2,0,0,0), state = (2,0,0,0), result += 0, state_count[(2,0,0,0)] = 1
  • T: count = (3,0,0,0), state = (0,0,0,0), result += 1, state_count[(0,0,0,0)] = 2 (구간: TTT)
  • G: count = (3,1,0,0), state = (0,1,0,0), result += 0, state_count[(0,1,0,0)] = 1
  • G: count = (3,2,0,0), state = (0,2,0,0), result += 0, state_count[(0,2,0,0)] = 1
  • G: count = (3,3,0,0), state = (0,0,0,0), result += 2, state_count[(0,0,0,0)] = 3 (구간: GGG, TTTGGG)
• 결과: 3 3 3 (흥미로운 구간: "TTT", "GGG", "TTTGGG")

 

> 여기서 state는 해당 조합이 나왔는지를 체크한다.

> state_count를 통해서 해당 조합이 이전에 나왔는지 체크하며, 특히 마지막 같이 state=(0,0,0,0) 같이 이전에 한번 나왔던 경우는 state_count가 2인 상태여서 result+=2가 된다.

---

솔루션

from collections import defaultdict

N = int(input())
S = input().strip()

state_count = defaultdict(int)
state_count[(0,0,0,0)] = 1 # 초기 상태

count = {'T':0, 'G':0, 'F':0, 'P':0}
result = 0

for char in S:
    count[char] += 1

    #현재 상태
    state = (
        count['T'] % 3,
        count['G'] % 3,
        count['F'] % 3,
        count['P'] % 3
    )
    # 동일한 상태가 이전에 있었다면, 그 차이는 흥미로운 구간
    result += state_count[state]
    # 현재 상태를 해시 맵에 추가
    state_count[state] += 1

print(result)