투 포인터(JAVA)

수들의 합5(백준 2018번)

https://www.acmicpc.net/problem/2018

2018번: 수들의 합 5

문제 설명

이 문제는 입력값 N을 몇 개의 연속된 자연수의 합으로 나타낼 수 있는지 구하는 것이다.

예를 들어 15를 입력 받으면 7+8, 4+5+6, 1+2+3+4+5, 15 이렇게 4가지 이다. 

 

문제에 대한 아이디어

투 포인터를 이용해서 풀어 나가는 대표적인 문제이다. start_idx 와 end_idx가 둘 다 처음 1에서 부터 시작한다. end_idx를 하나씩 올리면서 N과 같아질 때 까지 반복한다. 이러면 3가지의 경우가 생긴다. 

• 합이 N 보다 작을 경우 :  end_idx++, sum += end_idx;
• 합이 N 보다 클 경우 : sum -= start_idx, start_idx++
• 합이 N과 같을 경우 : ++count, ++end_idx, sum += end_idx (합이 같은 경우로 현재 end_idx 부분을 검사하였으므로 end_idx를 하나 올린다)

 

전체 코드

https://github.com/Heron-Woong/CodingTest_Practice/blob/main/%EB%B0%B1%EC%A4%80_2018.java

GitHub - Heron-Woong/CodingTest_Practice

 

좋다(백준 1253번)

https://www.acmicpc.net/problem/1253

1253번: 좋다

문제 설명

N개의 숫자가 정해지면 각 숫자가 나머지 숫자의 합으로 나타낼 수 있는지 검사 하는 것이다.

1 2 3 4 5 6 7 8 9 10이 있으면 3은 1과 2를 더함으로 써 나타낼 수 있으므로 좋은 수이다.

 

문제에 대한 아이디어

입력 값은 최대 2000이다. 일단 N개의 수를 모두 검사해야 하니 N시간은 무조건 필요하다. 거기에 좋은 수를 찾는 알고리즘은 N 제곱보다 무조건 작아야 2초 안에 풀 수가 있다. O(nlogn)안에 좋은 수를 찾아야 한다는 것을 알 수 있다.

투포인터와 정렬로 풀 수 있다.

정렬로 배열을 세팅 한 뒤, start_idx는 제일 처음 end_idx는 제일 마지막으로 설정한다. i는 처음부터 끝까지 한번 도는 인덱스이다.

• 합이 arr[i] 보다 작을 경우 :  더 큰 수를 더해야 하므로 start_idx++ 한다.
• 합이 arr[i] 보다 클 경우 : 더 작은 수를 더해야 하므로 end_idx--한다.
• 합이 arr[i]과 같을 경우 : count를 올려야 한다. 여기서 중요한 점은 start_idx와 end_idx가 i와 같아서는 안된다는 것이다. 문제에서 어떤 수가 다른 수 두개의 합으로 나타낼 수 있다 했으므로 자기 자신은 자기 자신을 구하는데에 쓰이면 안된다.

 

전체 코드

https://github.com/Heron-Woong/CodingTest_Practice/blob/main/%EB%B0%B1%EC%A4%80_1253.java

GitHub - Heron-Woong/CodingTest_Practice