This is a auto push repository for Baekjoon Online Judge created with [BaekjoonHub](https://github.com/BaekjoonHub/BaekjoonHub).
This is a auto push repository for Baekjoon Online Judge created with BaekjoonHub.
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> list = new ArrayList<>();
Comparator<int[]> myComparator = new Comparator<>(){
@Override
public int compare(int[] o1, int[] o2){
// 시작 오름차순
return o1[0]-o2[0];
}
};
Arrays.sort(intervals,myComparator);
int start = intervals[0][0];
int end = intervals[0][1];
for(int[] interval : intervals){
int s = interval[0];
int e = interval[1];
if(s<=end){
end = end > e? end: e;
}else{
list.add(new int[]{start,end});
start = s;
end = e;
}
}
// last element
list.add(new int[]{start,end});
int size = list.size();
int[][] result = new int[size][2];
for(int i = 0 ; i<size;i++){
result[i][0] = list.get(i)[0];
result[i][1] = list.get(i)[1];
}
return result;
}
}
public int findPeakElement(int[] nums) {
// O(N)
int answer = 0;
for(int i = 1; i<nums.length-1;i++){
int prev = nums[i-1];
int next = nums[i+1];
int cur = nums[i];
if(cur>prev && cur>next){
answer = i;
break;
}
}
return answer;
} class Solution {
public int findPeakElement(int[] nums) {
// nums 길이 1000
// O(logN)
// 양옆보다 큰 index 찾기
int N = nums.length;
// element가 1개인 경우
if(N==1){
return 0;
}
// 맨 왼쪽이 봉우리인 경우
if(nums[0]>nums[1]){
return 0;
}
// 맨 오른쪽이 봉우리인 경우
if( nums[N-1]>nums[N-2]){
return N-1;
}
int lo = 1;
int hi = nums.length-2;
int answer = 0;
while(lo<=hi){
int m = (lo+hi)/2;
if(nums[m]>nums[m-1]&& nums[m]>nums[m+1]){
answer = m;
break;
}
else if(nums[m]<nums[m-1]){
hi = m-1;
}else if(nums[m]<nums[m+1]){
lo = m+1;
}
}
return answer;
}
} void preOrder(TreeNode cur, Stack<TreeNode> S) {
if (cur == null) {
return;
}
S.add(cur);
preOrder(cur.left, S);
preOrder(cur.right, S);
}class Solution {
void preOrder(TreeNode cur,List<TreeNode> list){
if(cur==null){
return;
}
list.add(cur);
preOrder(cur.left,list);
preOrder(cur.right,list);
}
public void flatten(TreeNode root) {
List<TreeNode> list= new ArrayList<>();
// preOrder 진행
preOrder(root,list);
// List (1,2,3,4,5,6) 으로 담겨 있음
TreeNode prev = null;
for(TreeNode cur : list){
cur.left = null;
cur.right = null;
if(prev!=null){
prev.right = cur;
}
prev = cur;
}
}
}
// good pair
// i - j == nums[i] - nums[j]
// i - nums[i] == j - nums[j]
class Solution {
public long countBadPairs(int[] nums) {
int N = nums.length;
int[] diff = new int[N];
for(int i = 0 ; i< N; i++){
diff[i] = nums[i] - i;
}
// good pair
// i - j == nums[i] - nums[j]
// i - nums[i] == j - nums[j]
long tot = (long) N * (N - 1) / 2;
long goodCnt = 0;
HashMap<Integer, Integer> hm = new HashMap<>();
for (int i = 0; i < N; i++) {
if (hm.containsKey(diff[i])) {
goodCnt += hm.get(diff[i]);
}
hm.put(diff[i], hm.getOrDefault(diff[i], 0) + 1);
}
return tot - goodCnt;
}
}
// 콜라츠 추측으로 우박수열 그래프 만들기
public int[] getHeight(int k) {
List<Integer> graph = new ArrayList<>();
while (k > 1) {
graph.add(k);
if (k % 2 == 0) {
k = k / 2;
} else {
k = k * 3 + 1;
}
}
// 마지막에 1 추가
graph.add(1);
// list -> arr 변환
return graph.stream().mapToInt(i -> i).toArray();
}
// 사다리꼴 넓이 구하기
double[] area = new double[cnt + 1];
for (int i = 1; i <= cnt; i++) {
area[i] = (double) (height[i - 1] + height[i]) / 2;
}
// 누적합 구하기
double[] dp = new double[cnt + 1];
for (int i = 1; i <= cnt; i++) {
dp[i] = dp[i - 1] + area[i];
}import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
// 콜라츠 추측으로 우박수열 그래프 만들기
public int[] getHeight(int k) {
List<Integer> graph = new ArrayList<>();
while (k > 1) {
graph.add(k);
if (k % 2 == 0) {
k = k / 2;
} else {
k = k * 3 + 1;
}
}
// 마지막에 1 추가
graph.add(1);
// list -> arr 변환
return graph.stream().mapToInt(i -> i).toArray();
}
public double[] solution(int k, int[][] ranges) {
int[] height = getHeight(k);
// 콜라츠 횟수는 그래프 길이 -1 만큼
int cnt = height.length - 1;
// 사다리꼴 넓이 구하기
double[] area = new double[cnt + 1];
for (int i = 1; i <= cnt; i++) {
area[i] = (double) (height[i - 1] + height[i]) / 2;
}
// 누적합 구하기
double[] dp = new double[cnt + 1];
for (int i = 1; i <= cnt; i++) {
dp[i] = dp[i - 1] + area[i];
}
double[] answer = new double[ranges.length];
for (int i = 0; i < ranges.length; i++) {
int start = ranges[i][0];
int end = cnt + ranges[i][1];
// start ~ end 까지의 넓이 구하기
if (start <= end) {
// dp[end] = 0 ~ end 까지의 넓이
// dp[start] = 0 ~ start 까지의 넓이
// dp[end] - dp[start] = start ~ end 까지의 넓이
answer[i] = dp[end] - dp[start];
} else {
answer[i] = -1.0;
}
}
return answer;
}
}
우선순위
static void dfs(int idx,int[][] users,int[] emoticons){
if(idx==N){
// 시뮬레이션 시작
int[] result = simulate(users,emoticons);
int cnt = result[0];
int tot = result[1];
if(maxCnt<cnt){
maxCnt = cnt;
maxSale = tot;
}else if(maxCnt==cnt){
if(maxSale<tot){
maxSale = tot;
}
}
return;
}
for(int i = 0 ; i<4;i++){
// 이모티콘의 할인율 할당
emotiPercent[idx] = salePercent[i];
dfs(idx+1,users,emoticons);
}
}
static int[] simulate(int[][] users, int[] emoticons){
int cnt =0;
int tot = 0;
// 유저마다 이모티콘 구매 확인
for(int[] user : users){
int price = 0;
int buyRate = user[0];
int register = user[1];
for(int i = 0 ; i<N;i++){
// 유저가 정한 할인율 보다 높은 것이 있다면
// 이모티콘 구매
if(emotiPercent[i] >=buyRate){
price+= emoticons[i]*0.01*(100-emotiPercent[i]);
}
}
// 유저가 이모티콘플러스를 구입하는지 체크
if(price>=register){
cnt++;
}else{
// 이모티콘 플러스 구입 X
tot+=price;
}
}import java.util.*;
class Solution {
static int[] simulate(int[][] users, int[] emoticons){
int cnt =0;
int tot = 0;
// 유저마다 이모티콘 구매 확인
for(int[] user : users){
int price = 0;
int buyRate = user[0];
int register = user[1];
for(int i = 0 ; i<N;i++){
// 유저가 정한 할인율 보다 높은 것이 있다면
// 이모티콘 구매
if(emotiPercent[i] >=buyRate){
price+= emoticons[i]*0.01*(100-emotiPercent[i]);
}
}
// 유저가 이모티콘플러스를 구입하는지 체크
if(price>=register){
cnt++;
}else{
// 이모티콘 플러스 구입 X
tot+=price;
}
}
return new int[]{cnt,tot};
}
static void dfs(int idx,int[][] users,int[] emoticons){
if(idx==N){
// 시뮬레이션 시작
int[] result = simulate(users,emoticons);
int cnt = result[0];
int tot = result[1];
if(maxCnt<cnt){
maxCnt = cnt;
maxSale = tot;
}else if(maxCnt==cnt){
if(maxSale<tot){
maxSale = tot;
}
}
return;
}
for(int i = 0 ; i<4;i++){
// 이모티콘의 할인율 할당
emotiPercent[idx] = salePercent[i];
dfs(idx+1,users,emoticons);
}
}
static int[] salePercent = {10,20,30,40};
static int[] emotiPercent;
static int maxCnt;
static int maxSale;
static int N;
public int[] solution(int[][] users, int[] emoticons) {
N= emoticons.length;
emotiPercent = new int[N];
// 이모티콘의 크기는 최대 7이다
// 브루트포스가 가능하다 => 4^7= 2^14
dfs(0,users,emoticons);
return new int[]{maxCnt,maxSale};
}
}
import java.util.*;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
Queue<TreeNode> Q = new ArrayDeque<>();
boolean isRightDirect = true;
// 루트노드의 값이 존재한다면 큐에 추가
if(root!=null){
Q.add(root);
}
while (!Q.isEmpty()) {
List<Integer> line = new ArrayList<>();
int size = Q.size();
// 현재 레벨의 크기만큼 반복
while(size-->0){
TreeNode cur = Q.poll();
//오른쪽 방향이면 마지막에 추가
if(isRightDirect){
line.add(cur.val);
}else{// 왼쪽 방향이면 처음에 추가
line.add(0,cur.val);
}
if(cur.left!=null){
Q.add(cur.left);
}
if(cur.right!=null){
Q.add(cur.right);
}
}
// 레벨 반복문 끝
/// 방향 반대로
isRightDirect = !isRightDirect;
result.add(line);
}
return result;
}
}HashMap을 이용하여 해당 문자의 순서값 가져오기. 존재하지 않다면 최댓값 리턴 static class MyComparator implements Comparator<Character> {
HashMap<Character, Integer> orders;
public MyComparator(HashMap<Character, Integer> orders) {
this.orders = orders;
}
@Override
public int compare(Character o1, Character o2) {
// 해쉬맵에 존재하지 않는다면 최대값(26)을 리턴한다.
int order1 = orders.getOrDefault(o1, 26);
int order2 = orders.getOrDefault(o2, 26);
return order1 - order2;
}
} HashMap<Character, Integer> hm = new HashMap<>();
for (int i = 0; i < order.length(); i++) {
hm.put(order.charAt(i), i);
}
class Solution {
static class MyComparator implements Comparator<Character> {
HashMap<Character, Integer> orders;
public MyComparator(HashMap<Character, Integer> orders) {
this.orders = orders;
}
@Override
public int compare(Character o1, Character o2) {
// 해쉬맵에 존재하지 않는다면 최대값(26)을 리턴한다.
int order1 = orders.getOrDefault(o1, 26);
int order2 = orders.getOrDefault(o2, 26);
return order1 - order2;
}
}
public String customSortString(String order, String s) {
HashMap<Character, Integer> hm = new HashMap<>();
for (int i = 0; i < order.length(); i++) {
hm.put(order.charAt(i), i);
}
// 주어진 순서를 만족하게 해주는 Comparator
MyComparator myComparator = new MyComparator(hm);
Character[] charStr = new Character[s.length()];
for (int i = 0; i < s.length(); i++) {
charStr[i] = s.charAt(i);
}
// Comparator 은 Character Wrapper 클래스를 사용해야 함
Arrays.sort(charStr, myComparator);
StringBuilder sb = new StringBuilder();
for (char c : charStr) {
sb.append(c);
}
return sb.toString();
}
}S의 길이 : N
HashSet<Integer> hs = new HashSet<>();
for(int i = 0; i <4;i++){
for(int j = i+1;j<4;j++){
int[] p = arr[i];
int[] q = arr[j];
// 두 점 사이의 거리 체크
int dx = p[0]-q[0];
int dy = p[1]-q[1];
int dist = dx*dx + dy*dy;
hs.add(dist);
}
} int dist = dx*dx + dy*dy;class Solution {
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
// 정사각형 조건
// 네 변 길이 같음. 평행
int[][] arr = new int[][]{p1,p2,p3,p4};
HashSet<Integer> hs = new HashSet<>();
for(int i = 0; i <4;i++){
for(int j = i+1;j<4;j++){
int[] p = arr[i];
int[] q = arr[j];
// 두 점 사이의 거리 체크
int dx = p[0]-q[0];
int dy = p[1]-q[1];
int dist = dx*dx + dy*dy;
hs.add(dist);
}
}
if(hs.contains(0)){
return false;
}
return hs.size()==2;
}
} for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 육지이고 방문하지 않았다면 dfs 실행
if (grid[i][j] == '1' && !visited[i][j]) {
dfs(i, j, grid, visited);
islandCnt++;
}
}
} // dfs 탐색
void dfs(int x, int y, char[][] grid, boolean[][] visited) {
visited[x][y] = true;
// 상하 좌우에 대하여 탐색
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 격자에서 벗어났다면
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}
// 바다이거나, (육지이지만)방문했다면
if (grid[nx][ny] == '0' || visited[nx][ny]) {
continue;
}
//재귀 호출
dfs(nx, ny, grid, visited);
}
}class Solution {
// dfs 탐색
void dfs(int x, int y, char[][] grid, boolean[][] visited) {
visited[x][y] = true;
// 상하 좌우에 대하여 탐색
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 격자에서 벗어났다면
if (nx < 0 || ny < 0 || nx >= n || ny >= m) {
continue;
}
// 바다이거나, (육지이지만)방문했다면
if (grid[nx][ny] == '0' || visited[nx][ny]) {
continue;
}
//재귀 호출
dfs(nx, ny, grid, visited);
}
}
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
int n, m;
public int numIslands(char[][] grid) {
// n = 행, m = 열
n = grid.length;
m = grid[0].length;
boolean[][] visited = new boolean[n][m];
int islandCnt = 0; //섬의 개수
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 육지이고 방문하지 않았다면 dfs 실행
if (grid[i][j] == '1' && !visited[i][j]) {
dfs(i, j, grid, visited);
islandCnt++;
}
}
}
return islandCnt;
}
}
subString을 이용하여 index을 기준으로 왼쪽과 오른쪽을 나눔. 왼쪽에 있는 것은 회전해야 하는 문자열 String endStr =s.substring(0, i);
String startStr = s.substring(i);
String str = startStr + endStr;(),{},[]을 공백으로 치환한다. for(int j= 0 ;j <size;j++){
str = str.replace("{}","");
str = str.replace("[]","");
str = str.replace("()","");
}
class Solution {
public int solution(String s) {
// 길이 1000
// 회전 1000
int size = s.length();
int cnt = 0;
for(int i = 0 ; i<size;i++){
//회전 시킨다.
String endStr =s.substring(0, i);
String startStr = s.substring(i);
String str = startStr + endStr;
// System.out.println(str);
for(int j= 0 ;j <size;j++){
str = str.replace("{}","");
str = str.replace("[]","");
str = str.replace("()","");
}
if(str.length()==0){
cnt++;
}
}
return cnt;
}
}
class Solution {
static boolean dfs(int idx ,String s){
if(idx == s.length()){
return true;
}
for(int i = idx+1;i<=s.length();i++){
String subStr = s.substring(idx,i);
if(hs.contains(subStr)){
if(dfs(i,s)){
return true;
};
}
}
return false;
}
static HashSet<String> hs;
public boolean wordBreak(String s, List<String> wordDict) {
hs = new HashSet<>();
for(String word : wordDict){
hs.add(word);
}
return dfs(0,s);
}
}class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
HashSet<String> answer = new HashSet<>();
HashSet<String> hs = new HashSet<>();
for(String word : wordDict){
hs.add(word);
if(word.length()==s.length()){
answer.add(word);
}
}
while(hs.size()!=0){
HashSet<String> newHs = new HashSet<>();
for(String word: wordDict){
for(String str : hs){
String word1 = word+str;
String word2 = str+word;
int size = word1.length();
if(size<s.length()){
if(s.substring(0,size).equals(word1)){
newHs.add(word1);
}else if(s.substring(0,size).equals(word2)){
newHs.add(word2);
}
}else if(size==s.length()){
answer.add(word1);
answer.add(word2);
}
}
}
hs = newHs;
}
if(answer.contains(s)){
return true;
}else{
return false;
}
}
}
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
HashSet<String> hs = new HashSet<>();
for(String word : wordDict){
hs.add(word);
if(s.equals(word)){
return true;
}
}
String[] sArr = new String[s.length()];
for(int i = 1; i<s.length();i++){
sArr[i] = s.substring(0,i);
}
while(hs.size()!=0){
HashSet<String> newHs = new HashSet<>();
for(String word: wordDict){
for(String str : hs){
String word1 = word+str;
String word2 = str+word;
int size = word1.length();
if(size<s.length()){
if(sArr[size].equals(word1)){
newHs.add(word1);
}else if(sArr[size].equals(word2)){
newHs.add(word2);
}
}else if(size==s.length()){
if(s.equals(word1)){
return true;
}
if(s.equals(word2)){
return true;
}
}
}
}
hs = newHs;
}
return false;
}
}
.은 현재 디렉토리를 의미하고, ..은 이전 디렉토리를 의미함 String cur = st.nextToken();
//현재 path 값이 . 이라면 현재 디렉토리이므로 아무 작업 할 필요 없음
if (cur.equals(".")) {
continue;
}
// ..이라면 이전 디렉토리으로 이동
if (cur.equals("..")) {
if (!deque.isEmpty()) {
deque.pollLast();
}
//그 외는 경로에 추가
} else {
deque.addLast(cur);
}import java.util.*;
class Solution {
//경로 압축
public String simplifyPath(String path) {
// "/"을 기준으로 나눔
StringTokenizer st = new StringTokenizer(path, "/");
Deque<String> deque = new ArrayDeque<>();
while (st.hasMoreTokens()) {
String cur = st.nextToken();
//현재 path 값이 . 이라면 현재 디렉토리이므로 아무 작업 할 필요 없음
if (cur.equals(".")) {
continue;
}
// ..이라면 이전 디렉토리으로 이동
if (cur.equals("..")) {
if (!deque.isEmpty()) {
deque.pollLast();
}
//그 외는 경로에 추가
} else {
deque.addLast(cur);
}
}
StringBuilder sb = new StringBuilder();
while (!deque.isEmpty()) {
sb.append("/").append(deque.pollFirst());
}
// 경로가 공백인 경우는 루트 경로 리턴
return !sb.isEmpty() ? sb.toString() : "/";
}
}K : /으로 나눈 문자의 개수
int[][] dp = new int[N+1][M+1];
for(int i = 1; i<=N;i++){
for(int j = 1; j<=M;j++){
dp[i][j] = grid[i-1][j-1];
}
} int up = dp[i-1][j];
int left = dp[i][j-1];
int minValue = Math.min(up,left);
dp[i][j] += minValue;class Solution {
private static int INF = 40_001;
public int minPathSum(int[][] grid) {
int N = grid.length;
int M = grid[0].length;
int[][] dp = new int[N+1][M+1];
for(int i = 1; i<=N;i++){
for(int j = 1; j<=M;j++){
dp[i][j] = grid[i-1][j-1];
}
}
for(int i = 2; i<=N;i++){
dp[i][0] = INF;
}
for(int j = 2 ; j<=M;j++){
dp[0][j] = INF;
}
/* init grid
// 0 0 INF INF
// 0 1 3 1
// INF 1 5 1
// INF 4 2 1
*/
for(int i = 1; i <=N;i++){
for(int j =1 ; j<=M;j++){
int up = dp[i-1][j];
int left = dp[i][j-1];
int minValue = Math.min(up,left);
dp[i][j] += minValue;
}
}
return dp[N][M];
}
}BST은 다음과 같은 특성을 가지고 있음
따라서, 루트에서부터 내려가서 현재 노드의 값(val)과 찾으려는 p와 q의 값을 비교
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode cur = root;
int pValue = p.val;
int qValue = q.val;
while(cur!=null){
int curValue = cur.val;
// p ,q 모두 현재 노드의 값보다 큰 경우 오른쪽 자식으로 이동
if(pValue > curValue && qValue > curValue){
cur = cur.right;
}// p,q 모두 현재 노드의 값 보다 작은 경우 왼쪽 자식으로 이동
else if(pValue < curValue && qValue < curValue){
cur = cur.left;
}// 그렇지 않은 경우 현재 노드가 LCA이다.
else{
break;
}
}
return cur;
}
}/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode cur = root;
int pValue = p.val;
int qValue = q.val;
while(cur!=null){
int curValue = cur.val;
// p ,q 모두 현재 노드의 값보다 큰 경우 오른쪽 자식으로 이동
if(pValue > curValue && qValue > curValue){
cur = cur.right;
}// p,q 모두 현재 노드의 값 보다 작은 경우 왼쪽 자식으로 이동
else if(pValue < curValue && qValue < curValue){
cur = cur.left;
}// 그렇지 않은 경우 현재 노드가 LCA이다.
else{
break;
}
}
return cur;
}
}
int[] preqNum = new int[N]; // 이수과목 p -> q (q을 들으라면 p을 들어야 함)
for(int[] preq : prerequisites){
int q = preq[0];
int p = preq[1];
preqList[p].add(q);
preqNum[q]++;
}// 내가 들을 수 있는 과목
Queue<Integer> Q = new ArrayDeque<>();
for(int i = 0 ;i<N;i++){
if(preqNum[i]==0){
Q.add(i);
}
}while(!Q.isEmpty()){
int cur = Q.poll();
for(int next: preqList[cur]){
if(--preqNum[next]==0){
Q.add(next);
}
}
}class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int N = numCourses;
// 이후과목?
List<Integer>[] preqList = new ArrayList[N];
int[] preqNum = new int[N];
for(int i = 0; i <N;i++){
preqList[i] = new ArrayList<>();
}
// 이수과목 p -> q (q을 들으라면 p을 들어야 함)
for(int[] preq : prerequisites){
int q = preq[0];
int p = preq[1];
preqList[p].add(q);
preqNum[q]++;
}
// 내가 들을 수 있는 과목
Queue<Integer> Q = new ArrayDeque<>();
for(int i = 0 ;i<N;i++){
if(preqNum[i]==0){
Q.add(i);
}
}
while(!Q.isEmpty()){
int cur = Q.poll();
for(int next: preqList[cur]){
if(--preqNum[next]==0){
Q.add(next);
}
}
}
// 들을 수 없는 과목이 존재한다면
for(int i = 0 ; i<N;i++){
if(preqNum[i]>0){
return false;
}
}
return true;
}
}
class Solution {
static boolean isBingo(char c ){
// row check
for(int i = 0; i <3;i++){
boolean flag = true;
for(int j = 0 ;j<3;j++){
if(G[i][j] != c){
flag =false;
}
}
if(flag){
return true;
}
}
// col check
for(int i = 0 ; i<3;i++){
boolean flag = true;
for(int j= 0 ; j <3;j++){
if(G[j][i]!=c){
flag = false;
}
}
if(flag){
return true;
}
}
// diag check
boolean isTrue = true;
for(int i = 0 ; i<3;i++){
if(G[i][i]!= c){
isTrue = false;
}
}
if(isTrue){
return true;
}
isTrue = true;
for(int i = 0 ; i<3;i++){
if(G[i][2-i]!=c){
isTrue = false;
}
}
if(isTrue){
return true;
}
return false;
}
static char[][] G;
public int solution(String[] board) {
int oCnt = 0;
int xCnt = 0;
G = new char[3][3];
for(int i = 0 ; i<3;i++){
for(int j = 0 ; j<3;j++){
G[i][j] = board[i].charAt(j);
if(G[i][j]=='O'){
oCnt++;
}else if(G[i][j] =='X'){
xCnt++;
}
}
}
// X의 개수가 더 많거나
// O의 개수가 X의 개수+1 보다 많은 경우
if(xCnt>oCnt || oCnt>xCnt+1){
return 0;
}
// 현재 o까지 했을 때
if(oCnt>xCnt){
// X 빙고 있으면 안됨
if(isBingo('X')){
return 0;
}
}
// 현재 x까지 했을 때
else if (xCnt == oCnt){
// O 빙고 있으면 안됨
if(isBingo('O')){
return 0;
}
}
return 1;
}
}
for (int j = 1; j < i; j++) {
dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
}
if (i < n) {
dp[i] = Math.max(dp[i], i);
}class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
for (int i = 1; i <= n; i++) {
// dp[1]*dp[1]
for (int j =1;j<i;j++){
dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
}
if(i<n){
dp[i] = Math.max(dp[i], i);
}
}
return dp[n];
}
}
import java.util.*;
class Solution {
static class Ball{
int idx;
int cnt;
boolean isRight;
public Ball(int idx , int cnt, boolean isRight){
this.idx = idx;
this.cnt = cnt;
this.isRight = isRight;
}
}
public int[] minOperations(String boxes) {
// 박스 길이 최대 2000
int N = boxes.length();
int[] arr = new int[N];
int[] tot = new int[N];
Queue<Ball> Q = new ArrayDeque<>();
for(int i = 0 ; i < N ; i++){
if(boxes.charAt(i)-'0' == 1){
if(i>0)
Q.add(new Ball(i-1,1,false));
if(i<N-1)
Q.add(new Ball(i+1,1,true));
}
}
while(!Q.isEmpty()){
Ball cur = Q.poll();
tot[cur.idx]+=cur.cnt;
if(cur.isRight && cur.idx<N-1){
Q.add(new Ball(cur.idx+1,cur.cnt+1, true));
}
if(!cur.isRight && cur.idx>0){
Q.add(new Ball(cur.idx-1,cur.cnt+1,false));
}
}
return tot;
}
}dp
dp 배열을 j번째에 도착할 때 최소가 되는 값이라고 할 때
dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1]) + list.get(j) 으로 계산 가능
메모리를 최소화 하기 위하여 이를 1차원 배열로 사용 가능
0 -> j 로 탐색 하는 것이 아니라 j-1 -> 0으로 반대로 탐색
for(int i = 0 ; i<N;i++){
List list = triangle.get(i);
for(int j = list.size()-1 ; j>=0;j--){
dp[j+1] = Math.min(dp[j+1],dp[j]) +(int) list.get(j);
}
}import java.util.List;
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int N = triangle.size();
int[] dp = new int[N+1];
for(int i = 0 ; i<N;i++){
List list = triangle.get(i);
for(int j = list.size()-1 ; j>=0;j--){
dp[j+1] = Math.min(dp[j+1],dp[j]) +(int) list.get(j);
}
}
int minValue = Integer.MAX_VALUE;
for(int i = 1; i<=N;i++){
minValue = Math.min(minValue,dp[i]);
}
return minValue;
}
}
가장 작은값 출력
public int popSmallest() {
int result = PQ.poll();
hs.remove(result);
return result;
}숫자 추가
public void addBack(int num) {
if(!hs.contains(num)){
hs.add(num);
PQ.add(num);
}
}class SmallestInfiniteSet {
PriorityQueue<Integer> PQ ;
HashSet<Integer> hs;
public SmallestInfiniteSet() {
PQ = new PriorityQueue<>();
hs = new HashSet<>();
for(int i = 1; i<=1000;i++){
PQ.add(i);
hs.add(i);
}
}
public int popSmallest() {
int result = PQ.poll();
hs.remove(result);
return result;
}
public void addBack(int num) {
if(!hs.contains(num)){
hs.add(num);
PQ.add(num);
}
}
}
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* SmallestInfiniteSet obj = new SmallestInfiniteSet();
* int param_1 = obj.popSmallest();
* obj.addBack(num);
*/
링크 - https://school.programmers.co.kr/learn/courses/30/lessons/67257
연산자 +, -, *의 우선순위를 정하여 수식 결과의 절댓값을 최대화 하는 문제
* > + > -
100-200*300-500+20
= 100-(200*300)-500+20
= 100-60000-(500+20)
= (100-60000)-520
= (-59900-520)
= -60420
String del = "+-*";
StringTokenizer st = new StringTokenizer(expression, del, true);
nums = new ArrayList<>();
ops = new ArrayList<>();
while (st.hasMoreTokens()) {
String next = st.nextToken();
if (next.length() == 1 && del.contains(next)) {
ops.add(next.charAt(0));
} else {
long n = Long.parseLong(next);
nums.add(n);
}
} /* 연산 우선순위 순열 */
static void perm(int depth) {
if (depth == 3) {
long result = solve();
maxVal = Math.max(maxVal, result);
return;
}
for (int i = 0; i < 3; i++) {
if (!visited[i]) {
visited[i] = true;
opOrder[depth] = opArr[i];
perm(depth + 1);
visited[i] = false;
}
}
} static long calc(long a, long b, char op) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
default:// 연산자가 *
return a * b;
}
} // 연산자 우선순위가 높은 것부터 반복문 돌아서 실행
for (char op : opOrder) {
for (int i = 0; i < newOps.size(); i++) {
if (newOps.get(i) == op) {
long n1 = newNums.get(i);
long n2 = newNums.get(i + 1);
long result = calc(n1, n2, op);
newNums.remove(i + 1);
newNums.remove(i);
newNums.add(i, result);
newOps.remove(i);
i--;
}
}
}우선순위 : [*, +, -]
ops : [-, *, -, +] ,nums : [100, 200, 300, 500, 20]
ops : [-, -, +] ,nums : [100, 60000, 500, 20]
ops : [-, -] ,nums : [100, 60000, 520]
ops : [-] ,nums : [-59900, 520]
result :-60420
import java.util.*;
class Solution {
static long calc(long a, long b, char op) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
default:// 연산자가 *
return a * b;
}
}
static long solve() {
List<Long> newNums = new ArrayList<>(nums);
List<Character> newOps = new ArrayList<>(ops);
System.out.println("우선순위 : " + Arrays.toString(opOrder));
// 연산자 우선순위가 높은 것부터 반복문 돌아서 실행
for (char op : opOrder) {
for (int i = 0; i < newOps.size(); i++) {
if (newOps.get(i) == op) {
System.out.print("ops : " + newOps);
System.out.println(" ,nums : " + newNums);
long n1 = newNums.get(i);
long n2 = newNums.get(i + 1);
long result = calc(n1, n2, op);
newNums.remove(i + 1);
newNums.remove(i);
newNums.add(i, result);
newOps.remove(i);
i--;
}
}
}
long result = Math.abs(newNums.get(0));
System.out.println("result :" + newNums.get(0));
return result;
}
/* 연산 우선순위 순열 */
static void perm(int depth) {
if (depth == 3) {
long result = solve();
maxVal = Math.max(maxVal, result);
return;
}
for (int i = 0; i < 3; i++) {
if (!visited[i]) {
visited[i] = true;
opOrder[depth] = opArr[i];
perm(depth + 1);
visited[i] = false;
}
}
}
static char[] opOrder = new char[3];
static boolean[] visited = new boolean[3];
static char[] opArr = {'+', '-', '*'};
static long maxVal = 0;
static List<Long> nums;
static List<Character> ops;
public long solution(String expression) {
String del = "+-*";
StringTokenizer st = new StringTokenizer(expression, del, true);
nums = new ArrayList<>();
ops = new ArrayList<>();
while (st.hasMoreTokens()) {
String next = st.nextToken();
if (next.length() == 1 && del.contains(next)) {
ops.add(next.charAt(0));
} else {
long n = Long.parseLong(next);
nums.add(n);
}
}
perm(0);
return maxVal;
}
}
class Solution {
public void deleteNode(ListNode node) {
// 해당 노드를 삭제하는 것이 아니라
// 다음 노드의 값들을 가져옴
ListNode next = node.next;
node.val = next.val;
node.next = next.next;
}
}import java.util.*;
class Solution {
static class Time implements Comparable<Time>{
int h;
int m;
public Time(int h, int m){
this.h = h;
this.m = m;
}
static int diff(Time a,Time b){
int aMinute = 60*a.h+a.m;
int bMinute = 60*b.h+b.m;
return Math.abs(aMinute-bMinute);
}
public int compareTo(Time o){
if(this.h ==o.h){
return this.m - o.m;
}
return this.h - o.h;
}
}
public int findMinDifference(List<String> timePoints) {
int N = timePoints.size();
Time[] times = new Time[N];
int p = 0;
for(String time : timePoints){
StringTokenizer st = new StringTokenizer(time,":");
int h = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
times[p++] = new Time(h,m);
}
Arrays.sort(times);
int minDiff = 24*60;
for(int i=1;i<N;i++){
Time left = times[i-1];
Time right = times[i];
int diff = Time.diff(left,right);
minDiff = Math.min(minDiff,diff);
}
Time firstPlus24 = new Time(times[0].h+24, times[0].m);
minDiff = Math.min(minDiff,Time.diff(firstPlus24,times[N-1]));
return minDiff;
}
}
Q1 = [3,3,3,3]
Q2 = [3,3,21,3]
import java.util.*;
class Solution {
static int solve(int[] queue1,int[] queue2){
Queue<Integer> Q1 = new ArrayDeque<>();
Queue<Integer> Q2 = new ArrayDeque<>();
int cntMax = (queue1.length + queue2.length)*2;
long q1Tot = 0;
long tot = 0;
int q1Max = 0;
int q2Max = 0;
for(int n : queue1){
Q1.add(n);
q1Tot+=n;
tot+=n;
q1Max = Math.max(q1Max,n);
}
for(int n : queue2){
Q2.add(n);
tot+=n;
q2Max = Math.max(q2Max,n);
}
// 두 큐의 합을 같게 만들 수 없는 경우
long mid = tot/2;
if(tot%2==1 || q1Max>mid || q2Max>mid ){
return -1;
}
int cnt = 0;
while(Q1.size()>0 && cnt<=cntMax){
if(q1Tot == mid){
return cnt;
}
else if(q1Tot > tot/2){
int n = Q1.poll();
Q2.add(n);
q1Tot-=n;
cnt++;
}else{
int n = Q2.poll();
Q1.add(n);
q1Tot+=n;
cnt++;
}
}
return -1;
}
public int solution(int[] queue1, int[] queue2) {
int result = solve(queue1,queue2);
return result;
}
}i칸 도착했을 때 가능한 경우의 수는
i-1칸에서 1칸 점프i-2칸에서 2칸 점프 dp[i] = (dp[i-2] +dp[i-1])class Solution {
public long solution(int n) {
int[] dp = new int[n+1];
dp[1] = 1;
dp[0] = 1;
for(int i =2;i<n+1;i++){
dp[i] = (dp[i-2] +dp[i-1])%1234567;
}
return dp[n];
}
}
자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 "집합"으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다.
각 원소의 합이 S가 되는 수의 집합
위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합
class Solution {
public int[] solution(int n, int s) {
// n개의 자연수로 s를 만들 수 없는 경우
if (n > s) {
return new int[]{-1};
}
// 각 원소가 골고루 분배되어야 함
int[] answer = new int[n];
int div = s / n;
int remainder = s % n;
// 오름차순으로 정렬되어야 하므로 오른쪽부터 시작
for (int i = n - 1; i >= 0; i--) {
answer[i] = div;
if (remainder-- > 0) {
answer[i] += 1;
}
}
return answer;
}
}
class Solution {
public int dfs(int idx ,int sum,int[] nums,int target){
//마지막에 도달했을 때
if(idx==N){
//총합이 target 이라면
if(sum==target){
return 1;
}
return 0;
}
return dfs(idx+1,sum+nums[idx],nums,target) + dfs(idx+1,sum-nums[idx],nums,target);
}
static int N;
static int target;
static int[] nums;
public int findTargetSumWays(int[] nums, int target) {
N = nums.length;
//sum 범위 -20000 ~ 20000
return dfs(0,0,nums,target);
}
}
class Solution {
public int countPrimes(int n) {
// n보다 작은 소수 찾기
boolean[] isPrime = new boolean[n+1];
Arrays.fill(isPrime,true);
// 에라토스체네스의 해
// 소수가 아닌 것 false로 변경
for(int i = 2; i <=n;i++){
for(int j =2;i*j<=n;j++){
int num = i*j;
isPrime[num] = false;
}
}
// 개수 체크
int cnt = 0;
for(int i = 2; i<n;i++){
if(isPrime[i]){
cnt++;
}
}
return cnt;
}
}// mul : 1 -1 1 -1 1 -1 1 -1
// *
// seq : 2 3 -6 1 3 -1 2 4
// ||
// calc : 2 -3 -6 -1 3 1 2 -4 int[] calc = new int[N];
// (1,-1)을 교차하여 곱한 값
int p = 1;
for(int i = 0 ;i <N;i++){
calc[i] = sequence[i]*p;
p*=-1;
} long plus = 0; // 구간 배열의 합중 가장 큰 양수
long minus = 0;// 구간 배열의 합중 가장 큰 음수
long result = 0;
for(int i = 0 ; i<N;i++){
int cur = calc[i];
plus +=cur;
minus +=cur;
// 구간 배열의 합 < cur 인 경우 기존 구간을 사용하지 않아도 됨
plus = Math.max(plus,cur);
minus = Math.min(minus,cur);
long maxAbs = Math.max(plus,Math.abs(minus));
result = Math.max(result,maxAbs);
}class Solution {
public long solution(int[] sequence) {
//연속 펄스 부분 수열의 합 가장 큰 것 리턴하기
int N = sequence.length;
// MAX = 500_000 * 100_000 => 500억?
// mul : 1 -1 1 -1 1 -1 1 -1
// *
// seq : 2 3 -6 1 3 -1 2 4
// ||
// calc : 2 -3 -6 -1 3 1 2 -4
int[] calc = new int[N];
// (1,-1)을 교차하여 곱한 값
int p = 1;
for(int i = 0 ;i <N;i++){
calc[i] = sequence[i]*p;
p*=-1;
}
long plus = 0; // 구간 배열의 합중 가장 큰 양수
long minus = 0;// 구간 배열의 합중 가장 큰 음수
long result = 0;
for(int i = 0 ; i<N;i++){
int cur = calc[i];
plus +=cur;
minus +=cur;
// 구간 배열의 합 < cur 인 경우 기존 구간을 사용하지 않아도 됨
plus = Math.max(plus,cur);
minus = Math.min(minus,cur);
long maxAbs = Math.max(plus,Math.abs(minus));
result = Math.max(result,maxAbs);
}
return result;
}
}
들어오는 간선은 0개, 시작 지점에서 나가는 간선은 2개 이상임int start = -1;
for(int i = 0; i<N;i++){
if(in[i] == 0 && out[i]>=2){
start = i;
}
}도넛 모양
막대 모양
8자 모양
dfs을 이용하여 그래프를 탐색한다.
만약, 해당 정점에서 나가는 간선의 개수가 2개 이상이면 해당 정점이 있는 그래프는 8자 그래프이다.
또한, 시작 지점으로 돌아 오는 경우 이 그래프는 도넛 모양 그래프이다.
void dfs(int v,int start){
if(adjList[v].size()>=2){
isEight = true;
return;
}
for(int next : adjList[v]){
// 그래프 탐색시 시작 지점으로 돌아 온다면 도넛모양
if(next == start){
isDoughnut = true;
return;
}
dfs(next,start);
}
}import java.util.ArrayList;
import java.util.List;
class Solution {
int[] in;
int[] out;
List<Integer>[] adjList;
boolean isEight;
boolean isDoughnut;
static final int DOUGHNUT_IDX = 1;
static final int STICK_IDX = 2;
static final int EIGHT_IDX = 3;
void init(int[][] edges){
int N = -1;
for(int[] edge : edges){
N = Math.max(N,edge[0]);
N = Math.max(N,edge[1]);
}
in = new int[N+1];
out = new int[N+1];
adjList = new ArrayList[N+1];
for(int i = 0; i<=N;i++){
adjList[i] = new ArrayList<>();
}
for (int[] edge : edges) {
int start = edge[0];
int end = edge[1];
// start -> end
in[end]++;
out[start]++;
adjList[start].add(end);
}
}
void dfs(int v,int start){
if(adjList[v].size()>=2){
isEight = true;
return;
}
for(int next : adjList[v]){
// 그래프 탐색시 시작 지점으로 돌아 온다면 도넛모양
if(next == start){
isDoughnut = true;
return;
}
dfs(next,start);
}
}
public int[] solution(int[][] edges) {
int N = -1;
for(int[] edge : edges){
N = Math.max(N,edge[0]);
N = Math.max(N,edge[1]);
}
init(edges);
int start = -1;
for(int i = 0; i<N;i++){
if(in[i] == 0 && out[i]>=2){
start = i;
}
}
int[] answer = new int[4];
answer[0] = start;
for(int next: adjList[start]){
// 그래프 탐색
dfs(next,next);
if(isEight){
answer[EIGHT_IDX] += 1;
}else if(isDoughnut){
answer[DOUGHNUT_IDX] += 1;
}else{
answer[STICK_IDX] += 1;
}
}
return answer;
}
}
플로이드 워셜 : 모든 정점에서 다른 정점까지의 최소 거리를 구할 때 사용 for(int k = 1; k<=n ; k++){
for(int i = 1; i<=n ; i++){
for(int j = 1 ; j<=n ; j++){
dp[i][j] = Math.min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}import java.util.*;
class Solution {
public int solution(int n, int s, int a, int b, int[][] fares) {
// s -> m
// m -> a
// m -> b 경로 계산
int[][]dp = new int[n+1][n+1];
int MAX_COST = 100_000*200;
for(int[] row : dp){
Arrays.fill(row,MAX_COST);
}
for(int i = 1; i<=n;i++){
dp[i][i] = 0;
}
for(int[] fare : fares){
int v1 = fare[0];
int v2 = fare[1];
int cost = fare[2];
dp[v1][v2] = cost;
dp[v2][v1] = cost;
}
for(int k = 1; k<=n ; k++){
for(int i = 1; i<=n ; i++){
for(int j = 1 ; j<=n ; j++){
dp[i][j] = Math.min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
// for(int[] row : dp){
// System.out.println(Arrays.toString(row));
// }
int minCost = MAX_COST*2;
for(int i = 1;i<=n;i++){
int cost = dp[s][i] + dp[i][a] + dp[i][b];
minCost = Math.min(minCost,cost);
}
return minCost;
}
}
// ex) "CBD" => C:1, B:2, D:3
for (int i = 0; i < skill.length(); i++) {
int idx = skill.charAt(i) - 'A';
skillOrder[idx] = i + 1;
}class Solution {
public int solution(String skill, String[] skill_trees) {
int answer = 0;
int[] skillOrder = new int[26];
// 선행스킬 순서를 저장
// ex) "CBD" => C:1, B:2, D:3
for (int i = 0; i < skill.length(); i++) {
int idx = skill.charAt(i) - 'A';
skillOrder[idx] = i + 1;
}
fail:
for (String skill_tree : skill_trees) {
int skillDepth = 1;
int skillLen = skill_tree.length();
for (int i = 0; i < skillLen; i++) {
int idx = skill_tree.charAt(i) - 'A';
// 선행조건에 없는 스킬은 무시
// 선행조건에 있는 스킬이 순서에 맞지 않으면 실패
if (skillOrder[idx] == skillDepth) {
skillDepth++;
} else if (skillOrder[idx] > skillDepth) {
// 선행조건에 있는 스킬이 순서에 맞지 않으면 실패(다음 스킬트리로 continue)
continue fail;
}
}
// 주어진 스킬트리가 선행조건에 만족하면 성공
answer++;
}
return answer;
}
}
[링크] - https://leetcode.com/problems/sort-list/
다음과 같은 selection sort을 이용한 solution => 시간초과 O (N^2)
class Solution {
public ListNode sortList(ListNode head) {
if(head==null){
return null;
}
ListNode cur = head;
int minValue = head.val;
ListNode minNode = head;
// find min Node
while(cur.next!=null){
ListNode next = cur.next;
if(next.val< minValue){
minValue = next.val;
minNode = next;
}
cur = next;
}
// swapping
int tmp = head.val;
head.val = minNode.val;
minNode.val = tmp;
sortList(head.next);
return head;
}
}class Solution {
public ListNode sortList(ListNode head) {
ListNode cur = head;
List<Integer> list = new ArrayList<>();
while(cur!=null){
list.add(cur.val);
cur = cur.next;
}
Collections.sort(list);
Queue<Integer> Q = new ArrayDeque<>();
for(int n : list){
Q.add(n);
}
int p = 0;
cur = head;
while(cur!=null){
cur.val = Q.poll();
cur = cur.next;
}
return head;
}
}StringTokenizer 이용import java.util.*;
class Solution {
public String solution(String s) {
String answer = "";
StringTokenizer st = new StringTokenizer(s);
StringBuilder sb = new StringBuilder();
while(st.hasMoreTokens()){
String word = st.nextToken();
System.out.println("word = "+word);
int len = word.length();
// 첫 번째 문자 대문자로
char firstChar = word.charAt(0);
sb.append(Character.toUpperCase(firstChar));
// 나머지 문자 소문자로
for(int i =1 ; i<len;i++){
char c = word.charAt(i);
sb.append(Character.toLowerCase(c));
}
if(st.hasMoreTokens()){
sb.append(" ");
}
}
return sb.toString();
}
}charAt()을 이용import java.util.*;
class Solution {
public String solution(String s) {
StringBuilder sb = new StringBuilder();
boolean isFirst = true;
int len = s.length();
for(int i=0; i<len;i++){
char c = s.charAt(i);
// 단어의 첫 문자 체크
if(isFirst){
sb.append(Character.toUpperCase(c));
}else{
sb.append(Character.toLowerCase(c));
}
// 현재 공백인지 아닌지 체크
if(c==' '){
isFirst = true;
}else{
isFirst = false;
}
}
return sb.toString();
}
} int nextHeight = heights[nx][ny];
int diffHeight =Math.abs(nextHeight - currentHeight);
int maxEffort = Math.max(effort, diffHeight);
// 현재보다 노력이 큰 경우 더이상 진행하지 않음
if(maxEffort>=minEffort[nx][ny]) {
continue;
}
dfs(nx, ny, maxEffort, heights); void dfs(int x,int y, int effort,int[][] heights){
minEffort[x][y] = Math.min(minEffort[x][y],effort);
if(x == N-1 && y== M-1){
return;
}
int currentHeight = heights[x][y];
for(int i = 0; i<4;i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<0|| ny<0 || nx>=N|| ny>=M ) {
continue;
}
int nextHeight = heights[nx][ny];
int diffHeight =Math.abs(nextHeight - currentHeight);
int maxEffort = Math.max(effort, diffHeight);
// 현재보다 노력이 큰 경우 더이상 진행하지 않음
if(maxEffort>=minEffort[nx][ny]){
continue;
}
dfs(nx, ny, maxEffort, heights);
}
}import java.util.*;
class Solution {
static List<int[]> routes;
static void move(int start,int end,int other, int size){
if(size==0){
return;
}
move(start,other,end,size-1);
routes.add(new int[]{start,end});
move(other,end,start,size-1);
}
public int[][] solution(int n) {
routes = new ArrayList<>();
move(1,3,2,n);
int N = routes.size();
int[][] answer = new int[N][2];
for(int i = 0; i < N; i++){
answer[i] = routes.get(i);
}
return answer;
}
} isPalindrome = new boolean[N][N];
for(int i = 0 ; i<N;i++){
isPalindrome[i][i] = true;
}
for(int i = N-1;i>=0;i--){
for(int j = i+1;j<N;j++){
// i~j가 팰린드룸인지 확인
// i와 j가 같은 문자라면
if (s.charAt(i) ==s.charAt(j)){
// i와 j의 차이가 1이라면 팰린드룸 , ex) aa
if(j-i==1) {
isPalindrome[i][j] = true;
}else{
// i~j가 팰린드룸이라면 i+1~j-1도 팰린드룸인지 확인
isPalindrome[i][j] = isPalindrome[i+1][j-1];
}
}
}
} // s~e까지의 문자열을 팰린드룸으로 나누는 함수
private void rec(int s, int e, String str, List<String> route){
if(s==e){
result.add(route);
return;
}
// 문자열을 다음과 같이 쪼갤 것임
// [s, s+1, .... i] , i+1, ... e-1
// [s, s+1, .... i]가 팰린드룸이라면 다음 재귀 호출
for(int i = s;i<e;i++){
// s~i가 팰린드룸이라면 다음 재귀 호출
if(isPalindrome[s][i]){
List<String> newRoute = new ArrayList<>(route);
String substring = str.substring(s, i+1);
newRoute.add(substring);
// 다음 제귀 호출
rec(i + 1, e, str, newRoute);
}
}
}class Solution {
public int solution(String skill, String[] skill_trees) {
int answer = 0;
int[] skillOrder = new int[26];
// 스킬트리 순서를 저장
// ex) "CBD" => C:1, B:2, D:3
for (int i = 0; i < skill.length(); i++) {
int idx = skill.charAt(i) - 'A';
skillOrder[idx] = i + 1;
}
fail:
for (String skill_tree : skill_trees) {
int skillDepth = 1;
int skillLen = skill_tree.length();
for (int i = 0; i < skillLen; i++) {
int idx = skill_tree.charAt(i) - 'A';
// 선행조건에 없는 스킬은 무시
// 선행조건에 있는 스킬이 순서에 맞지 않으면 실패
if (skillOrder[idx] == skillDepth) {
skillDepth++;
} else if (skillOrder[idx] > skillDepth) {
continue fail;
}
}
// 주어진 스킬트리가 선행조건에 만족하면 성공
answer++;
}
return answer;
}
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// i가 k을 이기고
// k가 j을 이긴다면?
// => i > k > j
// => i가 j을 이긴다.
if (isWin[i][k] && isWin[k][j]) {
isWin[i][j] = true;
}
}
}
}continue loop; : label이 loop부분을 continue 합니다. loop:
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// i가 j을 이길 수 있거나
// j가 i을 이길 수 있거나
if (!isWin[i][j] && !isWin[j][i]) {
continue loop;
}
}
// 1부터 j까지 모두 승패를 알 수 있다면 canCnt++;
canCnt++;
}import java.util.*;
class Solution {
private static final int INF = 100_000;
public int solution(int n, int[][] results) {
// 1-based (1~n)
// 이길 수 있는지 없는지 체크하는 배열
boolean[][] isWin = new boolean[n + 1][n + 1];
for (boolean[] row : isWin) {
Arrays.fill(row, false);
}
for (int i = 1; i <= n; i++) {
isWin[i][i] = true;
}
for (int[] result : results) {
int winIdx = result[0];
int loseIdx = result[1];
// winIdx는 loseIdx을 이길 수 있음
isWin[winIdx][loseIdx] = true;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// i가 k을 이기고
// k가 j을 이긴다면?
// => i > k > j
// => i가 j을 이긴다.
if (isWin[i][k] && isWin[k][j]) {
isWin[i][j] = true;
}
}
}
}
int canCnt = 0;
loop:
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// i가 j을 이길 수 있거나
// j가 i을 이길 수 있거나
if (!isWin[i][j] && !isWin[j][i]) {
continue loop;
}
}
// 1부터 j까지 모두 승패를 알 수 있다면 canCnt++;
canCnt++;
}
return canCnt;
}
}
dp[i] = Math.max(dp[i - 1], dp[i - 2] + newNums[i]);for (int i = 2; i <= N; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + newNums[i]);
}class Solution {
public int rob(int[] nums) {
int N = nums.length;
// 0-base => 1-base
int[] newNums = new int[N + 1];
int[] dp = new int[N + 1];
for (int i = 1; i <= N; i++) {
newNums[i] = nums[i - 1];
}
dp[1] = newNums[1];
for (int i = 2; i <= N; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + newNums[i]);
}
return dp[N];
}
}
적합한 ip인지 확인
boolean isValidIp(String s, int len) {
// len의 길이로 자를 수 없는 경우
if (s.length() < len) {
return false;
}
String currentString = s.substring(0, len);
// 0으로 시작하는 경우
if (currentString.length() > 1 && currentString.charAt(0) == '0') {
return false;
}
int currentInt = Integer.parseInt(currentString);
// 255보다 큰 경우
if (currentInt > 255) {
return false;
}
return true;
}class Solution {
List<String> list = new ArrayList<>();
boolean isValidIp(String s, int len) {
// len의 길이로 자를 수 없는 경우
if (s.length() < len) {
return false;
}
String currentString = s.substring(0, len);
// 0으로 시작하는 경우
if (currentString.length() > 1 && currentString.charAt(0) == '0') {
return false;
}
int currentInt = Integer.parseInt(currentString);
// 255보다 큰 경우
if (currentInt > 255) {
return false;
}
return true;
}
// xxx.xxx.xxx.xxx 형태로 변환
String getIpAddress(String[] ip) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 4; i++) {
sb.append(ip[i]);
if (i != 3) {
sb.append(".");
}
}
return sb.toString();
}
void dfs(int depth, String s, String[] ip) {
if (depth == 4) {
// 아직 남아있는 문자열이 있다면 완성하지 못한 것임
if (!s.isEmpty()) {
return;
}
String ipAddress = getIpAddress(ip);
list.add(ipAddress);
return;
}
// 앞에서부터 1~3개 짤라봄
for (int i = 1; i <= 3; i++) {
if (!isValidIp(s, i)) {
continue;
}
ip[depth] = s.substring(0, i);
String remainString = s.substring(i);
dfs(depth + 1, remainString, ip);
}
}
public List<String> restoreIpAddresses(String s) {
String[] ip = new String[4];
dfs(0, s, ip);
return list;
}
}
int nx = cur.x ;
int ny = cur.y ;
while(true){
if(isStop(nx,ny,i)){
if(!visited[nx][ny]){
visited[nx][ny] = true;
Q.add(new Node(nx,ny,cur.cnt+1));
}
break;
}else{
nx += dx[i];
ny += dy[i];
}
}true 리턴 // 멈출 수 있는지 여부
static boolean isStop(int x, int y,int d){
int nx = x+dx[d];
int ny = y+dy[d];
if(nx==-1 || nx== N || ny==-1 || ny==M|| G[nx][ny]=='D'){
return true;
}
return false;
import java.util.*;
class Solution {
static class Node{
int x;
int y;
int cnt;
public Node(int x, int y,int cnt){
this.x = x;
this.y = y;
this.cnt =cnt;
}
}
// 멈출 수 있는지 여부
static boolean isStop(int x, int y,int d){
int nx = x+dx[d];
int ny = y+dy[d];
if(nx==-1 || nx== N || ny==-1 || ny==M|| G[nx][ny]=='D'){
return true;
}
return false;
}
static int N;
static int M;
static char[][] G;
static boolean[][] visited;
static int[] dx = {-1,1,0,0};
static int[] dy= {0,0,-1,1};
public int solution(String[] board) {
int answer = 0;
N = board.length;
M = board[0].length();
visited= new boolean[N][M];
Queue<Node> Q = new ArrayDeque<>();
G = new char[N][M];
Node end= null;
for(int i =0 ; i<N;i++){
for(int j = 0 ; j<M;j++){
G[i][j] = board[i].charAt(j);
if(G[i][j] == 'R'){
Q.add(new Node(i,j,0));
visited[i][j] = true;
}else if (G[i][j]=='G'){
end = new Node(i,j,0);
}
}
}
while(!Q.isEmpty()){
Node cur = Q.poll();
//골에 도달
if(cur.x==end.x && cur.y==end.y){
return cur.cnt;
}
for(int i = 0 ; i<4;i++){
int nx = cur.x ;
int ny = cur.y ;
while(true){
if(isStop(nx,ny,i)){
if(!visited[nx][ny]){
visited[nx][ny] = true;
Q.add(new Node(nx,ny,cur.cnt+1));
}
break;
}else{
nx += dx[i];
ny += dy[i];
}
}
}
}
return -1;
}
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
for (String a : parenthesis[j]) {
for (String b : parenthesis[i - j]) {
parenthesis[i].add(a + b);
}
}
}
for (String a : parenthesis[i - 1]) {
parenthesis[i].add("(" + a + ")");
}
}import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
class Solution {
public List<String> generateParenthesis(int n) {
// n개의 괄호 리스트 출력하기
// 1 : ()
// 2 : ()(), (())
// 3 : ((())), (()()), (())(), ()(()), ()()()
HashSet<String>[] parenthesis = new HashSet[n + 1];
for (int i = 0; i <= n; i++) {
parenthesis[i] = new HashSet<>();
}
parenthesis[1].add("()");
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
for (String a : parenthesis[j]) {
for (String b : parenthesis[i - j]) {
parenthesis[i].add(a + b);
}
}
}
for (String a : parenthesis[i - 1]) {
parenthesis[i].add("(" + a + ")");
}
}
return new ArrayList<>(parenthesis[n]);
}
}
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.