들어가기 전에
고민 없이 바로 풀었던 문제는 정리하지 않았습니다.
지문은 이해했지만, 어떻게 풀지에 대해 고민해도 풀지 못한 것만 정리했습니다.
D. Colorful Stamp
https://codeforces.com/contest/1669/problem/D
2칸짜리 스탬프를 찍는 문제.
찍은 곳에 또 찍을 수 있고, 찍은 걸 회전할 수 있다.(스탬프 반대로 찍는다.)
단, 스탬프가 범위 밖으로 나가면 안 된다.
즉, 길이가 1이면 무조건 NO
풀이
문자 W를 기준으로 split한다.
만약, 문자열이 R이나 B만 있는 경우 NO를 출력
왜냐하면 스탬프는 범위 밖으로 찍을 수 없기 때문에
어떠한 경우에도 R이나 B 하나는 있어야 한다.
못푼 이유
WBW에서 NO가 난 것을 보고 겹쳐찍을 수 없는 경우(범위 이탈)에 대해 생각해봤지만,
W로 둘러쌓이지 않은 테스트 케이스의 경우
스탬프를 여러번 겹쳐찍는 과정에서 위의 풀이에 대한 코너케이스가 있지 않을까 생각했다.
또한, T = 10^4, N = 10^5였기 때문에, O(T *logN) 에 풀어야 한단 생각을 했다.
괜히 다른 기법들을 써야하나 고민만 하다 못푼 문제
코드
for _ in range(int(input())):
N = int(input())
s1 = input()
s2 = s1.split('W')
error = False
for s in s2:
if len(s) == 0:
continue
R = s.count('R')
B = s.count('B')
if R == 0 or B == 0:
error = True
break
if error:
print("NO")
else:
print("YES")
E. 2-Letter Strings
https://codeforces.com/contest/1669/problem/E
2개의 문자열들을 입력받아 서로 겹치는 쌍의 총합을 구하는 문제
3가지 조건을 만족해야 쌍을 이룰 수 있다.
1. 위치 상관 없이 문자 하나만 같아야 한다. (ab, ab는 계산 X)
2. 문자열이 위치 상관없이 같은 문자로 이루어진 경우는 계산하지 않는다. (ab, ba는 계산 X)
3. 중복된 쌍은 허용 X -> (ac, ab)와 (ab, ac)는 계산 X
풀이
2차원 배열을 2개 만든다.
data1은 문자열의 0번 index가 앞에 있는 기준
data2는 문자열의 1번 index가 앞에 있는 기준
입력받은 문자 s가 'ab'인 경우
1) : a* 인 모든 경우에 대한 합 - ab인 경우의 수를 계산한다. (1번 조건)
2) : b* 인 모든 경우에 대한 합 - ba인 경우의 수를 계산한다. (2번 조건)
만약, 위의 설명만 단순히 볼 경우
ab와 ca를 비교하는 경우, 조건에 맞음에도 합산이 안 된다 생각할 수 있다.
그렇기 때문에, data1과 data2에서 문자열 s의 원소들이 앞에 오는 경우의 수를 더해준다.
못푼 이유
a~z에 대한 카운팅 배열 하나만 놓고
문자열 s의 앞뒤가 같은 경우에 대해 분기 처리를 하다보니 코드가 복잡해졌다.
분기가 복잡하면 코너케이스들도 찾기 힘들어지고, 찾는다 해도 수정이 힘들기 때문에
지쳐서 포기했다.
또 이건 내 문제긴 한데, 그냥 배열을 새로 만들거나, 차원을 올리면 되는데
이상한 부분에서 하나로 퉁쳐서 풀다보니 자꾸 이런 문제가 생긴다.
정답 코드
def index(n):
return ord(n) - ord('a')
for _ in range(int(input())):
N = int(input())
data1 = [[0] * 26 for i in range(26)]
data2 = [[0] * 26 for i in range(26)]
ans = 0
for i in range(N):
s = input()
ans += sum(data1[index(s[0])]) - data1[index(s[0])][index(s[1])]
ans += sum(data2[index(s[1])]) - data2[index(s[1])][index(s[0])]
data1[index(s[0])][index(s[1])] += 1
data2[index(s[1])][index(s[0])] += 1
print(ans)
오답 코드
from collections import Counter
T = int(input())
for i in range(T):
N = int(input())
nums = []
record = [0] * 26
for j in range(N):
a = list(input())
a.sort()
record[ord(a[0]) - ord('a')] += 1
if a[0] != a[1]:
record[ord(a[1]) - ord('a')] += 1
nums.append("".join(a))
countRecord = Counter(nums)
ans = 0
for num in nums:
index1 = ord(num[0]) - ord('a')
index2 = ord(num[1]) - ord('a')
record[index1] -= 1
if num[0] != num[1]:
record[index2] -= 1
temp = record[index1] + record[index2]
else:
temp = record[index1]
countRecord[num] -= 1
if num[0] != num[1]:
temp -= countRecord[num] * 2
else:
temp -= countRecord[num]
ans += temp
print(ans)
F. Eating Candies
https://codeforces.com/contest/1669/problem/F
누적합 + 투 포인터 문제
N과 T의 범위 때문에 누적합이 안 될줄 알았다.
풀이
Alice는 왼쪽, Bob은 오른쪽부터 스킵 없이 사탕을 가져야 한다.
각각의 방향에 대한 누적합을 구하고
이 누적합이 동일해지도록 사탕의 value를 빼준다.
이후, index를 잘 조절해서 더해주면 끝
못푼 이유
내가 시간 복잡도 계산을 잘못하는건지 모르겠는데
O()가 10억이 나오면 1초를 넘긴다고 생각하고 있다.
나는 누적합 시간 복잡도가 O(N)인줄 알았는데 뭔가 착각하고 있는게 있다.
그래서 이걸 이분탐색으로 어떻게 풀어야하나 고민만 하다 못푼 문제
++
지문 하단에 모든 테스트 케이스의 n의 합이 20만을 넘지 않는다고 한다.
다시 말해, 시간복잡도 계산을 모든 케이스가 아닌, 한 케이스를 기준으로 생각해도 된다고 한다.
코드
for _ in range(int(input())):
N = int(input())
candies = list(map(int, input().split()))
left, right = 0, N - 1
alice, bob = 0, 0
while left <= right:
if alice < bob:
alice += candies[left]
left += 1
else:
bob += candies[right]
right -= 1
left -= 1
right += 1
while alice != bob:
if alice < bob:
bob -= candies[right]
right += 1
else:
alice -= candies[left]
left -= 1
print((left + 1) + (N - right))
G. Fall Down
문제 자체는 쉽지만, 코테같이 시간이 촉박한 상황에선 당황해서 못푸는 문제 (개인적 생각)
설명보단 백준 관련 문제를 풀어보면 바로 이해가 될거 같다.
이걸 큐로 풀어야 하나 생각했는데 투 포인터로 풀 수 있는 모양