Hyun's_Devlog

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

기본적인 그리디 문제다. 오래전에 오답판정을 받고서 이번에 다시 풀어보았다. 사소한 부분을 놓친 거라 원인을 알고 나서 허탈했다.

풀이

현실에서의 시간은 24시간이지만, 문제에서 주어지는 시간의 최댓값은 1,000,000이다. 오답의 원인도 해당 부분을 꼼꼼히 보지 않아서 생긴 것이다. 정답으로 출력할 time변수를 시작시간의 최댓값 1,000,000으로 설정한다.

입력되는 일들을 마감시간을 기준으로 내림차순으로 정렬한 뒤, 시작시간이 마감시간보다 뒤에 있다면 시작시간을 (마감시간 - 작업시간)으로 변경한다.

만일 시작시간이 마감시간보다 앞에 있다면 작업시간만큼 앞당긴다.(빼준다.) 마지막으로 정답을 출력할 때, 시작시간이 음수라면, -1을 출력한다.

정답 코드

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

문자열과 연관된 구현문제다.

풀이

비슷한 단어의 판별은 문자열의 길이에 따라 총 3가지 경우가 나온다. 

1. 기준 문자열의 길이와 입력된 문자열의 길이가 같은 경우

구성요소가 완전히 똑같거나 하나 틀린 경우 비슷한 단어로 판별한다.

2. 기준 문자열의 길이가 입력된 문자열의 길이보다 하나 긴 경우

입력된 문자열의 구성요소가 기준 문자열의 구성요소에 완전히 포함되거나, 하나의 구성요소가 다를 경우에 비슷한 단어로 판별한다.

3. 기준 문자열의 길이가 입력된 문자열의 길이보다 하나 짧은 경우

기준 문자열의 구성요소가 입력된 문자열의 구성요소에 완전히 포함된 경우에만 비슷한 단어로 판별한다.

구성요소의 판별의 경우 입력되는 문자가 대문자로 한정되어 있어 26개의 배열을 생성하여 해당 요소에 해당하는 인덱스에 개수를 저장하여 계산하였다.

정답 코드

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을 출력하는 것도 까먹지 말자.

정답 코드