park345601   5년 전

v1과 v2를 비교하는 if문은 혹시몰라서 썼긴했지만

for문들을 돌면서 가장 값차이가 적게나는 소수의 합을 구하고 v1과 v2도 크기순으로 된다고 생각합니다

그런데 제출시 틀렸습니다가 나와서 

어디가 잘못된 부분인지 조언해주시면 감사하겠습니다!

djm03178   5년 전

al.size() / 2가 (최대 크기의 소수) / 2가 아닙니다. 즉, 두 소수 모두 al[al.size() / 2]보다 큰 쪽에서 찾아야 답이 나올 수도 있습니다.

park345601   5년 전

답변감사합니다!

근데 제가 잘 이해가 안되서 그런데

밑에 따온부분에서 for문 안에 있는 al.size에 대해 말씀해주시는건가요?


여기서 al에 해당 값까지의 모든 소수를 집어넣고

al의 인덱스를 이용해서 소수값을 꺼내서하려던건데

al에 들어간 소수들 중에서 중간에 위치한 소수보다 큰 소수들의 합으로도 결과가 나올 수 있다는건가요?

잘 이해가 안됩니다ㅠㅠㅠ

djm03178   5년 전

간단한 예시로 36은 17 + 19로 표현하면 차이가 최소가 되는데, 이 코드는 13 + 23으로 표현합니다. 이 때 al에 들어간 소수들의 목록은 아래와 같은데, al.size() / 2번째 원소인 13은 36의 반에 한참 못 미치는 수입니다. 더 위쪽에서 2개를 고를 수도 있다는 것입니다.

중간 인덱스에 위치한 소수가, 크기의 중간이 아니라는 게 이런 의미입니다.

djm03178   5년 전

참고로 소수는 수가 커질수록 희박해지는 성질이 있기 때문에 중간값은 항상 거의 초반에 머무를 수밖에 없습니다.

park345601   5년 전

아아! 이해에 도움주셔서 감사합니다.

그럼 제가한 코드에서처럼 array list를 이용하면 조금 복잡해질수도 있겠네요?

훨씬 더 간단한 방법이 많을것 같네요..

그리고 array list의 중간지점을 잡고하는게아니라 

주어진 짝수를 반으로 나눈 값을 기준으로 작은 소수값과 큰 소수값의 범위를 넓혀가면서 찾아가면 되겠네요!

djm03178   5년 전

사실 지금의 방법은 많이 비효율적입니다. 첫째로, 최소의 합을 찾을 때는 투 포인터 기법을 사용하면 전체 목록을 한 번 순회하는 것으로 답을 구할 수 있고, 둘째로 소수 목록을 매 쿼리마다 구할 필요 없이 한 번에 구해둘 수 있습니다.

park345601   5년 전

좋은 피드백감사합니다~!

소수 목록은 한번에 만들어 놓고 사용하도록 해보겠습니다.


그리고 투 포인터 알고리즘을 찾아봤는데, 

한 배열에서 (인덱스를 가리키는) 포인터를 두개 두고 각각의 포인터를 조건에 맞게 이동시키면서 배열을 한번만 훑도록 하는건가요?

구글링 자료가 제 이해가 어려워 외국글까지 어찌어찌 봐가면서 이해를 어느정도했는데..


제가 본 코드들을 이해한대로

두 포인터사이 인덱스의 합을 통해 인덱스를 조절하면서 합의 차가 가장 적은 소수값쌍을 구해볼수는 있을것같습니다!

댓글을 작성하려면 로그인해야 합니다.