아레나란
아레나 참가신청 페이지 : https://solved.ac/arena
최근 백준과 solved.ac에 아레나라는 기능이 추가되었다.
기존의 대회와 비슷한데, 일회성으로 끝나는 것이 아니라 대회 결과에 따라 레이팅을 부여하여 레이팅이 상승 및 하락하는 재밌는 시스템이다.
sovled.ac이 공식적으로 개최하는 그랜드 아레나가 있고, 기존에 열리던 각종 사설? 대회도 승인을 받으면 아레나로 인정이 되는 것 같다.
문제 목록
A ~ I까지 총 9문제가 출제되었다.
A, B 두 문제는 쉽게 풀 수 있는 브론즈 문제가 출제되었고, C부터는 최대 다이아까지의 랜덤 난이도 문제가 배정되었다고 한다.
그래도 4문제는 풀 수 있지 않을까 했는데, 그나마 풀만하다고 생각한 F번에서 시간을 모조리 탕진하여 3문제로 아레나를 마무리 하였다.
아레나 문제는 백준에서 28431 ~ 28439번 문제로 모두 풀어볼 수 있으니 관심이 있다면 풀어보자
문제 후기
- 문제 난이도는 8/7 12시 기준입니다.
A. 양말 짝 맞추기 (B4)
[5, 1, 3, 1, 5]
위와 같이 같은 숫자 두 쌍과 혼자 있는 숫자 하나가 있는 길이 5개의 정수가 입력으로 주어진다.
이 중에 짝이 없는 숫자 하나를 찾아 출력하면 되는 쉬운 문제이다.
코드
if __name__=="__main__":
socks_list = [int(input()) for _ in range(5)]
socks_set = set()
for sock in socks_list:
if sock in socks_set:
socks_set.remove(sock)
else:
socks_set.add(sock)
[print(sock) for sock in socks_set]set을 이용해 set에 값이 없다면 set에 추가하고, 있다면 제거하는 식으로 짝이 없는 숫자만 남기는 방식을 사용했다.
사실 N=5가 고정이기 때문에 그냥 리스트를 쭉 입력받은 뒤 count 같은 함수를 입력하는게 더 쉽지 않았을 까 생각한다.
B. 끝말잇기 (S5)
charlie - echo - ? - romeo - oscar 와 같이 끝말잇기가 되는 문자열이 차례로 주어진다.
여기서 ?는 o로 시작해서 r로 끝나야 한다는 것을 알 수 있다.
또한 추가 조건으로, 이미 주어진 문자열에 있는 단어가 중복 등장해서는 안된다.
다음으로 대답할 수 있는 문자 후보군이 주어진다.
"alfa", "oscar", "or"
이 경우 "oscar"는 이미 주어진 문자열에 있기 때문에 대답할 수 없다.
때문에 정답은 "or"가 된다.
코드
if __name__ == "__main__":
N = int(input())
words = [input() for _ in range(N)]
words_set = set(words)
prev_word = ""
next_word = ""
for i in range(N):
word = words[i]
try:
next_word = words[i+1]
except IndexError:
next_word = ""
if word == "?":
break
prev_word = word
M = int(input())
for _ in range(M):
word = input()
if ((not prev_word or word[0] == prev_word[-1])
and (not next_word or word[-1] == next_word[0])
and word not in words_set):
print(word)
break?가 맨 처음이나 맨 끝에 등장할 수 있기 때문에 이를 처리하는 방법을 조금 고민했다.
"?"가 맨 앞에 나오는 경우 그냥 next_word만 저장한 뒤 곧바로 반복문을 탈출했다.
이 경우 prev_word가 빈 문자열이므로 단어 앞에 무슨 문자가 와도 상관이 없다. 이를 조건문에 or로 추가하였다.
"?"가 맨 끝에 나오는 경우 try ~ except를 이용해서 next_word를 빈 문자열로 만든 뒤 빠져나오도록 하였다.
이 경우 next_word가 빈 문자열이므로 단어 끝에 무슨 문자가 와도 상관이 없다. 이를 조건문에 or로 추가하였다.
이미 등장한 단어가 중복 등장하는 것을 확인하기 위해서 set을 이용하였다.
H. 행렬 연산 (행렬계산하기) (S3)
행렬의 특정 행, 특정 열을 골라 특정 값을 모두 더하는 연산을 Q회 수행했을 때의 행렬을 출력하는 문제이다.
행렬의 각 셀을 일일히 더해주다가는 N*M이 최대 500,000, Q도 최대 500,000이기 때문에 곧바로 시간초과가 발생한다.
때문에 N*M의 행렬을 선언하는게 아니라, 길이 N의 row 배열, 길이 M의 col 배열을 선언하여 쿼리에 맞게 값을 더해 준 뒤,
출력할 때 i행 j열의 값을 row[i] + col[j]로 더해주면서 출력해야 한다.
이러면 쿼리 연산을 수행하는 과정이 O(N) 또는 O(M)이 아니라 O(1)로 수행되어 시간을 줄일 수 있다.
코드
import sys
input = sys.stdin.readline
if __name__ == "__main__":
N, M, Q = map(int, input().split())
row = [0] * N
col = [0] * M
for _ in range(Q):
operator, idx, num = map(int, input().split())
idx -= 1
if operator == 1:
row[idx] += num
else:
col[idx] += num
for i in range(N):
for j in range(M):
print(row[i]+col[j], end=" ")
print()위에서 설명한 내용을 그대로 구현한 것이다.
개인적으로 아이디어 떠올리는게 어려워서 실버3보다는 높아도 되지않을까 싶지만.. 고수분들이 실버3이라면야 ㅠㅠ
F. 돌 옮기기 (D5)
세상에 남은 문제중에 그나마 풀만 하다고 생각해서 접근했는데 다이아 문제였다.
틀린 코드
import sys
input = sys.stdin.readline
STONE_TO_IDX = {
"W": 0,
"B": 1
}
if __name__=="__main__":
T = int(input())
for _ in range(T):
stones = input().rstrip()
move_count = [0, 0] # 돌을 밀 수 있는 횟수 0:W, 1:B
prev = "." # 이전에 나온 돌을 저장
move = 0 # 연속으로 나온 "."의 횟수를 저장 (돌을 밀 수 있는 횟수)
stroke, prev_stroke = 0, 0 # 연속으로 나온 W, B의 횟수를 저장
for idx, stone in enumerate(stones[::-1]):
if stone == ".":
move += 1
continue
if stroke > prev_stroke:
move_count[STONE_TO_IDX[prev]] += move * (stroke - prev_stroke)
move = 0
if stone == prev:
if stroke >= prev_stroke:
stroke += 1
else:
prev_stroke = 0
stroke = 1
else:
prev_stroke = stroke
stroke = 1
prev = stone
# 탐색 완료 후 후처리
if stroke > prev_stroke:
move_count[STONE_TO_IDX[prev]] += move * (stroke - prev_stroke)
print("WHITE" if move_count[0] > move_count[1] else "BLACK")문제로 주어진 배열을 거꾸로 뒤집은 다음, 각 돌을 옮길 수 있는지 여부를 조건문으로 검사해서 move_count에 옮길 수 있는 만큼 더하는 식으로 문제를 풀었다.
예제 테스트 케이스와, 내가 직접 작성한 테스트 케이스 모두 문제 없이 통과했는데 (손으로 move_count를 비교해보기도 했는데 맞았다)
제출해보니 계속 틀렸다는 결과만 나왔다.
에디토리얼을 본 결과 접근 자체는 비슷하게 한 것 같은데 뭔가 현재 코드가 검사하지 못하는 조건이 하나 정도 더 있는 것 같다.
반례
1
.W....BW.
expected : "WHITE"
output : "BLACK"위 상황에서 가장 왼쪽에 있는 W를 움직이면 B는 오른쪽의 B를 움직일 수 밖에 없고, 끝까지 움직일 경우 결국 한 번 더 움직일 수 있는 WHITE가 승리한다.
그런데 위 코드에서는 move_count가 [0, 0]이기 때문에 먼저 시작하는 WHITE가 진다는 결과를 출력한다.
결국 접근 방향이 좀 잘못되었다는 결론이다.
틀린 코드같은 경우는 '.'을 만날 때마다 움직일 수 있는 move값을 더한 다음 새로운 stone을 만났을 때 이전에 저장했던 값을 바탕으로 처리했지만
에디토리얼의 접근은 '.'을 만날 때마다 W가 움직일 수 있다면 그만큼 +를, B를 움직일 수 있다면 그만큼 -를 준다.
for idx, stone in enumerate(stones[::-1]):
# 맨 뒤에있는 "." 들을 버리는 부분
if prev == ".":
prev = stone
if prev == ".":
continue
if stone == ".":
move += (1 if prev=="W" else -1) * cnt
elif prev == stone:
cnt += 1
else:
cnt = 0
prev = "."이렇게 실시간으로 돌을 만날 때마다 처리를 해주어야 반례 없이 풀 수 있는 문제였다.
아마 '.'을 그냥 지나가는 빈 칸 정도로 생각하고, 'W', 'B'만 중요하게 생각하다가 잘못된 코드를 작성하게 되지 않았나 싶다.
결과
1.4천명의 참가자중에 299등을 기록했다.
퍼포먼스는 SS가 찍혔는데, 아마 첫 아레나라 많은 사람들이 참여하다보니 뻥튀기가 많이 된 것 같다.
아레나 퍼포먼스 계산 로직을 확인해보니 첫 아레나에서는 참가자들의 AC 레이팅(백준 티어점수)을 고려한다고 한다.
지금이야 사람들이 많이 관심을 갖고 티어에 상관없이 참여하고 있지만,
나중에 참가자들이 줄어 "진짜"들만 남게되면 퍼포먼스 점수를 얻기가 많이 빡세지지 않을까...
참가 보상으로는 예쁜 solved.ac 배너와 뱃지들을 받을 수 있다.
무려 움직인다.
소감
A, B문제를 나름 빠르게 풀었다고 생각했는데
내가 브론즈 2문제를 푸는 동안 플레~다이아급 문제를 3~4문제씩 풀어서 스코어보드에 등재되어있는 사람들을 보고 세상엔 괴물이 참 많구나라는 것을 느꼈다.
꾸준히 풀어서 기업용 코테를 정복할 수 있을 수준이 되야 이들의 발끝이라도 따라 갈 수 있을 것 같다고 생각하면서
알고리즘 공부를 꾸준히 해야겠다는 것을 느꼈다.
