[BOJ] 2866. 문자열 잘라내기
[작성일]
- 2022-02-10
[분류]
- Set
[문제링크]
[요구사항]
- 맨 윗줄을 지우고 열 문자열끼리 비교해서 같은 값이 없으면 count+1 해주고 있으면 count를 출력하고 종료해라.
[풀이]
한 줄씩 지워가면서 비교를 일일이 처음에는 다 해줄려고 했는데 hashset에 넣어서 비교 시간을 크게 단축할 수 있는 방법이 떠올랐다. 이를 이용해서 한 문자열에 대한 중복검사 로직은 O(1)로 단축할 수 있었다.
1) string을 열로 나누어서 배열로 담는다.
2) 맨 윗줄을 지운다 = 각 문자열마다 맨 앞 글자를 지운다.
3) 지울 때마다 hashSet에 동일한 문자열이 있는지 확인하고 없으면 hashSet에 해당 문자열을 추가해주어서 뒤에 올 문자열들이 비교할 수 있도록 해준다.
4) 동일한 문자열이 있을 경우 loop문을 빠져나와 count를 출력하고 아닐 경우 count+1을 해주고 2)번 과정부터 다시 반복한다.
[코드]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
public class Main {
static int R, C;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
Set<String> set = new HashSet<>();
int count = 0;
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
// C개의 stringbuilder 생성
StringBuilder[] sb = new StringBuilder[C];
for (int i = 0; i < sb.length; i++) {
sb[i] = new StringBuilder();
}
for (int i = 0; i < R; i++) {
String s = br.readLine();
for (int j = 0; j < C; j++) {
sb[j].append(s.charAt(j));
}
}
String[] str = new String[C];
for (int i = 0; i < C; i++) {
str[i] = sb[i].toString();
}
loop:
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
// 1. 맨 위에 문자열을 지운다
str[j] = str[j].substring(1);
// 2-1. 동일한 문자열 발견 시 break
if (set.contains(str[j])) break loop;
else {
// 2-2. 동일한 문자열 검사를 위해 set에 넣어주기
set.add(str[j]);
}
}
// 검사 통과 시 count++
count++;
// 메모리가 쌓이는 것을 막기위해 set 초기화
set.clear();
}
System.out.println(count);
}
}
[통과여부]
[느낀점]
중복검사를 해야한다면 항상 set 자료구조를 사용하는 것을 염두해야겠다!
Author And Source
이 문제에 관하여([BOJ] 2866. 문자열 잘라내기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hyodonglee/BOJ-2866.-문자열-잘라내기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)