import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine(), " ");
// ArrayList에 값을 담아줌
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < N; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < M; i++) {
if (list.contains(Integer.parseInt(st.nextToken()))) { // list.contains() 함수를 사용
bw.write("1");
} else {
bw.write("0");
}
bw.write("\n");
}
bw.flush();
bw.close();
br.close();
}
}
[정답코드]
import java.io.*;
import java.util.*;
public class Main {
public static int[] arr;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
arr = new int[N];
st = new StringTokenizer(br.readLine(), " ");
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// 이분탐색은 반드시 정렬이 되어야만 한다.
Arrays.sort(arr);
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < M; i++) {
if (binarySearch(Integer.parseInt(st.nextToken())) >= 0) {
bw.write("1");
} else {
bw.write("0");
}
bw.write("\n");
}
bw.flush();
bw.close();
br.close();
}
public static int binarySearch(int key) {
int low = 0; // 탐색 범위의 왼쪽 끝 인덱스
int high = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스
// low 가 high 보다 커지면 종료
while (low <= high) {
int mid = (low + high) / 2; // 찾는 범위의 중간 값
if (key < arr[mid]) { // key 가 중간값보다 작을 경우
high = mid - 1;
} else if (key > arr[mid]) { // key 가 중간값보다 클 경우
low = mid + 1;
} else { // key 가 중간값과 같을 경우
return mid;
}
}
// 끝까지 탐색했지만 값이 존재하지 않을 경우
return -1;
}
}
[설명]
이 문제는 이분 탐색을 활용하면 풀 수 있는문제다. 하지만 처음에 봤을때 간단하게 보여서 list.contains() 메서드를 활용하면 풀릴것같아서 시도해보았다. 결과는 시간초과가 발생했다.
contains 메서드의 설명을 보면 알 수 있듯이 contains 메서드도 결국에는 리스트의 처음부터 끝까지 탐색하기 때문에 내가 직접 반복문을 시행하나 메서드를 활용하나 별 차이가 없기 때문에 시간초과가 발생했다.
그래서 이분탐색을 활용해 다시 정답을 구해냈다. 코드는 간단해서 설명할것이 없을것 같고 나는 시간복잡도가 궁금해 자료를 검색해봤다.
이러한 일반적인 이분탐색은 거의 대다수가 O(logN) 의 시간 복잡도를 가진다.
N개의 요소를 가진 리스트를 K번 반복한다는 함수를 구한다면 다음과 같다.
운이 좋아 1번만에 찾는다면 (1/2)*N 가 될것이고 3번만에 찾는다면 (1/2)*(1/2)*(1/2)*N 이 될것이다.
운이 안좋아 최악의 경우로 마지막 탐색범위가 1인 경우가 있을수도있다. K번 반복 했을 때 쪼개진 크기가 1이라고 가정한다면, 결국 K번 반복한다고했으니 이를 다음과같이 풀어볼 수 있다.
결국 시간복잡도는 O(logN) 이 되는것이다.
원래 내가 작성했던 코드는 간단히 보자면 이중for문이 되는것이기 때문에 시간복잡도는 O(N^2) 혹은 O(NM)이 된다.
import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < N; i++) {
String word = br.readLine();
if (word.length() >= M) { // 길이 M 이상만 저장
map.put(word, map.getOrDefault(word, 0) + 1); // 같은 단어가 등록될경우 value를 하나씩 증가
}
}
// map 의 value 기준 내림차순 정렬
List<Map.Entry<String, Integer>> entryList = new LinkedList<>(map.entrySet());
entryList.sort(new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
int cmp = o2.getValue().compareTo(o1.getValue()); // value 기준 내림차순 정렬 0일경우 value가 같음
if (cmp == 0) {
int lengthCompare = Integer.compare(o2.getKey().length(), o1.getKey().length()); // value가 같을 경우 value가 같은것 끼리 key의 길이를 내림차순 정렬
return lengthCompare == 0 ? o1.getKey().compareTo(o2.getKey()) : lengthCompare; // key의 길이가 같을경우(lengthCompare == 0일경우) 길이가 같은것은 사전순으로 정렬
}
return cmp;
}
});
for (Map.Entry<String, Integer> entry : entryList) {
bw.write(entry.getKey());
bw.write("\n");
}
bw.flush();
bw.close();
br.close();
}
}
[설명]
이 문제는 맵을 활용한 키와 밸류의 정렬, Comparator를 잘 활용해야하는 문제이다.
먼저 단어를 입력받을때 단어의 길이가 M 이상인 경우만 Map에 저장해준다. 같은 단어가 나올때 해당 단어의 갯수를 map으로 카운팅 해준다.
입력이 끝났다면 map의 Value를 기준으로 내림차순 정렬을 해준다. 그렇다면
// map 의 value 기준 내림차순 정렬
List<Map.Entry<String, Integer>> entryList = new LinkedList<>(map.entrySet());
entryList.sort(new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
int cmp = o2.getValue().compareTo(o1.getValue()); // value 기준 내림차순 정렬 0일경우 value가 같음
return cmp;
}
});
이런식으로 정렬을 해주면 된다.
하지만 문제에서 value 가 같을 경우에는 길이가 긴순으로 재 정렬을 해줘야한다고 되어있다. 그래서 약간 변형해
// map 의 value 기준 내림차순 정렬
List<Map.Entry<String, Integer>> entryList = new LinkedList<>(map.entrySet());
entryList.sort(new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
int cmp = o2.getValue().compareTo(o1.getValue()); // value 기준 내림차순 정렬 0일경우 value가 같음
if (cmp == 0) {
int lengthCompare = Integer.compare(o2.getKey().length(), o1.getKey().length()); // value가 같을 경우 value가 같은것 끼리 key의 길이를 내림차순 정렬
return lengthCompare;
}
return cmp;
}
});
cmp 가 같을 경우에 조건문을 걸어 길이가 긴순으로 내림차순을 해준다.
하지만 문제에 또다른 조건이 있다. 길이마저 같을 경우에는 사전순으로 정렬을 해준다고 되어있다.
// map 의 value 기준 내림차순 정렬
List<Map.Entry<String, Integer>> entryList = new LinkedList<>(map.entrySet());
entryList.sort(new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
int cmp = o2.getValue().compareTo(o1.getValue()); // value 기준 내림차순 정렬 0일경우 value가 같음
if (cmp == 0) {
int lengthCompare = Integer.compare(o2.getKey().length(), o1.getKey().length()); // value가 같을 경우 value가 같은것 끼리 key의 길이를 내림차순 정렬
return lengthCompare == 0 ? o1.getKey().compareTo(o2.getKey()) : lengthCompare; // key의 길이가 같을경우(lengthCompare == 0일경우) 길이가 같은것은 사전순으로 정렬
}
return cmp;
}
});
3항연산자를 사용해 lengthComapre가 같을경우에는 o1.getKey().compareTo(o2.getKey()) 로 비교해사전순으로 정렬해준다.
그리고 마지막 출력을 할 때
for (Map.Entry<String, Integer> entry : entryList) {
System.out.println(entry.getKey());
}
이런식으로 출력을 할 경우 시간초과가 발생한다. 문제설명 맨 마지막에 설명을 보듯 BufferedWriter를 사용해주어야 시간초과가 발생하지 않는다.
