Hyun's_Devlog

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/1652

간단한 문자열 탐색 문제다. 문제를 이해하는 시간이 더 길었던 문제다.

풀이

문제에 대한 설명이 부실하다고 생각되지만, 내 문해력이 부족한 것이라고 생각해야겠다. 예제를 그림으로 설명하면 다음과 같다.

즉 두 칸 이상의 공간이 생기면 해당공간을 하나의 누울 자리로 취급하겠다는 이야기. 

주의해야 할 사항으로 자리는 벽과 짐으로 구분한다는 것을 잊지 말아야 한다.

입력되는 문자열을 기준으로 가로배열과 세로배열을 생성. 두 배열을 "X"문자열을 기준으로 split() 함수를 통해 빈 공간을 탐색하였다.

정답 코드

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

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

풀이

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

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

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

정답 코드

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

투 포인터로 접근한 문제다.

풀이

기준이 될 인덱스 i는 1부터 n까지, 비교할 인덱스 k는 i+1부터 i+4까지 반복문을 수행. 둘의 차이가 5보다 작다면 올바른 배열로 판정한다.

기준 인덱스 i가 바뀔 때마다 최댓값을 갱신한 뒤, 반복문이 끝나고 나면 값을 출력하면 된다.

정답 코드

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

투 포인터, 슬라이딩 윈도우로 접근한 문제다.

풀이

투 포인터를 사용하여 곰이 얼음에 닿을 수 있는 최대거리 (2*k+1) 범위의 얼음합을 좌표값 0부터 1000,000까지 탐색을 하면 된다. 단 k의 크기가 500,000을 넘는다면 모든 좌표에 있는 얼음을 가져올 수 있으므로, 입력을 받으면서 얼음의 최댓값을 미리 계산하여 출력하면 된다.

정답 코드

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

투포인터 문제다. 간단한 문제라고 생각하고서 접근했지만, 약간의 시간이 걸린 문제다.

풀이

head와 tail 두 개의 변수에 구간 합의 시작 인덱스와 끝 인덱스를 할당. 처음에는 둘 다 0으로 시작한다. 주어지는 수는 무조건 자연수다. 그 이야기는 해당 구간의 합이 k보다 크다면, 그 이후의 구간은 모두 조건을 만족한다는 뜻이다. 조건이 맞는다면 tail에 해당하는 인덱스부터 n까지의 개수를 모두 더해준 뒤, head 인덱스를 증가하여 다시 조건을 탐색. 이런 방법으로 구간을 탐색한다.

만일 sum이 k보다 작고, tail이 더 이상 증가할 수 없는 상황이라면, 반복문을 종료하면 된다.  

정답 코드

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

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

풀이

1부터 N까지의 수를 오름차순으로 담은 배열을 생성한 뒤, 인덱스를 활용한 구간탐색을 통해 답을 구하면 된다. 시작 인덱스와 끝인덱스는 동일하게 0으로 시작한 뒤, 아래와 같은 조건으로 반복을 수행한다.

• 누적합이 목표 숫자보다 크다면 시작 인덱스가 가리키는 숫자를 뺀 뒤 시작 인덱스 증가
• 누적합이 목표 숫자보다 작거나 같다면 끝 인덱스가 가리키는 숫자를 더 해준 뒤 끝 인덱스 증가
• 누적합이 목표숫자와 같다면 카운트 증가
• 끝 인덱스가 증가할 부분이 없다면 종료

정답코드