free from
[백준]1253 좋다 본문
문제소개
1253좋다 문제는 투 포인터 알고리즘 문제입니다.
배열에서 다른 두 개의 숫자를 더하여 배열 내의 다른 숫자를 만드는 문제입니다.
예를 들어 (idx:숫자)
아래와 같이 숫자 배열이 있습니다.
| idx | 1 | 2 | 3 | 4 | 5 |
| 숫자 | 0 | -10 | -2 | 4 | 2 |
3: -2와 4: 4를 합하여 5: 2를 만들 수 있습니다.
이렇게 만들 수 있는 숫자의 개수를 구하는 문제입니다. 숫자는 정수인 점을 유의하세요.
문제 풀이
이 문제를 러프(rough)하게 풀면 O(N^3)으로 풀 수 있습니다.
그런데 2000개의 입력값을 가지므로 1초 내에 풀기는 어렵기 때문에
O(N^2)로 풀 수있는 투 포인터 알고리즘으로 풀어야 합니다.
그러니깐 배열을 먼저 정렬해야 합니다.
| idx | 1 | 2 | 3 | 4 | 5 |
| 숫자 | -10 | -2 | 0 | 2 | 4 |
그런 다음 배열 순서대로 진행하면서 해당 숫자를 다른 두 숫자를 더해서 구할 수 있는지를 판별해야 합니다.
이때 다른 두 숫자에 투 포인터 알고리즘을 적용합니다.
예를 들어 4: 2가 좋은 숫자인지 판별해보겠습니다.
1.
| idx | 1 | 2 | 3 | 4 | 5 |
| 숫자 | -10 | -2 | 0 | 2 | 4 |
left = -10 (배열의 시작)
right = 4 (배열의 끝)의 인덱스를 가르킵니다.
음수가 있기 때문에 배열의 시작과 끝에서 시작해야 합니다.
left + right = -6
left + right < find 이므로
left pointer를 += 1 (정렬된 상태이므로)
2.
| idx | 1 | 2 | 3 | 4 | 5 |
| 숫자 | -10 | -2 | 0 | 2 | 4 |
left point = -2
right point = 4
left + right = 2
left + right == find 이므로
4: 2는 좋은 숫자입니다.
좋은 숫자로 판별됬으므로 while문을 종료합니다.
다시 예를 들어 2: -2가 좋은 숫자인지 판별해보겠습니다.
1.
| idx | 1 | 2 | 3 | 4 | 5 |
| 숫자 | -10 | -2 | 0 | 2 | 4 |
left = -10 (배열의 시작)
right = 4 (배열의 끝)의 인덱스를 가르킵니다.
left + right = -6
left + right < find 이므로
left pointer += 1
2.
| idx | 1 | 2 | 3 | 4 | 5 |
| 숫자 | -10 | -2 | 0 | 2 | 4 |
left = -2
right = 4
문제에서 다른 두 수라고 명시 되어 있기 때문에
left pointer는 +=1
3.
| idx | 1 | 2 | 3 | 4 | 5 |
| 숫자 | -10 | -2 | 0 | 2 | 4 |
left = 0
right = 4
left + right = 4
left + right > -2
right pointer -= 1 (정렬되어 있기 때문에)
4.
| idx | 1 | 2 | 3 | 4 | 5 |
| 숫자 | -10 | -2 | 0 | 2 | 4 |
left = 0
right = 2
left + right = 2
left + right > -2
right pointer -= 1
5.
| idx | 1 | 2 | 3 | 4 | 5 |
| 숫자 | -10 | -2 | 0 | 2 | 4 |
left = 0
right = 0
문제에서 다른 두수라고 명시되어 있으므로 left > right 인 경우 while 문을 종료할 수 있습니다.
-2는 좋은 숫자가 아니네요. 다음과 같은 로직으로 1253을 해결할 수 있습니다.
'개발 > 알고리즘' 카테고리의 다른 글
| [백준]1348 주차장 (0) | 2018.12.28 |
|---|---|
| [백준] 1637 날카로운 눈 (0) | 2018.12.26 |
| [백준]7344 나무 막대 (0) | 2018.12.17 |
| [백준]8979 올림픽 (0) | 2018.12.16 |
| [백준] 3108 로고 (0) | 2018.12.15 |
