1912번 - 연속합
실제 코드는 260줄부터입니다.
제 코드 알고리즘은 다음과 같습니다.
[
우선 0들은 집어넣지 않고 zero touch = true를 해줍니다.
모든 수열을 받아서 + - + - + .... - + (양수, 음수, 양수, ...) 로 압축합니다(합칩니다).
예를 들어, 23, 14, -5, -13, 0, 2, 15, -33 의 input이 주어진다면
{37, -18, 17} 이 됩니다. (양쪽 맨끝은 항상 양수가 되도록 음수를 제거합니다)
양수와 음수가 번갈아서 반복되는 형태가 된다면 이제 본격적으로 시작됩니다.
맨 오른쪽 3개를 추출하여 left, mid, right라 할 때,
이를 압축하는 방법은 크게 3가지가 있습니다.
1) left와 right 둘 다 |mid|보다 클 때 -> {... left, mid, right} -> {... left+mid+right}
나머지 경우 중
2) left >= right일 때 mid의 크기에 상관없이 {... left, mid, right} -> {... left}
3) left < right일 때 {... left, mid, right} -> {... left+mid,right}
3번의 경우 벡터의 끝이 - - + 의 형태가 될수 있는데, left가 음수인지 체크하여 left와 mid를 합쳐줍니다.
이 과정을 벡터의 크기가 2 이하일 때까지 진행 후 case 처리합니다.
getMAX()의 맨 윗부분에서 모두 음수일 경우 처리해 주었습니다.
]
질문에 나온 대부분의 반례를 모두 넣어본 결과 제대로 나오는데, 4%에서 바로 틀렸습니다가 떠버립니다..
만들어본 반례들이나 이미 있는 것들은 다 되는데 안되는 반례를 못찾겠네요ㅜㅜ
도와주세요..
코드 어딘가에서 메모리 침범이 일어나는 것 같습니다.
댓글을 작성하려면 로그인해야 합니다.
whdudgns412 5년 전
실제 코드는 260줄부터입니다.
제 코드 알고리즘은 다음과 같습니다.
[
우선 0들은 집어넣지 않고 zero touch = true를 해줍니다.
모든 수열을 받아서 + - + - + .... - + (양수, 음수, 양수, ...) 로 압축합니다(합칩니다).
예를 들어, 23, 14, -5, -13, 0, 2, 15, -33 의 input이 주어진다면
{37, -18, 17} 이 됩니다. (양쪽 맨끝은 항상 양수가 되도록 음수를 제거합니다)
양수와 음수가 번갈아서 반복되는 형태가 된다면 이제 본격적으로 시작됩니다.
맨 오른쪽 3개를 추출하여 left, mid, right라 할 때,
이를 압축하는 방법은 크게 3가지가 있습니다.
1) left와 right 둘 다 |mid|보다 클 때 -> {... left, mid, right} -> {... left+mid+right}
나머지 경우 중
2) left >= right일 때 mid의 크기에 상관없이 {... left, mid, right} -> {... left}
3) left < right일 때 {... left, mid, right} -> {... left+mid,right}
3번의 경우 벡터의 끝이 - - + 의 형태가 될수 있는데, left가 음수인지 체크하여 left와 mid를 합쳐줍니다.
이 과정을 벡터의 크기가 2 이하일 때까지 진행 후 case 처리합니다.
getMAX()의 맨 윗부분에서 모두 음수일 경우 처리해 주었습니다.
]
질문에 나온 대부분의 반례를 모두 넣어본 결과 제대로 나오는데, 4%에서 바로 틀렸습니다가 떠버립니다..
만들어본 반례들이나 이미 있는 것들은 다 되는데 안되는 반례를 못찾겠네요ㅜㅜ
도와주세요..