likemath1997

풀이 및 사고일단 누적합이라는 걸 알고 풀긴했다.. ㅎ문제에서 최대 한번의 오타를 냈다는 말이 있다. 이 말로 케이스(나올 수 있는 누적합 경우의 수)가 확 줄어들기 때문에 꼭 기억하고 풀어야 한다.처음 생각으로는 여는 괄호를 1, 닫는 괄호를 -1로 체크한 배열을 만들었다. 예시는 닫는 괄호가 더 많은 케이스라 누적합 처리를 하면 배열의 총합이 -2가 나온다.()(()))) ⇒ [1, -1, 1, 1, -1, -1, -1, -1] ⇒ [1, 0, 1, 2, 1, 0, -1, -2]여기서 문제가 어떤 괄호를 고쳐야 올바른 괄호쌍이 될 수 있는지 판단해야 하는 것이다.나올 수 있는 케이스를 먼저 생각해보면 누적합이 0, 2, -2인 케이스 밖에 없다.올바른 괄호쌍이거나 여는 괄호가 1개 많은 경우이거나 닫..

일단 모든 순열을 구해서 다음 순열을 찾으려면 순열에만 10000!(팩토리얼)을 쓰기 때문에 시간초과가 난다. 그래서 다른 방법을 써봤다. 기본적으로 a, b 두 스택을 이용했다. 스택을 나누는 대신 인덱스를 정해서 탐색해도 되지만, 직관적으로 이해가 잘돼서 스택을 이용했다. 이 방법을 이용하면 a, b 나누면서 N, b를 다시 탐색하면서 N으로 O(N)의 복잡도를 가진다고 생각한다. 기본 로직은 정답 코드에 적어놨다. 정답 코드 import sys n = int(sys.stdin.readline()) a = list(map(int, sys.stdin.readline().split())) b = [] # 12345 => a = [1, 2, 3, 4, 5], b = [] => b.append(a.pop()..