누적합 문제1 [백준] 오타 - 5875 문제링크 5875번: 오타 올바른 괄호쌍을 좋아하는 키파는 최근에 노트북을 샀다. 그런데 키보드의 크기가 너무 작았기 때문에, 키파는 혹시 여는 괄호와 닫는 괄호를 서로 잘못 입력하지 않았는지 걱정되었다. 키 www.acmicpc.net 최대 100,000개의 입력값이 주어지며 1초의 시간 안에 풀어야 하므로 log(n) ~ nlog(n) 안에 풀어야 합니다. 변경할 괄호의 위치를 순환하는 n은 필수적으로 소모되므로 변경된 문자열이 올바른 괄호쌍인지 판단하는데 소모되는 시간은 log(n) 보다 짧아야 합니다. 문제를 풀기 위해 누적합(prefix sum) 알고리즘을 사용했습니다. 해당 알고리즘은 n만큼의 시간을 소요하여 새로운 정보를 만든 후 해당 정보를 1만큼의 시간을 통해 가공하여 답을 찾습니다. 풀.. 2023. 12. 8. 이전 1 다음
