Hyun's_Devlog

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

투 포인터 문제다. 출력 횟수가 많으므로 스위프트의 경우 출력을 한 번에 몰아서 해야 시간초과를 받지 않는다.

풀이

문자열 키와 정수형 값을 가지는 딕셔너리를 활용했다. 투포인터를 통해 입력 텍스트를 탐색하면서 딕셔너리의 크기가 n 미만이라면 tail이 가리키는 글자를 추가. n이상이라면 tail이 가리키는 글자가 딕셔너리에 있는 글자인지 확인. 있는 글자라면 해당하는 딕셔너리의 값과 tail 증가. 없는 글자라면 head가 가리키는 글자를 키로 가지는 딕셔너리의 값을 감소시킨다. 이후 head를 증가시킨다.

매 반복문마다 딕셔너리의 크기가 n 이하라면 tail - head의 값으로 최댓값을 갱신한다.

정답 코드

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

투 포인터 문제다. 

풀이

범위의 시작 인덱스를 담은 head 변수와 끝 인덱스를 담은 tail 변수를 생성. 다음과 같은 동작들을 tail이 n이 될 때까지 반복한다.

현재 tail이 가리키는 조약돌이 검은 돌이고 들고 있는 검은 돌의 개수가 B개 미만이라면, 더 들고 갈 수 있는 상태이므로 가져가야 할 돌로 포함시키고 tail을 증가시킨다.

현재 tail이 가리키는 조약돌이 검은 돌이고 들고 있는 검은 돌의 개수가 B개 이상이라면, 더 이상 들고 갈 수 없으므로 head가 가리키는 조약돌을 버리고 head를 증가시킨다.

현재 tail이 가리키는 조약돌이 흰돌이라면 가져가야 할 돌로 포함시키고 tail을 증가시킨다. 매 탐색마다 주운 조약돌의 개수가 준표의 조건에 맞다면 출력값을 최대길이로 갱신한다.

정답 코드

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

투 포인터 문제다.

풀이

입력받은 P와 V를 pair로 생성하여 배열에 담는다. N이 100,000이기에 P를 기준으로 오름차순 정렬한 뒤 탐색을 시작해도 시간초과가 일어나지 않는다.

tail과 head가 가리키는 P의 차이가 D보다 작다면, 더 많은 선물을 받을 수 있다는 얘기이므로 선물의 범위를 늘리기 위해 tail을 증가시킨 후 tail이 가리키는 만족도 V를 추가하여 더 큰 값으로 갱신한다.

만일 P의 간격이 D이상이라면, 선물을 받을 수 없는 상황이다. head가 가리키는 만족도 V를 뺀 후 head를 증가시켜 선물을 받는 범위를 좁힌다. tail이 N에 도달하면 반복문을 종료한다.

정답 코드

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

투포인터 문제다.

풀이

시작을 나타내는 인덱스 head, 끝을 나타내는 인덱스 tail을 생성하여 각각 0과 n-1을 부여. (head <= tail)인 순간까지 문자열 S를 탐색한다. 매 반복문마다 더 먼저 오는 문자를 출력할 문자열에 더해주고 해당 인덱스를 증가시킨다.

head와 tail이 가리키는 문자가 같다면, head ~ tail 범위의 문자열과 역순의 문자열을 비교하여 순서가 먼저인 문자열 측의 문자를 추가하면 된다.

80자마다 줄 바꿈 "\n"을 출력해야 한다는 점을 잊지 말자. 본인의 경우 문자열에 "\n"을 추가한 뒤 마지막에 한 번에 출력하게끔 코드를 작성했는데, "\n" 문자열도 포함돼서 카운트하는 바람에 오답판정을 받았다.

정답 코드

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

투포인터 문제다.

풀이

짝수가 연속된 수열에서 k번의 삭제를 할 수 있다는 얘기는 최대 k개의 홀수가 담긴 배열의 크기를 찾는 것과 같은 이야기다. 구간의 범위를 나타내는 head와 tail 변수를 사용하여 탐색한다.

구간 안에 홀수가 k개 이하라면 tail을 증가시켜 구간을 늘린다. 매 탐색마다 구간의 크기는 (tail - head - 홀수의 개수)가 된다. 해당 부분의 최댓값을 출력하면 정답이다.

구간의 범위를 나타내는 head와 tail 변수를 사용하여 범위를 탐색, 구간 안에 홀수가 k개를 초과한다면, head를 증가시켜 구간을 축소시켜 홀수의 개수를 조절한다. tail이 이미 N이라면, 더 이상 증가시킬 수 없다는 뜻이므로 반복문 종료.

정답 코드

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

투포인터 문제다.

풀이

두 제곱수간의 차가 G를 만족하는 쌍을 찾아내면 된다. G의 값이 최대 100,000이므로 제곱수를 담은 크기 100,000의 배열을 생성한 후, head와 tail인덱스를 생성하여 인덱스 간 차이를 계산, G보다 작다면 tail을 증가, G이상이라면 head를 증가시켜 차이를 조절하며 탐색한다. 둘의 차가 G라면 tail의 값을 정답으로 출력하면 된다. 그림으로 보면 더 이해하기 쉽다. 정답이 없다면 -1을 출력하는 것도 까먹지 말자.

정답 코드

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

투포인터 문제다.

풀이

문제에 주어지는 두 지점사이의 거리는 시계방향과 반시계 방향 중 짧은 쪽이 거리가 된다고 한다. 즉 시계방향 기준 반시계 방향 거리라 함은 (전체 길이 - 시계방향 거리) 로 계산이 가능하며 해당 지점의 거리는 둘 중 적은 거리로 정해진다는 것이다.

시작 인덱스와 끝 인덱스를 생성하여 구간의 길이를 측정한다. 구간의 길이가 최대거리보다 짧거나 같다면, 끝 인덱스를 한칸 늘린다. 반대로 현재 구간의 길이가 최대값보다 크다면, 시작 인덱스를 증가한다. 

정답 코드

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

기본적인 투포인터 문제다.

풀이

head, tail 두 개의 인덱스를 담는 변수와 인형의 개수를 담는 변수를 통해 조건을 판별한다. 개수가 k이상이라면, head를 증가 k보다 작다면 tail을 증가한다. 각 조건마다 head와 tail인덱스에 1이 담겨있는지 확인하여 개수를 갱신한다. 

개수가 k보다 적고, tail이 이미 n이라면, 더 이상 k개의 인형이 없다는 뜻이므로 반복문을 종료한다.

전체를 탐색했는데도 k개의 인형이 없다면 -1을 출력해야 한다는 조건도 까먹지 말자.

정답 코드