USACO 2023 US Open Contest, Bronze Problem 1 FEB

USACO 2023 US Open Contest의 Bronze 1번 문제 FEB 입니다.

본 포스트는 이해를 돕기 위해 문제를 간략하게만 정리하였으므로 상세 내용과 코드 제출은 아래 링크를 참고해 주세요.

USACO

 

문제 개요 설명

---

베시와 엘시가 서로 메시지를 주고받고 있습니다. 여기서 베시가 보낸 메시지는 B로, 엘시가 보낸 메시지는 E로 표시됩니다.

예를 들어 메시지 리스트는 BBEBE 와 같이 표현할 수 있습니다.

그런데 존이 중간에서 베시와 엘시의 메시지를 가로채, 몇몇 메시지를 누가 보낸 메시지인지 알 수 없게 바꾸어 버렸습니다. 존이 바꿔버린 메시지는 F로 표시됩니다. 이는 FEBFE 와 같이 표현할 수 있습니다.

 

이렇게 B와 E와 F가 섞여있는 메시지 리스트가 있을 때, 한 사람이 연속된 메시지를 보내는 경우가 몇 가지 나올 수 있을지 알아보려 합니다.

연속된 메시지란 메시지에서 EE 혹은 BB가 연속해서 2회 나타나는 경우를 의미합니다. 예를 들면, 메시지 리스트가 BBEBEE일 경우 연속된 메시지는 2개입니다.

하지만 중간에 F가 섞여 있다는 것을 잊지 말아야 합니다. 이 F로 표시된 메시지는 누가 보냈는지 알 수 없기 때문에, B가 될 수도 E가 될 수도 있습니다. 그렇기 때문에 이러한 메시지를 체크하려면 경우의 수를 모두 고려해야 합니다.

예를 들어, BFFE는 아래와 같이 연속된 메시지가 0개 혹은 2개가 등장할 수 있습니다.

 

BBBE	2개
BBEE	2개
BEBE	0개
BEEE	2개

 

이와 같은 방식으로 주어진 메시지에서 베시와 엘시가 연속된 메시지를 보내는 모든 경우의 수를 알아내 주세요.

 

입력

---

• 첫 번째 입력은 주어지는 메시지의 길이를 의미하는 정수 N입니다.
• 두 번째 입력은 메시지를 의미하는 문자열 S입니다.

출력

---

• 첫 번째 줄에는 연속된 메시지를 보내는 경우가 총 몇 가지 나올 수 있는지를 의미하는 정수 K를 출력합니다.
• K개 각 케이스별로 연속된 메시지가 몇 개 나오는지를 출력합니다. 

 

입출력 예시

---

입력 :

4
BEEF

출력 :

2
1
2

BEEF 에서 고려해야 할 부분은 마지막 F 부분입니다. 이를 참고해서 모든 경우의 수를 구해보겠습니다.

 

BEEB	1개
BEEE	2개

 

따라서 총 두 가지 경우가 있으며, 1개가 나오는 경우 그리고 2개가 나오는 경우입니다.

 

 

입력 :

5
BFFFB

출력 :

3
0
2
4

동일하게 모든 경우의 수를 구해보면 다음과 같습니다.

 

BBBBB	4개
BBBEB	2개
BBEEB	2개
BEEEB	2개
BEBBB	2개
BEEBB	2개
BEBEB	0개
BBEBB	2개

 

따라서 총 3가지 경우가 있으며, 0개가 나오는 경우, 2개가 나오는 경우, 4개가 나오는 경우입니다.

 

솔루션 코드

---

input_n = int(input())
input_text = input()

# F로만 이루어진 문자열인 경우 처리하기
if input_text.count('F') == len(input_text):
   input_text = 'E' + input_text[1:]

# 패턴 적용을 위해 인덱스 값을 이용하여 문자열을 작은 구간들로 쪼개기
message_index = [i for i in range(len(input_text)) if input_text[i] != 'F']

min_range = 0
max_range = 0

# 쪼갠 구간들에서 연속문자 최소개수, 최대개수를 구하기
for i,k in zip(message_index,message_index[1:]):

    # 시작과 끝이 같고, 짝수이면
    if (k-i+1) % 2 == 0 and input_text[i] == input_text[k]:
        min_range += 1
    
    # 시작과 끝이 다르고, 홀수이면
    elif (k-i+1) % 2 != 0 and input_text[i] != input_text[k]:
        min_range += 1
    
    # 시작 끝이 같으면 최대값은 n-2
    if input_text[i] == input_text[k]:
        max_range += k-i
    # 시작 끝이 다르면 최대값은 n-2
    elif input_text[i] != input_text[k]:
        max_range += k-i-1

# 문자열의 시작/끝이 F라면 F의 개수 체크하기
count_f = input_n - message_index[-1] - 1 + message_index[0]

# 최소개수, 최대개수 사이의 정답들 출력하기
result = []
for i in range(min_range,max_range+count_f+1,1+(count_f == 0)):
    result.append(i)

print(len(result))
print(*result,sep='\n')

 

코드 설명에 앞서, USACO에서 제공해 주는 솔루션 설명을 참고하여 코드를 작성했기 때문에 아래 링크에서 확인해 주시면 더욱 자세한 내용을 확인하실 수 있습니다.

Solution - FEB (USACO Bronze 2023 Open)

 

만약 주어진 문자열이 시작과 끝이 1개의 E 혹은 B로 둘러싸인 F로만 이루어져 있다고 가정할 경우, 우리가 알고자 하는 연속된 메시지가 나오는 경우의 수에는 특정 조건에 따른 일정한 패턴이 존재합니다. 먼저 해당 조건들을 정리해 보겠습니다. 총 4가지가 존재합니다.

 

• 문자열의 시작과 끝이 같은 경우 (BFFB, EFE)
• 문자열의 시작과 끝이 다른 경우 (EFB,BFFE)
• 문자열의 길이가 짝수인 경우 (EFFE, BFFFFE)
• 문자열의 길이가 홀수인 경우 (BFB, EFFFE)

해당 조건들을 조합함에 따라 등장하는 패턴은 다음과 같습니다.

 

조건		등장값 범위	예시
문자열의 시작과 끝 동일	문자열의 길이가 짝수	1 ~ n-1	BFFB
	문자열의 길이가 홀수	0 ~ n-1	EFE
문자열의 시작과 끝 상이	문자열의 길이가 짝수	0 ~ n-2	BFFE
	문자열의 길이가 홀수	1 ~ n-2	EFFFB

 

조건들에 따라 연속된 메시지가 등장할 수 있는 최소 개수값과 최대 개수값을 위와 같이 알아낼 수 있는데요. 중간 F가 어떻게 조합되냐에 따라, 이 범위 내에서 나타나는 연속 메시지의 개수가 달라지게 될 것입니다.

 

이때, 앞뒤에 다른 문자들로 둘러싸여 있는 F들은 어떤 문자로 인식되는가에 따라 앞뒤 두 가지 경우에 영향을 주기 때문에, 연속된 메시지가 등장하는 등장값의 최소~최대 범위 내에서 경우의 수는 2씩 증가하게 됩니다. 예를 들어 시작과 끝이 다르고, 문자열의 길이가 7인 경우에는 연속된 메시지가 1,3,5개 등장하게 됩니다. (1부터 n-2까지 2씩 증가)

 

그렇다면 반대로 F로 시작하거나 F로 끝나는 문자열일 때는 어떨까요? 이런 경우 F는 자기 자신의 앞, 혹은 뒤 한 가지 문자에만 영향을 주게 됩니다. 따라서 이 상황에서는 최소~최대 범위 내에서 경우의 수가 1씩 증가하는 것이 가능해집니다.

 

이제 위 내용을 바탕으로 코드를 이해해 보도록 하겠습니다.

input_n = int(input())
input_text = input()

# 패턴 적용을 위해 인덱스 값을 이용하여 문자열을 작은 구간들로 쪼개기
message_index = [i for i in range(len(input_text)) if input_text[i] != 'F']

min_range = 0
max_range = 0

문제를 풀이하는 기본 아이디어는 문제로 주어지는 문자열을 여러 부분으로 분할하여 계산한 후에 다시 합쳐서 답을 구하는 것입니다. 따라서 문자열을 쪼개어 위에서 찾아낸 패턴을 적용시킬 수 있는 형태로 만드는 작업이 필요합니다.

F가 아닌 문자들의 인덱스를 모두 구해줍니다. 이를 가지고 자연스럽게 BFFE, EFE 등등 패턴 적용이 가능한 문자열의 정보를 알아낼 수 있게 됩니다.

# 쪼갠 구간들에서 연속문자가 등장할 수 있는 최소개수, 최대개수를 구하기
for i,k in zip(message_index,message_index[1:]):

    # 시작과 끝이 같고, 짝수이면
    if (k-i+1) % 2 == 0 and input_text[i] == input_text[k]:
        min_range += 1
    
    # 시작과 끝이 다르고, 홀수이면
    elif (k-i+1) % 2 != 0 and input_text[i] != input_text[k]:
        min_range += 1
    
    # 시작 끝이 같으면 최대값은 n-2
    if input_text[i] == input_text[k]:
        max_range += k-i
    # 시작 끝이 다르면 최대값은 n-2
    elif input_text[i] != input_text[k]:
        max_range += k-i-1

알아낸 패턴 규칙에 따라 등장 범위의 최솟값 최댓값을 구해줍니다.

# 문자열의 시작/끝이 F라면 F의 개수 체크하기
count_f = input_n - message_index[-1] - 1 + message_index[0]

# 최소개수, 최대개수 사이의 정답들 출력하기
result = []
for i in range(min_range,max_range+count_f+1,1+(count_f == 0)):
    result.append(i)

print(len(result))
print(*result,sep='\n')

우리가 앞서 계산한 부분에는 F로 시작/끝나는 문자열에 대한 내용이 없었기 때문에, 추가적으로 주어진 전체 문자열의 시작과 끝이 F로 시작하는 경우라면 이 부분도 체크해야 합니다. 코드에서는 count_f 변수를 이용해 해당되는 F가 몇 개인지 확인했습니다.

 

이때 count_f가 존재한다면(count_f > 0) 최댓값에 해당 F의 개수만큼 경우의 수를 더해 주고, 등장값은 1씩 증가하게 됩니다. 반면 존재하지 않는다면 더할 값은 없고, 그대로 2씩 증가하게 됩니다.

# F로만 이루어진 문자열인 경우 처리하기
if input_text.count('F') == len(input_text):
   input_text = 'E' + input_text[1:]

마지막으로 모든 문자가 F만 주어질 경우를 처리하기 위해 예외 처리를 해 주었습니다. 해당 방법 외에도 F만 주어지는 경우가 들어오면 바로 계산해서 값을 출력하도록 구조를 작성하는 경우도 있을 것 같습니다.