프로그래머스 AND 백준/java11 백준 14889 스타트와 링크 java 팀 밸런스가 잘 맞아야 한다. 해결 아이디어는 다음과 같다. 1. n 수가 굉장히 적다. 20명중에서 10팀을 뽑는다고 해도 20 c 10이기 때문에 브루트포스로 해도 충분하다. 그래서 백트래킹을 쓰면 될 것 같았다.2. 일단 백트래킹으로 10팀을 뽑고, 2중 for문으로 team1의 시너지를 모두 sum에 더해준다.3. team1에 속하지 않은 팀 2의 시너지도 모두 필요하기 때문에 visited 배열 또한 만들어줘서 visited[]가 false인 값을 team2로 설정한다.4. Math.abs(sum1-sum2) 값을 Math.min(min, 절대값) 이렇게 해준다.5. min을 출력한다. package programers;import java.util.Scanner;public class .. 2024. 4. 29. 프로그래머스 호텔대실 우연히도 PriorityQueue를 배우자 마자 써먹을 기회가 생긴 것 같다.회의실 관련 문제는 이렇게 접근하면 된다. 1. 회의 전체를 시작시간 순서대로, 시작 시간이 동일하다면 끝나는 시간 순서대로 정렬한다.2. PriorityQueue를 만들어서 끝나는 시간 기준 오름차순으로 설정한다 (제일 빨리 끝나는 회의가 필요하기 때문)3. 회의 전체의 while문을 돌려서 만약 회의 시작 시간 기준 끝난 회의가 있다면 pq를 모두 poll해준다4. pq에 offer 해준다5. result = Math.max(result, pq.size())를 해준다 다만 시간이 String으로 되어있고 사용하기 불편했기 때문에 나같은 경우에는 시간이 있다면 :를 떼어버리고 parseInt를 해줬다.이럴 경우에는 00 : 5.. 2024. 4. 25. 비트마스크 알고리즘 풀다가 비트마스크라는 것을 처음알았다. 이진수를 이용해서 집합을 만든다고 이해하면 될 것 같다. 이해한 대로 설명하자면 비트 하나하나를 집합(set)으로 쓸 수 있다는 것이다. 큰 장점은 비트 하나 하나가 집합 하나 하나기 때문에 메모리 사용량이 극도로 적어진다는 것이다. ex) 10진수 2진수 16 1000 17 1001 31 1111 즉 만약 length가 4인 집합을 만들고 싶다면 이렇게 4비트의 메모리만 있어도 된다. 여기서 0,1이 false, true값이다. 1. 1 2024. 4. 11. 백준9019_DSLR 생각보다 별거 없었다. DSLR가져오는 아이디어만 고려하면 나머지는 그냥 기본 BFS로 접근하면 완성,. 아래와 같이 만들었다. 어차피 9999까지 만들고 visited 배열 있으니까 시간복잡도에 무리는 없을 것 같았다. 물론 test case가 많지만. - 참고 사항으로는 그냥 초기화만 해줬는데- 그렇게 되면 String 배열에서는 null값이 들어간다는 것을 알았지만서도 (이전것 + " ")를 통해서 graph 배열에 넣어주니까 예상과는 다르게 NullDSLR 이런식으로 들어갔다. 그래서 start 배열에는 그냥 "" 2024. 4. 11. 프로그래머스 - 석유시추 구현 1차 절망, 시간복잡도 2차 절망이었다. 처음에는 그냥 bfs + visited로 해서 열마다 방문 횟수 초기화를 해주면서 계속 돌렸는데, 정답은 구할 수 있지만 효율성 테스트에서 전부 시간 초과가 나왔다. 그래서 생각한 건 방문 횟수 초기화를 하지 말고 모든 그래프를 돌며 수행한 bfs의 결과를 배열로 만들어서 [left, right, count] 전체 열을 돌면서 이중 배열을 만들어주고 전체 열만 돌면서 left = col 인 경우 count++ 를 해주고 나온 값의 max를 리턴해줬다. 이렇게 하니까 시간복잡도는 줄일 수 있었는데 문제 2,3 번에서는 시간초과가 나왔다. 그러다가 생각난 게 굳이 배열을 만들어서 for문을 돌릴 필요 없이 저 배열 하나를 add 하는 대신 처음에 전체 열의 co.. 2024. 3. 25. 백준 2573번 bfs 배우니까 신세계가 따로 없다. 뭐 말로는 dfs로 풀 수 있는 건 bfs로 풀 수 있는데 bfs로 풀 수 없는 건 dfs로 풀 수 없다니까 bfs라도 잘 알아놓고 가자. 일단 그래프를 만든다. 하지만 여기는 동서남북 모든 노드의 정보를 알아야 하기 때문에 테두리를 둘러줘야한다. 그래서 그래프의 넓이를 n+1이 아닌 n+2로 만들어준다. why? 1에서 n까지가 행과 열의 넓이라고 가정해보자 1 1 1 1 1 1 1 1 1 11 11 1 1 1 1 11 1 1 1 1 1 1 1 111 1 1 1 1 1 1 1이 들어가있는 노드가 그래프의 시작이라고 가정하자. 시간의 흐름을 옆 노드를 기준으로 반영하기 위해서는 위, 아래, 좌, 우 노드가 모두 있어야만 한다. (그렇지 않다면 첫 번째 인덱스를 돌다가.. 2024. 3. 24. 이전 1 2 다음
