본문 바로가기

Algorithm/Practice

 (81)
Programmers - 순위 with JAVA (V) 문제 격투 대회에서 각 참가자의 번호가 1~N으로 주어지고 대결 결과가 주어진다. 이 때, 순위를 정확히 알 수 있는 사람의 수를 구하라. 로직 이 문제는 shortest way의 플로이드 워셜 알고리즘 중에 정확한 순위 문제와 유사하다. 순위 문제는 종종 나오는데, 정확한 순위를 알 수 있는지 여부 문제와 정확한 순위가 무엇인지 문제, 정확한 순위를 알 수 있는 경우의 수 문제가 주어진다. 정확한 순위를 알 수 있는지 true/false : 위상 정렬을 사용하여 판단. 싸이클이 발생하는 경우(큐에서 꺼내는 값의 개수가 0인 경우), 두개 값의 순위 구별이 안되는 경우 (큐에서 꺼내는 값의 수가 두개이상인 경우) 정확한 순위가 무엇인지 : 위상정렬 활용 (위의 경우를 벗어나면 정확한 순위를 알 수 있다...
Programmers - 큰 수 만들기 with JAVA (V) 문제 문제는 굉장히 간단하다. 주어진 숫자에서 순서를 바꾸지 않고 K만큼의 수를 삭제하여 가장 큰수를 만드는 것이다. 예를들어, 18403, k=2일때, 843이 되는 것이다. 아이디어 및 로직 우선적으로 아이디어는 앞에서부터 삭제할지 여부를 판단하는데 현재 값이 앞에 있는 값보다 작으면 삭제를 한다. 예를 들어, 83845가 있을 때, 8을 입력, 3을 입력, 8을 입력할 때는 3은 삭제된다. 1. Check 리스트 생성 2. 주어진수의 첫번째 수부터 확인 3. Check 리스트가 비어있다면 초기값 삽입 후 다음 수 확인 4. 현재 수가 Check리스트의 마지막 수보다 크다면 현재 수보다 작은 Check리스트 안의 수 모두 삭제 K -= 1 (가장 최근값(전의 값)이 현재 수보다 작다면 삭제 -> 만약..
Programmers - 조이스틱 with JAVA (+) 문제 처음에 "AAAA" 처럼 A로만 이루어진 문자열이 주어진다. 그리고 만들려고 하는 문자열이 주어진다 예를 들어, "JJJJAAAN"이라고 하자. 시작은 인덱스 0에서 시작하는데 이동 횟수와 A를 J나 N으로 바꾸는 변경 횟수의 합의 최소값을 구하는 문제이다. 아이디어 & 로직 우선, A를 다른 문자로 바꾸는 변경을 위한 횟수는 정해져있다. 다만, A에서 -1을 하면 Z이기에 해당 만들려는 글자가 Z와 가까운지 A와 가까운지 확인하면 된다. -> Math.min( 글자 - 'A' , 'Z' -글자 + 1) 이동 횟수는 항상 인덱스는 0에서 시작한다. 모든 인덱스에 대해서 경우의 수를 구하고 최소값을 구하면 된다. 예를 들어, 인덱스가 0 1 2 3 4 5 가 있다고 가정하고 3의 대한 경우의 수를 본..
Programmers - 가장 큰수 with JAVA (+) 문제 문제에는 Integer 리스트가 주어진다. 예를들어, 다음과 같이 주어진다고 가정하자. [3, 30, 34, 5, 9] 이를 조합해 가장 큰 수를 만드는 문제이다. 아이디어 & 로직 우선적으로 String으로 바꾼 후 정렬을 해주면 앞자리가 클 수록 앞으로 정렬된다. 또한 앞자리가 같다면 다음 수가 클 수록 앞에 정렬된다. 위의 예시를 String으로 바꾼 후 정렬하면 다음과 같은 결과를 얻을 수 있다. [9, 5, 34, 30, 3] 하지만 여기서 결과를 만들면 틀렸다. 왜냐하면 303보다 330이 크기 때문이다. 따라서 위와같이 그래도 정렬해서 반환하면 안된다. 조건에서 각 원소는 0부터 1000이하라고 하였다. 따라서 각 요소를 4배로 바꾸면 그 크기 비교가 더 명확해진다. 위의 예시를 4배 ..
Programmers - 디스크 컨트롤러 with JAVA 문제 문제는 우선 디스크에 처리해야하될 작업들이 수행될 것이고 문제에는 작업들마다 작업이 디스크에 들어가는 시점과 소요시간이 묶여서 디스크에 들어간다. 이제 디스크를 처리할 때, (각 작업이 걸린 시간 + 작업이 디스크에 들어오고 기다린 시간) / 총 작업의 수 의 최소를 구하는 문제이다. 아이디어 & 로직 & 코드 우선적으로 아이디어는 다음과 같다. 1. 만약 작업 대기 줄에 하나밖에 없다면 먼저 실행된다. 2. 두개 이상의 작업이 있다면 수행시간이 짧은 것을 먼저 실행시킨다. 결국에 구하는 값을 보면 총작업의 수는 고정이고 각 작업이 걸리는 시간도 고정이다 작업이 디스크에 들어오고 기다리는 시간이 짧을 수록 최소값을 구할 수 있는 구조인데, 걸리는 시간이 짧은 작업을 먼저 수행해야 다른 작업이 기다리..
Programmers - 구명보트 with JAVA 문제의 조건은 아래와 같다 1. 구명보트에는 두명까지 탈 수 있다. 2. 두사람의 몸무게의 합이 limit보다 작아야 한다. 3. 최소한의 보트를 사용하여 모든 사람을 구조한다. 로직 1. 몸무게 배열을 정렬한다. 2. 투포인터를 활용해 보트의 태울 사람을 정한다. 왼쪽의 해당하는 무게와 오른쪽의 해당하는 무게의 합이 limit이하라면 둘 다 태우고 왼쪽, 오른쪽 인덱스 모두 변경 아니라면 무거운 쪽에 해당하는 오른쪽의 무게만 태우고 오른쪽 인덱스 변경 만약 오른쪽, 왼쪽 인덱스 값이 같아진다면 한명 태우고 종료 [50, 20, 30, 70, 30, 40] 이라는 데이터가 있고 limit이 100이라고 가정한다. 정렬하면 [20, 30, 30, 40, 50, 70, 90]이 된다. 이때 왼쪽 포인터 0,..
Programmers - 베스트 엘범 with JAVA 프로그래머스에 있는 문제 중 베스트 엘범이라는 문제에 대해서 블로그를 작성하고자 한다. 문제 1. 장르에 속한 곡들의 플레이수 합이 높을 수록 먼저 출력 2. 장르에 속한 곡들 사이 플레이수가 높을 수록 먼저 출력 3. 최대 장르당 2개 출력 4. 인덱스를 출력 5. 장르에 속한 곡이 하나면 하나만 출력 해결 1. 장르별 합, 인덱스 리스트 처리 2. 합 별로 정렬 3. 해당 장르의 인덱스들 불러와 크기별로 정렬 4. 출력 (만약 장르에 속한 음악의 수가 1이면 그대로 출력) 코드 import java.util.*; class Solution { public List solution(String[] genres, int[] plays) { List answer = new ArrayList(); HashM..
Programmers - 여행경로 with JAVA 프로그래머스 문제 중 '여행경로' 문제에 대해서 블로그를 작성해보려고 한다. 우선, 입력은 다음과 같이 티켓이 주어진다. [[ICN, JFK] , [HND, IAD], [JFK, HND]] 조건은 다음과 같다. 1. 출발지는 ICN이다. 2. 모든 티켓을 사용한다. 3. 경로가 여러개라면 알파벳 순으로 정렬해서 첫번째 티켓을 출력한다. 나머지는 길이나 부가적인 조건이다. 출력은 다음과 같다. [ICN, JFK, HND, IAD] 와 같이 경로를 출력한다. 구현 1. 출발지는 ICN이다 -> for문을 돌며 티켓의 시작이 ICN이면 DFS를 돌린다. 2. 모든 티켓을 사용한다. -> DFS를 돌며 티켓의 길이가 다 찼을때, 반환시킨다. 3. 알파벳 정렬 -> 티켓이 여러개일 경우 -> String으로 나열..

티스토리툴바