본문 바로가기

99클럽

99클럽 코테스터디 31일차 TIL + [프로그래머스] 네크워크 java 풀이 1. 문제 설명문제 링크서로 연결되어 있는 그래프를 하나의 군집체로 볼 때, 주어진 전체 노드에서 군집체가 총 몇 개 있는지 구하는 문제이다. 2. 접근 방식인접 리스트 형태로, 노드와 연결 정보를 저장한다. 방문 배열을 만들고 방문하지 않은 배열을 기점으로 BFS를 실행한다.한 번 BFS를 돌면, 시작 정점과 연결된 모든 정점은 방문 처리가 될 것이다. 이는 하나의 군집체를 조회한 걸로 볼 수 있다. 따라서 BFS를 돈 횟수만큼 군집체가 존재하는 것이므로, BFS를 실행한 횟수를 반환하면 된다.3. 코드 분석import java.io.*;import java.util.*;class Solution { public int solution(int n, int[][] computers) { .. 더보기
99클럽 코테 스터디 29일 TIL + [LeetCode] maximum-profit-job-scheduling 풀이설명 1. 문제 설명문제 링크(1) 일거리의 시작 시간, 끝 시간, 일을 끝냈을 때의 이익 이 주어진다.(2) 시작 시간과 끝 시간의 범위가 겹치는 일은 같이 하지 못한다. 반면 어떤 일이 끝나자마자 다른 일은 시작할 수 있다.예를 들어, job A의 끝 시간이 3시 이고 job B의 시작시간이 3시이면 두 일 거리는 연달아 할 수 있다. 반면 job C가 3~5시이고 job D가 4~6시이면 두 일은 일의 시간 범위가 겹치므로 같이하지 못한다.(3) 이때, 겹치지 않게 일을 해서, 최대 이익을 얻으려고 한다. 주어진 일거리들 중에서 가질 수 있는 최대 이익은 몇인가?2. 접근 방식KEY WORD: DP(1) 주어진 문제가 시작시간, 끝시간, 이익을 따로 따로 주기에 이를 하나의 일(job) 단위로 하나로 묶.. 더보기
99클럽 코테 스터디 28일차 + [백준] 1874 스택 수열 java 풀이 1. 문제 설명문제 링크2. 접근 방식KEY WORD: DATA STRUCTURE(0) 현재 조회 중인 수를 value, 출력해야 하는 수를 now라고 해보자.(1) value (2) stack의 top과 now를 비교한다.(3) top이 크면 어떤 방법을 써도 수열을 만들 수 없다. NO를 출력하자.(왜냐하면, 수열은 무조건 stack에서 pop되는 값으로 만들어야 하기 때문이다. stack에는 오름차순으로 값이 저장되기에, 현 stack의 top 값이 크다고 새로 push를 받으면 더 큰 값밖에 들어오지 않는다. stack의 top이 now보다 작을 때는 같은 값이 들어올 때까지 기다리면 되는 것과 상반된다.)(4) top == now 이면 stack에서 pop해서 값을 뺀다.Stack은 진짜 sta.. 더보기
99클럽 코테 스터디 26일차 TIL + [프로그래머스] 개인정보 수집 유효기간 풀이 1. 문제 설명문제 링크(1) 오늘이 몇년, 몇월, 며칠인지 알려주고, 개인정보의 유형별로 정보 보관 기간을 알려준다. (2) String 배열 형태로, 정보가 수집된 날짜, 개인정보의 유형이 주어질 때, 주어진 배열에서 오늘 파기될 정보가 무엇인지, 번호를 배열 형태로 반환하라. 2. 접근 방식KEY WORD: 문자열 자르기해당 문제의 입력은 다음과 같이 주어진다. todaytermsprivaciesresult"2022.05.19"["A 6", "B 12", "C 3"]["2021.05.02 A", "2021.07.01 B", "2022.02.19 C", "2022.02.20 C"][1, 3]"2020.01.01"["Z 3", "D 5"]["2019.01.01 D", "2019.11.15 Z", "2.. 더보기
99클럽 코테 스터디 25일차 TIL + [프로그래머스] 순위 두 가지 풀이 ✨ 1. 문제 설명문제 링크 2. 접근 방식KEY WORD: BFS생각 해야할 점: 하나의 정점이 자신의 위치를 안다는 것은 단방향 그래프에서 해당 정짐이 다른 모든 정점들과 서열를 가진다는 것이다. 이 때, 해당 서열은 간접적으로 파악이 되도 된다.간접적으로 파악된다는 것은 무슨 뜻인가?해당 그림은, 문제에서 예시로 주어진, 정점들간의 관계이다. 문제에서는 2번이 1,4,3번에게 패하고, 5번에게 이겼음으로 4등이라고 했다. 5번은 그 2번에게 졌음으로, 1,3,4번에게도 간접적으로 진 것이다. 따라서 2, 5번은 모든 정점에 대해서 서열을 가진다.(1) 단 방향 그래프를 두 개 만들기첫 번째 방법은 단 방향 그래프 2개 만들기 이다.우리의 핵심은, 현재 조회 중인 정점이 간접적으로라도, 모든 정점과 서열.. 더보기
99클럽 코테 스터디 18일차 TIL + [백준] 5547 일루미네이션 java 완벽 설명! ^^ 1. 문제 설명2. 접근 방식KEY WORD: BFS, IDEA해당 문제는 문제를 풀기 위한 IDEA만 생각해낸다면 간단한 BFS 문제이다. 문제에 대한 접근 방식은 다음과 같다.(1) 입력받은 좌표의 변두리 부분도 페인트를 칠할 수 있다. 가령파란색으로 칠한 부분을 봐라. 만약 입력 좌표 그대로 2차원 배열을 만든다면, 해당 변두리 부분은 배열을 벗어나게 되어, 페인트를 칠할 때 골치가 아파진다. (자칫 잘못하면 OutOfArrayIndex 에러가 나기 때문이다!!)따라서 우리는 해당 좌표도 배열 내에서 받을 수 있도록 2차원 배열을 테두리까지 넉넉하게 만들고, 여기에 입력받은 좌표값들을 집어넣는다.int [][] map = new int [row+2][col+2]그러면 이렇게 받을 수 있다. 파란색으.. 더보기
99 클럽 코테 스터티 16일차 TIL + 프로그래머스 N-queen java 쉬운 풀이! 1. 문제 설명문제 설명2. 접근 방식KEY WORD : BACK-TRACKING(0) 사전 세팅1차원 배열(arr)을 n의 크기만큼 만들고 배열의 index = 행 , 배열의 value = 열로 생각한다.예를 들어 배열이 다음과 같을 때, 그림으로 나타내면 이렇게 된다.index(행)0123value(열)1302(1) 만약에 arr[i] = j 라고 한다면 2차원 배열 [i] [j] 에 퀸을 두겠다는 소리이다. 이게 가능한지 체크한다. 체크하는 방법은0 ~ i-1 까지의 배열 값을 이용해, 이전에 놔둔 퀸의 공격 경로와 겹치는지 확인하면 된다. 확인법은 다음과 같다.(1-1) 좌하단 확인대각선이 일치하는 값들은 모두 행+열의 합이 같다. 이를 이용한다. 우리의 경우는 index가 행이고 value가 열.. 더보기
99 클럽 코테 스터티 15일차 TIL + 프로그래머스 소수 찾기 java 1. 문제 설명문제 설명2. 접근 방식KEY WORD: 브루트 포스(1) 문자열로 받은 숫자를 한 자릿수가 되게 나누어서 배열에 저장한다.(2) 전체 숫자가 n개라면 그 중 k개를 뽑아서 나열한다. (순열, k = 1 ~ n )(3) 나열된 k개의 수를 합쳐서 하나의 숫자로 만들고, 소수 판별한다. (소수 판별법 이용)(4) 소수 판별이 확정되면 해당 수가 이전에 나왔는지, hashSet으로 체크한다. 없으면, 소수의 개수를 +1 올린다.  ※추신※(1)나는 한자리 수를 합치는 것을 원래의 수 * 10 + 새로 들어온 한 자리 수로 그때 그때 바로 했다.(2)소수 판별법을 모른다면, 정리 잘 한 사람 링크를 보고 오기 바란다. 해당 링크에서는 왜 n의 제곱근까지만 나눠서 확인하면 되는지 나와있다.(3)소.. 더보기

티스토리툴바