알고리즘 풀이 (84) 썸네일형 리스트형 [프로그래머스] 다리를 지나는 트럭 - JAVA 🔗 문제 링크 [프로그래머스] 다리를 지나는 트럭 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이 programmers.co.kr 📝 풀이 과정 트럭은 정해진 순서로 진입하고 진입한 순서대로 다리에서 빠져나오기 때문에 Queue를 사용하기로 했다. if (!queue.isEmpty() && time == queue.peek()[1]) { int[] truck = queue.poll(); weight += truck[0]; } Queue에 int배열로 {진입한 트럭의 무게, 도달시간} 순으로 넣고, time을 반복할 때마다 하.. [프로그래머스] 베스트앨범 - JAVA 🔗 문제 링크 [프로그래머스] 베스트앨범 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr 📝 풀이 과정 genreTimes.put(genres[i], genreTimes.getOrDefault(genres[i], 0) + plays[i]); 먼저 장르마다 총 누적 플레이시간을 저장해야하기 때문에 Map.getOrDefault()를 통해 Map에 해당 장르가 존재한다면 기존 값을 얻어와 더해 다시 덮어쓰기 해주고 아니라면 0을 반환해 현재 값을 추가해 넣도록 하였다. List list = new ArrayLi.. [프로그래머스] 전화번호 목록 - JAVA 🔗 문제 링크 [프로그래머스] 전화번호 목록 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 📝 풀이 과정 전화번호를 set에 모두 넣고, for문을 통해 전화번호를 앞에서부터 잘라 set.contains()를 활용해 set에 있는지 확인했다. 만약 set에 존재한다면, 해당 전화번호는 다른 전화번호로 시작하기 때문에 접두어가 있으므로 false를 반환해 주었다. 반복문이 끝날 때까지 return 되지 않았다면, 다른 전화번호가 접두어가 되는 경우가 없기 때문에 true를 반환해 주었다. 💻 코드 impo.. [백준] 15591번: MooTube (Silver) - JAVA 🔗 문제 링크 BOJ 15591번: MooTube (Silver) 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 📝 풀이 과정 문제를 보면 N까지의 영상이 존재하는데 영상끼리 가는 경로는 무조건 존재하며, 개수는 N - 1개라고 주어진다. 이것으로 주어진 그래프가 Spanning Tree(신장 트리, 최소 연결 부분 그래프)임을 알 수 있다. 따라서, 만약 A → B로가는 연결이 끊어진다면 A → B로는 갈 수 없게 되며 A에서 출발해 B에서 연결된 다른 간.. [백준] 1932번: 정수 삼각형 - JAVA 🔗 문제 링크 BOJ 1932번: 정수 삼각형 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 📝 풀이 과정 위층부터 차례로 누적하며 아래층으로 내려왔을 때, 가장 최대가 되는 수의 합을 구하는 문제이다. 문제대로 해결하는 방법도 있겠지만, 그렇게 되면 제일 마지막 층의 합을 구했을 때 다시 한 번 반복을 돌며 최대값을 찾아야 된다고 생각했다. 이를 반대로 아래에서 위로가며 최대값을 누적하는 방식으로 답을 구했다. for (int i = N - 1; i > 0; i--) { for (int j = 0; j < i; j++) nums[i-1][j] += Math.max(nums[i].. [프로그래머스] 다트 게임 / 2018 KAKAO BLIND RECRUITMENT(1차) - JAVA 🔗 문제 링크 [프로그래머스] 다트 게임 / 2018 KAKAO BLIND RECRUITMENT(1차) 코딩테스트 연습 - [1차] 다트 게임 programmers.co.kr 📝 풀이 과정 다트 게임의 결과가 일정한 패턴을 가진 String로 들어오게 된다. String을 하나씩 끊어가며 처리하는 방법도 있겠지만, 숫자의 경우 10이 들어오게 되면 처리가 불편해지기 때문에 Pattern과 Matcher class를 사용하기로 했다. (참고 : [Java] Pattern, Matcher Class로 정규식 활용하기) Pattern pattern = Pattern.compile("([0-9]+)([SDT])([*#]?)"); Matcher matcher = pattern.matcher(dartResult);.. [프로그래머스] 비밀지도 / 2018 KAKAO BLIND RECRUITMENT(1차) - JAVA 🔗 문제 링크 [프로그래머스] 비밀지도 / 2018 KAKAO BLIND RECRUITMENT(1차) 코딩테스트 연습 - [1차] 비밀지도 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다 programmers.co.kr 📝 풀이 과정 지도 두 장을 겹쳐 둘 중 하나라도 벽('1')일 경우 결과 값에 벽('1')이 나오는 것을 보고 OR연산이 떠올랐다. 1010 | 1100 = 1110 Integer.toBinaryString(arr1[i] | arr2[i]).replace('1', '#').replace('0', ' ') 입력은 정수 배열의 형태로 들어오기 때문에 하나씩.. [백준] 1786번: 찾기 - JAVA 🔗 문제 링크 BOJ 1786번: 찾기 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 📝 풀이 과정 주어진 문자열(T)에서 패턴 문자열(P)를 찾아 인덱스를 구하면 되는 간단한 문제이다. 하지만, 범위가 각각 $1,000,000 = 10^6$이므로 단순하게 문자열을 찾는 이중반복문으로 문제를 해결하려고 하면 $O(NM) = 10^{12}$으로 시간초과가 발생하게 된다. 따라서, 효율적으로 문자열을 찾는 알고리즘인 KMP 알고리즘을 사용해야 한다. 처음 문제를 풀 때, 기존 KMP에서 인덱스를 저장하는 .. 이전 1 ··· 3 4 5 6 7 8 9 ··· 11 다음
