import java.util.*;
class Solution {
public int[] solution(int[] numbers) {
//더한 값들을 담을 배열 선언
ArrayList<Integer> arr = new ArrayList<>();
//0번부터 number.length-1까지 방문하는 for문
for (int i = 0; i < numbers.length; i++) {
//i번의 다음 순서부터 number.length-1가지 방문하는 for문
for (int j = i+1; j < numbers.length; j++) {
//두 숫자를 더한 값이 arr에 없으면 추가하고 아니면 그냥 넘어가기
int num = numbers[i] + numbers[j];
if (arr.indexOf(num) == -1) arr.add(num);
}
}
//ArrayList 오름차순 정렬
Collections.sort(arr);
//ArrayList를 int[]로 변환하면서 리턴
return arr.stream().mapToInt(Integer::intValue).toArray();
}
}
import java.util.*;
class Solution {
public int solution(String s) {
int answer = 0;
//String으로 다루는 것보다 char로 다루는 것이 시간 차지를 덜 하기 때문에
//s을 char 배열로 만들고 ArrayList에 담기
char[] c = s.toCharArray();
ArrayList<Character> arr = new ArrayList<>();
for (int i = 0; i < c.length; i++) {
arr.add(c[i]);
}
//만약 list의 길이가 홀수일 경우에는 올바른 괄호를 만들 수 없기 때문에 그냥 바로 0 리턴
if (arr.size() % 2 != 0) return 0;
int bracket = arr.size() / 2;
//한 칸씩 한 칸씩 확인하면서 뒤로 넘기기
for (int i = 0; i < arr.size(); i++) {
Stack<Character> stack = new Stack<>();
int count = 0;
for (int j = 0; j < arr.size(); j++) {
char word = arr.get(j);
//만약 닫는 괄호이고,
if (word == ']' || word == '}' || word == ')') {
//스택이 비었다면 탈출
if (stack.empty()) break;
//스택 제일 위의 값이 동일한 모양의 열린 모양이 아니라면 탈출
if (word == ']' && stack.peek() != '[') break;
if (word == '}' && stack.peek() != '{') break;
if (word == ')' && stack.peek() != '(') break;
stack.pop();
count++;
} else { //단어가 열린 괄호라면 스택에 추가
stack.push(word);
}
}
//만약에 만들어진 괄호가 만들 수 있는 괄호 숫자와 동일하다면 답+1
if (count == bracket) answer++;
//맨 앞의 값은 맨 뒤로 추가하고 삭제하기
arr.add(arr.get(0));
arr.remove(0);
}
return answer;
}
}
import java.util.*;
class Solution {
HashMap<String, ArrayList<String>> map;
ArrayList<String> answer;
public int solution(String[] user_id, String[] banned_id) {
map = new HashMap<>(); //banned_id에 해당하는 user_id 검출용
answer = new ArrayList<>(); //만들 수 있는 banned 리스트 제작용
for (int i = 0; i < banned_id.length; i++) {
ArrayList<String> list = map.getOrDefault(banned_id[i], new ArrayList<>());
//만약 map에서 가져온 배열의 길이가 0이 아니면 이미 체크한 banned_id이기 때문에 continue;
if (list.size() != 0) continue;
//user_id와 banned_id[i]를 각각 비교하여 불량 사용자에 해당하는지 파악
for (int j = 0; j < user_id.length; j++) {
if (banned_id[i].length() == user_id[j].length()) {
boolean value = checkWord(user_id[j], banned_id[i]);
if (value) list.add(user_id[j]);
}
}
map.put(banned_id[i], list);
}
create(banned_id, 0, new ArrayList<>());
return answer.size();
}
public void create(String[] key, int index, ArrayList<String> result) {
if (key.length == index) {
//이미 만든 리스트인지 확인하기 위해 오름차순 정렬 후 String화해서 확인하기
Collections.sort(result);
String word = Arrays.toString(result.toArray());
if (answer.indexOf(word) == -1) answer.add(word);
return;
}
ArrayList<String> value = map.get(key[index]);
for (int i = 0; i < value.size(); i++) {
String word = value.get(i);
if (result.indexOf(word) != -1) continue;
ArrayList<String> temp = new ArrayList<>();
temp.addAll(result);
temp.add(word);
create(key, index+1, temp);
}
}
public boolean checkWord(String a, String b) {
//String배열로 비교하면 시간복잡도가 올라가기 때문에 char배열로 비교
char[] alist = a.toCharArray();
char[] blist = b.toCharArray();
for (int i = 0; i < alist.length; i++) {
if (blist[i] != '*' && alist[i] != blist[i]) {
return false;
}
}
return true;
}
}
import java.util.*;
class Solution {
public int[] solution(String[] gems) {
int[] answer = new int[2]; //리턴할 배열 {시작위치, 끝위치}
//보석 개수와 각 보석의 배열 위치를 지정하기 위해 Map 활용
HashMap<String, Integer> names = new HashMap<>();
//만약 names에 해당 보석에 대한 지정된 위치가 없다면 새로 추가하기
for (int i = 0; i < gems.length; i++) {
if (names.getOrDefault(gems[i], 0) == 0) {
names.put(gems[i], names.size() + 1);
}
}
int size = names.size();
//배열 위치 파악하기 위해서
int[] list = new int[size+1];
//구간 파악을 위해서
int count = Integer.MAX_VALUE;
for (int i = 0; i < gems.length; i++) {
//보석 위치에 대한 배열은 i+1로 수정하기
list[names.get(gems[i])] = i+1;
boolean value = true;
//모두 보석이 등장했는지를 파악하기 위한 for문
for (int j = 1; j <= size; j++) {
if (list[j] == 0) {
value = false;
break;
}
}
int min = Integer.MAX_VALUE;
int max = 0;
//모든 보석이 등장했다면 시작 위치와 끝 위치 파악하고,
//만약 구간 길이가 저장된 count 보다 짧다면 answer 리셋
if (value) {
for (int j = 1; j <= size; j++) {
min = Math.min(list[j], min);
max = Math.max(list[j], max);
}
if (max - min < count) {
answer[0] = min;
answer[1] = max;
count = max-min;
}
}
}
return answer;
}
}
import java.util.*;
class Solution {
public String solution(int n, int k, String[] cmd) {
//삭제됬는지 안됬는지를 확인할 배열
boolean[] list = new boolean[n];
//처음에는 모두 있기 때문에 true로 설정함
Arrays.fill(list, true);
//위치 파악을 위한 index 변수 선언
int index = k;
//삭제된 위치들 모을 stack도 선언
Stack<Integer> delete = new Stack<>();
//위로든 아래로든 움직이는 것을 선언할 때마다 움직일 필요가 없고
//삭제나 돌아가기가 호출 될 때 움직임을 모았다가 움직이면 되기 때문에
//따로 모아놓을 변수 선언
int moveCount = 0;
//cmd 순서대로 돌기 위해서 for문
for (int i = 0; i < cmd.length; i++) {
//cmd[i]를 띄어쓰기 기준으로 나눠서 String 배열 만들기
String[] s = cmd[i].split(" ");
//문자 비교를 위해 String으로 하기 보단 char로 하기 위해서 char로 형 변환
char key = s[0].charAt(0);
//움직이는 숫자를 파악하기 위해 만약 s가 1보다 길면 숫자 변환하고 아님 0 넣기
int count = s.length > 1 ? Integer.parseInt(s[1]) : 0;
if (key == 'U') { //만약 U이면 위로 움직여야 하기 때문에 moveCount에선 빼기
moveCount -= count;
} else if (key == 'D') { //만약 D이면 아래로 움직여야 하기 때문에 더하기
moveCount += count;
} else if (key == 'C') { //C이면
//move함수 호출해서 index 위치 움직이기
index = move(list, index, moveCount);
//moveCount는 움직였기 때문에 0으로 리셋
moveCount = 0;
//현 위치인 index를 삭제해야 하기 때문에 false로 변경
list[index] = false;
//삭제된 위치는 스택에 넣기
delete.push(index);
//그리고 현 위치에 있으면 안되고 아래로 한 칸 이동해야 하기 때문에 next함수 호출
index = next(list, index);
} else if (key == 'Z') { //만약 Z이면
//현재 위치 다시 수정하고,
index = move(list, index, moveCount);
moveCount = 0;
//스택에서 제일 마지막에 넣은 값을 꺼내와서
int reset = delete.pop();
//해당 위치의 값 다시 true로 변환
list[reset] = true;
}
}
//String으로 붙이면 시간 많이 잡아 먹어서 StringBuilder로 추가한 후 toString()으로 문자열 변환
StringBuilder sb = new StringBuilder();
for (int i = 0; i < list.length; i++) {
if (list[i]) sb.append("O"); else sb.append("X");
}
return sb.toString();
}
public int next(boolean[] list, int index) {
//일단 아래로 내려가서 삭제되지 않는 값이 있다면 그 위치로 리턴
for (int i = index+1; i < list.length; i++) {
if (list[i]) return i;
}
//아래로 내려가도 리턴되지 않으면 위로 올라가기
for (int i = index-1; i >= 0; i--) {
if (list[i]) return i;
}
return index;
}
public int move(boolean[] list, int index, int num) {
if (num > 0) { //만약 num이 0보다 크면 아래로 내려가야하기 때문에
for (int i = index+1; i < list.length; i++) {
if (num == 0) break;
if (list[i]) num--;
index++;
}
} else {
for (int i = index-1; i >= 0; i--) {
if (num == 0) break;
if (list[i]) num++;
index--;
}
}
return index;
}
}
import java.util.*;
class Solution {
int col, row;
ArrayList<String> arr;
ArrayList<String[]> answer;
public int solution(String[][] relation) {
answer = new ArrayList<>();
col = relation[0].length;
row = relation.length;
arr = new ArrayList<>();
//후보키 조합 만들기
create(0, "");
//길이 기준으로 오름차순 정렬
Collections.sort(arr, new Comparator<String>(){
@Override
public int compare(String a, String b) {
return a.length() - b.length();
}
});
//최소성 확인하고 유일성 확인
for (int i = 0; i < arr.size(); i++) {
String[] s = arr.get(i).split("");
if (check(s)) make(relation, s);
}
return answer.size();
}
//유일성 확인 함수
public void make(String[][] r, String[] s) {
HashMap<String, Integer> m = new HashMap<>();
//글자를 만들면서 중복이 있는지 없는지 파악
for (int i = 0; i < row; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < s.length; j++) {
sb.append(r[i][Integer.parseInt(s[j])]);
}
String str = sb.toString();
if (m.getOrDefault(str, 0) != 0) return;
m.put(str, 1);
}
answer.add(s);
}
//최소성 확인 함수
public boolean check(String[] s) {
List<String> list = Arrays.asList(s);
//answer이랑 비교하면서 answer에 있는 조합이 s에 들어 있는지를 파악함
for (int i = 0; i < answer.size(); i++) {
String[] a = answer.get(i);
if (a.length > s.length) continue;
boolean value = false;
for (int m = 0; m < a.length; m++) {
if (list.indexOf(a[m]) == -1) {
value = true;
break;
}
}
if (!value) return false;
}
return true;
}
public void create(int num, String s) {
for (int i = num; i < col; i++) {
StringBuilder temp = new StringBuilder(s);
temp.append(i);
String str = temp.toString();
arr.add(str);
create(i + 1, str);
}
}
}
import java.util.*;
class Solution {
Point[][] points;
int[][] table;
int n, m;
boolean answer;
public boolean solution(int[][] key, int[][] lock) {
answer = false;
n = key.length;
m = lock.length;
table = new int[m + (n-1)*2][m + (n-1)*2];
int spin = 0;
int start = n-1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (key[i][j] == 1) spin++;
}
}
//돌기가 있는 점들 0도, 90도, 180도, 270도 버전으로 미리 배열에 담아놓기
points = new Point[4][spin];
int position = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (key[i][j] == 1) {
points[0][position] = new Point(i, j);
points[1][position] = new Point(j, n-i-1);
points[2][position] = new Point(n-i-1, n-j-1);
points[3][position] = new Point(n-j-1, i);
position++;
}
}
}
//table은 key가 상하좌우 대각선 모두 다 넣을 수 있도록 범위를 넓힌 상태에서
//lock 부분 체크해놓기
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
table[i+n-1][j+n-1] = lock[i][j];
}
}
//key 넣으면서 체크하기
for (int i = 0; i < table.length - (n-1); i++) {
for (int j = 0; j < table.length - (n-1); j++) {
for (int k = 0; k < 4; k++) {
if (call(i, j, k)) return true;
}
}
}
return false;
}
//만약 func함수 호출 후 answer이 true가 된다면 그냥 바로 리턴하기
public boolean call(int x, int y, int index) {
func(x, y, n-1, index, 0);
if (answer) return true;
return false;
}
public void func(int sX, int sY, int sLock, int index, int num) {
//num과 points[index]의 길이가 같으면 key의 돌기를 다 돈 것이기 때문에
//lock 부분이 전부 1이면 true 아니면 false 리턴
if (num == points[index].length) {
for (int i = sLock; i < sLock+m; i++) {
for (int j = sLock; j < sLock+m; j++) {
if (table[i][j] == 0 || table[i][j] == 2) return;
}
}
answer = true;
return;
}
Point p = points[index][num];
if (table[sX + p.x][sY + p.y] == 0) {
table[sX + p.x][sY + p.y]++;
func(sX, sY, sLock, index, num+1);
table[sX + p.x][sY + p.y]--;
}
}
}
class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}