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

 

2607번: 비슷한 단어

첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이

www.acmicpc.net

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

 

풀이

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

 

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

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

 

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

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

 

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

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

 

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

 

정답 코드

'Problem Solving > BOJ' 카테고리의 다른 글

[1544] 사이클 단어  (0) 2023.01.30
[1263] 시간 관리  (0) 2023.01.29
[6503] 망가진 키보드  (0) 2023.01.24
[15831] 준표의 조약돌  (0) 2023.01.23
[12892] 생일 선물  (0) 2023.01.21

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

 

6503번: 망가진 키보드

입력은 여러 개의 테스트 케이스로 이루어져 있고, 각 테스트 케이스는 두 줄로 이루어져 있다. 테스트 케이스의 첫째 줄에는 m이 주어진다. (1 ≤ m ≤ 128) 둘째 줄에는 상근이가 입력하려고 하는

www.acmicpc.net

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

 

풀이

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

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

 

정답 코드

'Problem Solving > BOJ' 카테고리의 다른 글

[1263] 시간 관리  (0) 2023.01.29
[2607] 비슷한 단어  (2) 2023.01.27
[15831] 준표의 조약돌  (0) 2023.01.23
[12892] 생일 선물  (0) 2023.01.21
[6137] 문자열 생성  (0) 2023.01.20

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

 

15831번: 준표의 조약돌

첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조

www.acmicpc.net

투 포인터 문제다. 

 

풀이

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

 

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

 

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

 

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

 

정답 코드

'Problem Solving > BOJ' 카테고리의 다른 글

[2607] 비슷한 단어  (2) 2023.01.27
[6503] 망가진 키보드  (0) 2023.01.24
[12892] 생일 선물  (0) 2023.01.21
[6137] 문자열 생성  (0) 2023.01.20
[22862] 가장 긴 짝수 연속한 부분 수열 (large)  (0) 2023.01.19

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

 

12892번: 생일 선물

첫 줄에 친구의 수 N(1 ≤ N ≤ 100,000)과 미안함을 느끼게 되는 최소가격차 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 선물의 가격 P와 만족도 V(0 ≤ P ≤ 1,000,000,000, 0

www.acmicpc.net

투 포인터 문제다.

 

풀이

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

 

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

 

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

 

정답 코드

'Problem Solving > BOJ' 카테고리의 다른 글

[6503] 망가진 키보드  (0) 2023.01.24
[15831] 준표의 조약돌  (0) 2023.01.23
[6137] 문자열 생성  (0) 2023.01.20
[22862] 가장 긴 짝수 연속한 부분 수열 (large)  (0) 2023.01.19
[1484] 다이어트  (0) 2023.01.18

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

 

6137번: 문자열 생성

첫 번째 줄에 문자열 S의 길이 N이 주어진다. (N <= 2,000) 이후 N개의 줄에 S를 이루는 문자들이 주어진다.

www.acmicpc.net

투포인터 문제다.

 

풀이

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

 

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

 

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

 

정답 코드

'Problem Solving > BOJ' 카테고리의 다른 글

[15831] 준표의 조약돌  (0) 2023.01.23
[12892] 생일 선물  (0) 2023.01.21
[22862] 가장 긴 짝수 연속한 부분 수열 (large)  (0) 2023.01.19
[1484] 다이어트  (0) 2023.01.18
[2118] 두 개의 탑  (0) 2023.01.17

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

 

22862번: 가장 긴 짝수 연속한 부분 수열 (large)

수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

www.acmicpc.net

투포인터 문제다.

 

풀이

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

 

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

 

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

 

정답 코드

해당 문제는 같은 문제지만 수열의 크기 범위만 더 좁은 22857 문제에서도 정답을 받을 수 있다.

'Problem Solving > BOJ' 카테고리의 다른 글

[12892] 생일 선물  (0) 2023.01.21
[6137] 문자열 생성  (0) 2023.01.20
[1484] 다이어트  (0) 2023.01.18
[2118] 두 개의 탑  (0) 2023.01.17
[1652] 누울 자리를 찾아라  (0) 2023.01.16

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

 

1484번: 다이어트

성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다.

www.acmicpc.net

투포인터 문제다.

 

풀이

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

정답 코드

'Problem Solving > BOJ' 카테고리의 다른 글

[6137] 문자열 생성  (0) 2023.01.20
[22862] 가장 긴 짝수 연속한 부분 수열 (large)  (0) 2023.01.19
[2118] 두 개의 탑  (0) 2023.01.17
[1652] 누울 자리를 찾아라  (0) 2023.01.16
[15565] 귀여운 라이언  (0) 2023.01.15

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

 

2118번: 두 개의 탑

첫째 줄에 지점의 개수 N(2 ≤ N ≤ 50,000)이 주어진다. 다음 N개의 줄에는 차례로 두 지점 사이의 거리가 양의 정수로 주어진다. 전체 거리의 총 합은 1,000,000,000을 넘지 않는다.

www.acmicpc.net

투포인터 문제다.

 

풀이

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

 

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

 

정답 코드

'Problem Solving > BOJ' 카테고리의 다른 글

[22862] 가장 긴 짝수 연속한 부분 수열 (large)  (0) 2023.01.19
[1484] 다이어트  (0) 2023.01.18
[1652] 누울 자리를 찾아라  (0) 2023.01.16
[15565] 귀여운 라이언  (0) 2023.01.15
[1337] 올바른 배열  (0) 2023.01.14

+ Recent posts