2866번: 문자열 잘라내기
첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자
www.acmicpc.net
- 풀이
1. 이분탐색을 통해 열의 인덱스 (mid, end) 를 보내줍니다.
2. mid부터 end까지의 중복되는 문자열이 있는지 찾습니다.
3. 문자열이 있다면 right를 mid -1로 초기화 시키며 더 위의 열을 확인해줍니다.
4. 문자열이 없다면 left를 mid+1로 초기화 시키며 더 아래의 열을 확인해줍니다.
5. 2~4의 작업을 반복합니다.
위의 설명대로 구현하였으며, 같은 문자열이 있는지 check해줄 때의 데이터는 순서가 상관없으므로 더 빠른 HashSet을 이용했습니다.
- 코드
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
public class Main {
static int R, C, answer;
static char[][] array;
public static void main(String[] args) throws Exception {
SetData();
System.out.println(answer);
}
// 데이터
private static void SetData() throws Exception {
InputReader in = new InputReader(System.in);
R = in.nextInt();
C = in.nextInt();
array = new char[R][C];
for (int i = 0; i < R; i++) {
String s = in.nextLine();
for (int j = 0; j < C; j++) {
array[i][j] = s.charAt(j);
}
}
binarySearch(1, R - 1, R - 1);
}
private static boolean check(int start, int end) {
Set<String> s = new HashSet<>();
for (int j = 0; j < C; j++) {
String temp = "";
for (int i = start; i <= end; i++)
temp += array[i][j];
if (!s.contains(temp))
s.add(temp);
else
return false;
}
return true;
}
private static void binarySearch(int left, int right, int end) {
while (left <= right) {
int mid = (left + right) / 2;
boolean flag = check(mid, end);
if (flag) {
if (answer < mid)
answer = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
}
}
class InputReader {
private final InputStream stream;
private final byte[] buf = new byte[8192];
private int curChar, snumChars;
public InputReader(InputStream st) {
this.stream = st;
}
public int read() {
if (snumChars == -1)
throw new InputMismatchException();
if (curChar >= snumChars) {
curChar = 0;
try {
snumChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (snumChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public long nextLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public int[] nextIntArray(int n) {
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = nextInt();
}
return a;
}
public String nextLine() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isEndOfLine(c));
return res.toString();
}
public boolean isSpaceChar(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
private boolean isEndOfLine(int c) {
return c == '\n' || c == '\r' || c == -1;
}
}
- 더 빠르고 메모리 적게 잡아먹는 다른 사람 코드
아래의 코드는 arrayList에 이미 모든 열로 이어진 행의 개수를 다 넣은 뒤 subString으로 더 빠르게 확인해 준 방법이다.
방법은 같지만 반복해서 Set에 데이터를 추가해주는 저의 코드에 비해 반복없이 1번만 작업해줌으로서 훨씬 시간을 단축해준 코드입니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int R = Integer.parseInt(st.nextToken());
int C = Integer.parseInt(st.nextToken());
char[][] arr = new char[R][C];
for (int i = 0; i < R; i++) {
arr[i] = br.readLine().toCharArray();
}
ArrayList<String> list = new ArrayList<>();
StringBuilder sb = new StringBuilder("");
for (int i = 0; i < C; i++) {
sb.setLength(0);
for (int j = 0; j < R; j++) {
sb.append(arr[j][i]);
}
list.add(sb.toString());
}
int count = 0, start = 0, end = R;
ArrayList<String> tempList = new ArrayList<>();
while (start <= end) {
tempList.clear();
int mid = (start + end) / 2;
for (int i = 0; i < list.size(); i++) {
String temp = list.get(i);
temp = temp.substring(mid, temp.length());
if (!tempList.contains(temp)) {
tempList.add(temp);
} else {
break;
}
}
if (tempList.size() != list.size()) {
end = mid - 1;
} else {
start = mid + 1;
count = mid;
}
}
System.out.print(count);
}
}'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 5430번 : AC (0) | 2021.09.10 |
|---|---|
| [BOJ/JAVA] 백준 9177번 : 단어 섞기 (0) | 2021.09.08 |
| [BOJ/JAVA] 백준 14725번 : 개미굴 (0) | 2021.09.07 |
| [JAVA] 백준 12015번 : 가장 긴 증가하는 부분 수열 2 (0) | 2021.08.31 |
| [BOJ/JAVA] 백준 2617번 : 구슬 찾기 (0) | 2021.08.27 |
