[17609] 회문
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 (추가 시간 없음) | 512 MB | 31555 | 8988 | 6634 | 29.094% |
문제
회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.
여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다.
입력
입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.
출력
각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.
문제풀이
이 문제는 주어진 문자열이 회문인지, 유사회문인지, 그 외의 일반 문자열인지 확인하는 문제이다.
여기서 유사회문이란, 회문은 아니지만 한 문자를 삭제하였을 때 회문이 되는 문자열이다.
회문은 예전에 완전탐색방법으로 풀이를 한 적이 있다.
public static boolean isPalindrome(int[] digit) {
for (int i = 0; i < digit.length / 2; i++)
if (digit[i] != digit[digit.length - i - 1)
return false;
return true;
}
그렇다면 유사회문은 어떻게 찾을 수 있을까?
아래 그림은 유사회문인 경우이다.
값이 달라지는 전까지 비교해보면 i는 2까지 j는 6까지 같은 수 이다.
양끝에서 회문을 확인하고 있는 중에 다른 문자가 등장했다면 둘 중 하나를 제거해 유사회문이 될 수 있다.
이렇게 아래 이미지를 보면 X혹은 Y값을 제외하고 회문인 경우이면 유사회문이다.
즉, 양끝에서 연속적인 회문[0:X-1], [Y+1:S-1]을 경계로 두가지가 있다.
1. 주어진 문자열이 회문이라면 0
일단 문자열이 회문인지 판단하는 코드를 작성해보자.
투 포인터를 이용하여 탐색을 할 것이다.
아래 조건문에 들어가지 않는 경우는 회문인 경우이다.
int ans = 0;
while(l <= r) {
if (s[l] != s[r]) {
}
}
2. 주어진 문자열이 유사회문이라면 1
3. 회문도 유사회문도 아닌 경우라면 일반 문자열이므로 2
isPaliindrome 함수를 만들어 유사회문인 경우를 찾아보자. 유사회문이라면 ans는 1이 될 것 이고, 일반 문자열이라면 2를 출력한다.
// 2. 주어진 문자열이 유사회문이라면 1
if (isPaliindrome(s, l, r - 1) || isPaliindrome(s, l + 1, r)) ans = 1;
// 3. 회문도 유사회문도 아닌 경우라면 일반 문자열이므로 2
else ans = 2;
4. 문자열이 유사회문인지 찾는 함수
static boolean isPaliindrome(char[] s, int l, int r) {
while( l <= r ) {
if (s[l] != s[r]) return false;
l++;
r--;
}
return true;
}
전체코드
import java.util.Scanner;
class Main {
static boolean isPaliindrome(char[] s, int l, int r) {
while( l <= r ) {
if (s[l] != s[r]) return false;
l++;
r--;
}
return true;
}
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while(T-->0) {
char[] s = sc.next().toCharArray();
int l = 0;
int r = s.length - 1;
// 1. 주어진 문자열이 회문이라면 0
int ans = 0;
while(l <= r) {
if (s[l] != s[r] ) {
// 2. 주어진 문자열이 유사회문이라면 1
if (isPaliindrome(s, l, r - 1) || isPaliindrome(s, l + 1, r)) ans = 1;
// 3. 회문도 유사회문도 아닌 경우라면 일반 문자열이므로 2
else ans = 2;
break;
}
l++;
r--;
}
System.out.println(ans);
}
}
}
시간복잡도
이 알고리즘의 **시간복잡도는 O(T * |S|)**이다. T번 입력을 받고 T번 만큼 S를 순회해야 한다.
[15831] 준표의 조약돌
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 512 MB | 1996 | 763 | 593 | 37.891% |
문제
그림1. 준표가 좋아하는 하얀색의 미미
준표는 오랜만에 미미와 함께 산책을 나왔다. 산책로에는 일렬로 검은색과 흰색 조약돌이 놓여 있다. 총 N개의 조약돌은 1번부터 N번까지 차례로 번호가 붙여져 있다. 준표는 이 조약돌을 주워 집에 장식하려고 한다.
준표는 임의의 지점에서 산책을 시작하고, 원하는 지점에서 산책로를 빠져나와 집으로 돌아간다. 이때 준표는 산책한 구간에 있는 모든 조약돌을 줍는다. 미미의 건강을 위해 준표는 조금이라도 더 긴 구간을 산책하고 싶다. 하지만 준표에게는 확고한 취향이 있어, 아래 조건을 만족하는 구간만을 산책할 수 있다.
- 준표는 까만색을 싫어한다. 그래서 까만색 조약돌은 B개 이하로 줍고 싶다.
- 준표는 미미와 같은 흰색을 좋아한다. 그래서 흰색 조약돌은 W개 이상 줍고 싶다.
만약 위 조건을 만족하는 구간이 없다면 준표는 바로 집으로 돌아간다. 이때 준표와 미미가 산책할 수 있는 구간 중 가장 긴 구간의 길이를 구해보자.
입력
첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조약돌은 검은색이고, W라면 흰색이다.
출력
준표와 미미가 걷게 될 가장 긴 구간의 길이를 한 줄에 출력한다. 준표가 원하는 조건에 맞는 구간이 없다면 0을 출력한다.
Small (100점)
- 1 ≤ N ≤ 3,000
- 0 ≤ B, W, B+W ≤ N
Large (150점)
- 1 ≤ N ≤ 300,000
- 0 ≤ B, W, B+W ≤ N
문제풀이
이 문제는 N개의 조약돌 중 아래 조건을 만족하는 가장 긴 연속 구간의 길이를 구하는 문제다.
- 구간의 까만색 조약돌은 B개 이하여야 한다.
- 구간의 하얀색 조약돌은 W개 이상이어야 한다.
그렇다면 누적합을 사용해서 문제를 풀 수 있다.
다만 아래 방법으로 문제를 풀면 시간복잡도가 O(N^2)이 될 것이다.
// 누적합 계산
for (int i = 1; i <= N; i++) {
accBlack[i] = accBlack[i - 1] + (stones.charAt(i - 1) == 'B' ? 1 : 0);
accWhite[i] = accWhite[i - 1] + (stones.charAt(i - 1) == 'W' ? 1 : 0);
}
int ans = 0;
// 모든 구간을 탐색
for (int i = 1; i <= N; i++) {
for (int j = i; j <= N; j++) {
int countBlack = accBlack[j] - accBlack[i - 1];
int countWhite = accWhite[j] - accWhite[i - 1];
// 조건 확인
if (countBlack <= B && countWhite >= W) {
ans = Math.max(ans, j - i + 1); // 최대 길이 업데이트
}
}
}
그러면 한 번 제출해보자.
Small 케이스만 통과되어 100점을 받는 것을 볼 수 있다.
투 포인터 풀이
아래 이미지를 보면 i를 3에서 시작하고 j를 7에서 끝나게 되는데 검은색: 1개, 흰색: 4개이다.
즉, 각 시작점 i에 대해 검은색이 B개 이하이면서 흰 색이 W이상이 되는 가장 긴 구간 j를 찾는다.
1. 현재 위치가 W이면 흰색 개수 추가 반대이면 검은색 개수 추가
while (nextIndex < N) {
if (currentBlackCount == B && color[nextIndex] == 'B') break;
if (color[nextIndex++] == 'W') currentWhiteCount++;
else currentBlackCount++;
}
2. 현재 흰색의 개수가 W이상이면 ans보다 크면 업데이트
if (currentWhiteCount >= W)
ansLength = Math.max(ansLength, nextIndex - i);
3. i 번째 돌은 다음 구간에서 제외
if (color[i] == 'W') currentWhiteCount--;
else currentBlackCount--;
전체코드
import java.util.Scanner;
class Main
{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int B = sc.nextInt();
int W = sc.nextInt();
char[] color = sc.next().toCharArray();
int currentWhiteCount = 0;
int currentBlackCount = 0;
int ansLength = 0;
int nextIndex = 0;
for (int i = 0; i < N; i++) {
while (nextIndex < N) {
if (currentBlackCount == B && color[nextIndex] == 'B') break;
if (color[nextIndex++] == 'W') currentWhiteCount++;
else currentBlackCount++;
}
if (currentWhiteCount >= W)
ansLength = Math.max(ansLength, nextIndex - i);
if (color[i] == 'W') currentWhiteCount--;
else currentBlackCount--;
}
System.out.println(ansLength);
}
}
시간복잡도
이 알고리즘의 시간복잡도는 O(N) 이다.
'알고리즘 > Two Pointer' 카테고리의 다른 글
| [코딩테스트] [16472] 고냥이 (1) | 2025.01.03 |
|---|---|
| [코딩테스트] [11728] 배열 합치기 (0) | 2024.12.30 |
| [코딩테스트] [12891] DNA비밀번호 & [2118] 두개의탑 (0) | 2024.12.29 |
| [코딩테스트] [2230] 수 고르기 (0) | 2024.12.26 |
| [코딩테스트] [Two Pointer] [2003] 수들의 합 2 & [1806] 부분합 (0) | 2024.12.24 |