https://www.acmicpc.net/problem/15787 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net [풀이] 비트마스킹 유형의 문제였습니다.(물론, 비트마스킹 없이 단순 구현으로도 풀 수 있습니다.) 초기값은 0으로 두고, 좌석은 20자리이지만, 비트마스킹을 위해 21자리를 만듭니다. N개의 기차가 있으며 좌석은 1~20번째 자리가 있습니다. switch문으로 해당 명령이 어떤 것인지 구분했습니다. 특히, 3번 명령의 경우, 연산과정후, 20개의 범위 밖, 21번째에 값이 남아있으므..
https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net [풀이] 투포인터의 기본적인 문제였습니다. 주어진 M보다 크면 안되고 작아도 안되기 때문에 각 조건에 맞게 start,end 변수의 크기를 조절해야합니다. M보다 배열의 합이 작다면, start의 크기를 1증가, M보다 배열의 합이 크다면, end의 크기를 1 감소 해야합니다. 만약, M이되었다면, start와 end변수 각각 크기를 1증가, 1감소 해야합니다. 이 반복을..
https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net [풀이] 투포인터 유형의 문제였다. 0번 인덱스에서, 배열의 길이 - 1의 인덱스에서 좁혀오며 비교를 하였다. 만약, 합이 x값과 같다면 start 혹은 end를 1 더하거나 뺐다. 합이 x값보다 작다면, start 값을 1 더하고 x값보다 크다면, end 값을 1 뺐다. 이렇게 연산과정을 반복하면서 개수를 세면된다. [코드] import j..
https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net [풀이] HashMap 자료구조의 key는 주어진 문자열을, 값은 해당하는 것의 개수를 넣는 형식으로 구현했습니다. 이후, Map의 Value를 확인하면서 가장 큰 값의 value를 얻었습니다. 다음으로, Map의 key를 정렬을 한 후, Map을 돌면서, 해당하는 maxValue를 가진 key값을 반환했습니다. [코드] import java.io.BufferedReader; import ..
[풀이] 30의 배수가 되려면 먼저, 30은 2 * 5 * 3으로 되어있기에 일의 자리가 필수적으로 0이어야 합니다. 두번재로는 각 자리수의 합이 3의 배수여야 합니다. 위 두 조건을 if 조건문으로 처리후, 만약 30의 배수일 경우에는 역순으로 정렬을 하여 StringBuffer을 통해 출력하였습니다. [코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Collections; public class Main { public static void main(String[] args) throws IOExcept..
[풀이] java의 startsWith() 메소드를 이용하면 풀 수 있습니다. 하지만, startsWith() 메소드를 사용하기 이전에 정렬을 하면 시간 복잡도를 줄일 수 있습니다. 정렬을 하지 않을 경우 O^2의 시간복잡도로 모든 경우를 다 탐색해야하지만, 정렬을 할 경우에는 바로 앞, 뒤 배열의 값만 비교하면 되므로 시간초과가 나지 않습니다. 프로그래머스의 전화번호 목록 문제와 거의 비슷한 문제입니다. [코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(St..
