// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in Java SE 11
int cnt = 0;
int cntSum = 0;
int total = 0;
for (int i = A.length - 1; i >= 0; i--) {
if (A[i] == 1) {
cnt++;
} else {
cntSum += cnt; // 2 // 3
total += cntSum; // 2 // 5
if (total > 1000000000) {
total = -1;
break;
}
cnt = 0;
}
}
return total;
}
}
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.*;
class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
int arrSize = A.length;
HashSet<Integer> hs = new HashSet<>();
for (int i = 0; i < arrSize; i++) {
hs.add(i + 1);
}
for (int i = 0; i < arrSize; i++) {
hs.remove(A[i]);
}
if (hs.isEmpty()) {
return 1;
} else {
return 0;
}
}
}
public class Solution {
// 도둑질 // 두 번째 시도(시간 초과)
public static int getMaxMoneyExceptTargetIndex(int[] money, int targetIndex) {
int[] dp = new int[money.length - 1]; // 제일 먼저 1을 뺐을 경우 2,3,1,4,2,5에서 개미전사 문제
int num1 = (targetIndex + 1) % (money.length); // 타겟 인덱스의 바로 다음 인덱스
int num2 = (targetIndex + 2) % (money.length); // 타겟 인덱스의 다음 다음 인덱스
int num3 = 0;
dp[0] = money[num1];
dp[1] = money[num2];
for (int i = 2; i < money.length - 1; i++) {
num3 = (targetIndex + i + 1) % (money.length);
dp[i] = Math.max(dp[i - 2] + money[num3], dp[i - 1]);
}
return dp[money.length - 2];
}
public static int solution(int[] money) {
int answer = 0;
int maxMoney = 0;
for (int i = 0; i < money.length; i++) {
maxMoney = Math.max(maxMoney, getMaxMoneyExceptTargetIndex(money, i)); // i번째 인덱스를 제외했을 때의 최대 값
}
answer = maxMoney;
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] money = {1, 2, 3, 1, 4, 2, 5}; // 1 빼고 2,3,1,4,2,5 개미전사 문제 // 2 빼고 3,1,4,2,5,1 개미전사 문제 // 3 빼고 1,4,2,5,1,2 개미전사 문제 // 총 7개의 값 중 max값을 return
System.out.println(solution(money));
}
}
public class Solution {
// 도둑질
// 첫 번째 시도(★ 부분으로 인해 예외 발생)
// 세 번째 시도 성공
public static int solution(int[] money) {
int answer = 0;
int[] dpExceptLast = new int[money.length - 1]; // 1, 2, 3, 1, 4, 2 담자
int[] dpExceptFirst = new int[money.length - 1]; // 2, 3, 1, 4, 2, 5 담자
dpExceptLast[0] = money[0]; // 1
// dpExceptLast[1] = money[1]; // 2 // ★ 첫 번째 풀이에서 예외가 발생했던 이유 !
dpExceptLast[1] = Math.max(money[0], money[1]); // 2 // 이게 맞지
dpExceptFirst[0] = money[1]; // 2
// dpExceptFirst[1] = money[2]; // 3 // ★ 첫 번째 풀이에서 예외가 발생했던 이유 !
dpExceptFirst[1] = Math.max(money[1], money[2]); // 3 // 이게 맞지
for (int i = 2; i < money.length; i++) {
if (i < money.length - 1) {
dpExceptLast[i] = Math.max(dpExceptLast[i - 2] + money[i], dpExceptLast[i - 1]);
}
if (i > 2) {
dpExceptFirst[i - 1] = Math.max(dpExceptFirst[i - 3] + money[i], dpExceptFirst[i - 2]);
}
}
answer = Math.max(dpExceptLast[money.length - 2], dpExceptFirst[money.length - 2]);
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] money = {1, 2, 3, 1, 4, 2, 5};
System.out.println(solution(money));
}
}
public class Solution {
// [3차] 자동완성 // 테스트 케이스 부족, 시간 초과
public static int strContainWordCnt(String[] words, String str) {
int cnt = 0;
for (String word : words) {
if (word.contains(str)) {
cnt++;
}
if (cnt > 1) return 2;
}
return cnt;
}
public static int solution(String[] words) {
int answer = 0;
String word = ""; // words 배열 속 원소
StringBuilder sb = new StringBuilder(); // 문자열 비교를 위한 StringBuilder
for (int i = 0; i < words.length; i++) { // words의 문자 하나씩 체크
word = words[i];
sb.setLength(0); // StringBuilder 초기화
for (int j = 0; j < word.length(); j++) {
sb.append(word.charAt(j));
// if (Arrays.asList(words).contains(sb.toString())) // 배열이 특정 문자열을 포함하는지 여부를 확인할 때 사용
//
// System.out.println(Collections.frequency(Arrays.asList(words), sb.toString())); // 이건 sb.toString()이 배열에 몇 개 들어있는지 체크네
//
// if (Collections.frequency(Arrays.asList(words), sb.toString()) == 1 || j == word.length() - 1) { // 특정 문자열을 포함하는 문자가 1개 남았거나, 2개 이상 남았어도 특정 문자열이 현재 i번째 word 자체인 경우
// answer += j + 1; // j는 0부터 시작했으므로 개수는 + 1
// break; // 안쪽 for문 탈출
// } else {
// continue;
// }
if (strContainWordCnt(words, sb.toString()) == 1 || j == word.length() - 1) { // 특정 문자열을 포함하는 문자가 1개 남았거나, 2개 이상 남았어도 특정 문자열이 현재 i번째 word 자체인 경우
answer += j + 1; // j는 0부터 시작했으므로 개수는 + 1
break; // 안쪽 for문 탈출
} else {
continue;
}
}
}
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] words = {"worlll","warrior","war","word","world"}; // "abc","def","ghi","jklm" // 4 // a, d, g, j만 입력하면 자동완성 가능
System.out.println(solution(words)); // 21
// "worlll","warrior","war","word","world"
// "worll" ,"warr" ,"war","word","world" // 5 + 4 + 3 + 4 + 5
// "worlll","warrior","war","word","world" // false false false false false
// "w" 입력했을 때 후보 5개 (worlll길이보다 작아)
// "wo" 입력했을 때 후보 3개 (worlll길이보다 작아)
// "wor" 입력했을 때 후보 3개 (worlll길이보다 작아)
// "worl" 입력했을 때 후보 2개 (worlll길이보다 작아)
// "worll" 입력했을 때 후보 1개(5) (worlll길이보다 작아) // true false false false false
// "w" 입력했을 때 후보 5개 (warrior길이보다 작아)
// "wa" 입력했을 때 후보 2개 (warrior길이보다 작아)
// "war" 입력했을 때 후보 2개 (warrior길이보다 작아)
// "warr" 입력했을 때 후보 1개(4) (warrior길이보다 작아) // true true false false false
// "w" 입력했을 때 후보 5개 (war길이보다 작아)
// "wa" 입력했을 때 후보 2개 (war길이보다 작아)
// "war" 입력했을 때 후보 2개 but war길이와 같아(3) // true true true false false
// "w" 입력했을 때 후보 5개 (word길이보다 작아)
// "wo" 입력했을 때 후보 3개 (word길이보다 작아)
// "wor" 입력했을 때 후보 3개 (word길이보다 작아)
// "word" 입력했을 때 후보 1개 and word길이와 같아(4) // true true true true false
// "w" 입력했을 때 후보 5개 (world길이보다 작아)
// "wo" 입력했을 때 후보 3개 (world길이보다 작아)
// "wor" 입력했을 때 후보 3개 (world길이보다 작아)
// "worl" 입력했을 때 후보 2개 (world길이보다 작아)
// "world" 입력했을 때 후보 1개 and world길이와 같아(5) // true true true true true
// 첫 번째 단어부터 마지막 단어까지 체크
// 한 단어를 앞에서부터 차례로 자르면서 더하고 그 단어가 전체 단어 배열 중 몇 개의 단어와 일치할 수 있는지 판단
// 후보가 1개이거나 or 2개 이상 존재할지라도 마지막 글자까지 잘라서 더한 상태라면(현재 단어 그 자체라면) 현재까지 자른 글자 수 카운트해서 더하기
}
}
문자열 배열 {"AB", "ABC", "BC", "ZX"} 이 있을 때 문자열 "AB"를 포함하는 원소의 개수를 알고싶을 때 배열의 길이만큼 반복하며 체크하는 방법 외에 2를 바로 리턴받을 수 있는 방법이 있을까?
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
public class Solution {
// 주차 요금 계산
public static int calcMin(String time1, String time2) {
String[] time1Arr = time1.split(":");
String[] time2Arr = time2.split(":");
int min = (Integer.parseInt(time2Arr[0]) * 60 + Integer.parseInt(time2Arr[1])) - (Integer.parseInt(time1Arr[0]) * 60 + Integer.parseInt(time1Arr[1]));
return min;
}
public static int[] solution(int[] fees, String[] records) {
int[] answer = {};
String[] tempArr = new String[3];
// 차량 번호로 기록 구분 필요
// 0000 : 06:00 IN, 06:34 OUT, 18:59 IN, 23:59 OUT // 34 + 300
// 0148 : 07:59 IN, 19:09 OUT // 670
// 5961 : 05:34 IN, 07:59 OUT, 22:59 IN, 23:00 OUT // 145 + 1
// IN과 OUT은 담을 필요없다. 기록이 짝수 개 존재하는 것이 중요하며, 이 문제에서는 무조건 IN, OUT, IN, OUT 순서이다.
HashMap<String, ArrayList<String>> hmlist = new HashMap<>();
ArrayList<String> numberList = new ArrayList<>();
for (int i = 0; i < records.length; i++) {
tempArr = records[i].split(" "); // "06:00", "0000", "IN"
if (!hmlist.containsKey(tempArr[1])) { // "0000"
hmlist.put(tempArr[1], new ArrayList<String>()); // key 등록 // "0000"
numberList.add(tempArr[1]); // key값만 담아둘 리스트 // "0000"
}
hmlist.get(tempArr[1]).add(tempArr[0]); // "06:00"
}
// numberList에 현재 넘버 리스트 담겨있음
Collections.sort(numberList); // key값 리스트 오름차순 정렬
for (String str : numberList) { // 0000, 0148, 5961
System.out.println(str);
if (hmlist.get(str).size() % 2 == 1) { // 짝이 안맞는다면, 즉 마지막 출차 기록이 없다면
hmlist.get(str).add("23:59"); // 마지막 출차 기록은 23:59로
}
}
int[] totalTimeArr = {}; // 차량 번호별 총 시간 담기 위한 배열
totalTimeArr = new int[numberList.size()]; // 시간 담을 배열 크기는 차량 번호 수만큼
answer = new int[numberList.size()]; // 금액 담을 배열 크기는 차량 번호 수만큼
String[] tempTimeArr = new String[2]; // 시간 두 개씩 잘라서 분으로 바꾸기 위한 임시 배열
int j = 0; // 차량 번호 수만큼 증가시킬 변수
for (String str : numberList) {
int i = 0; // 시간 두 개를 담기 위한 인덱스 i
int timeSum = 0;
for (String time : hmlist.get(str)) {
tempTimeArr[i] = time; // 0, 1
i++;
if (i == 2) { // 0, 1을 넘어가면
timeSum += calcMin(tempTimeArr[0], tempTimeArr[1]); // 분 계산 함수
i = 0; // 시간 두 개씩 끊기 위해 0으로 초기화
}
}
totalTimeArr[j] = timeSum; // 해당 차량 번호의 총 시간
j++; // 0 ~ 2
}
double d = 0;
for (int i = 0; i < totalTimeArr.length; i++) {
if (totalTimeArr[i] <= fees[0]) { // 180분을 넘지 않았다면
answer[i] = fees[1]; // 5000원
} else { // 180분을 초과했다면
d = (double)(totalTimeArr[i] - fees[0]) / fees[2]; // 소수점 올림을 위해 double형으로 받기
answer[i] = (int)Math.ceil(d) * fees[3] + fees[1]; // 초과한 금액 + 5000원
}
}
for (int i = 0; i <answer.length; i++) {
System.out.println(answer[i]);
}
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] fees = {180, 5000, 10, 600}; // 기본시간(분), 기본요금(원), 단위시간(분), 단위요금(원)
String[] records = {"05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN", "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"}; // 시:분 차 번호 IN/OUT // 마지막 나간 기록 없으면 23:59 나간 것으로 간주
System.out.println(solution(fees, records)); // 14600, 34400, 5000
}
}
public class Solution {
// 땅따먹기
public static int solution(int[][] land) {
int answer = 0;
int[][] sumArr = new int[land.length][land[0].length];
sumArr = land;
for (int i = 1; i < land.length; i++) { // 행
for (int j = 0; j < 4; j++) { // 열
int max = sumArr[i][j]; // 비교 대상 행의 열 값을 max로 지정
for (int z = 0; z < 4; z++) { // 비교 열
if (j == z) { // 같은 행에선 비교x
continue;
}
if (max < sumArr[i - 1][z] + land[i][j]) {
max = sumArr[i - 1][z] + land[i][j]; // 더 큰 값이 존재한다면 max값 변경
}
}
sumArr[i][j] = max; // 비교가 끝났다면 이번 행, 이번 열이 가질 수 있는 최대값 갱신
}
}
// for (int i = 0; i < land.length; i++) {
//
// for (int j = 0; j < 4; j++) {
// System.out.print(sumArr[i][j] + " ");
// }
// System.out.println();
// }
int sumMax = sumArr[sumArr.length - 1][0];
for (int i = 1; i < 4; i++) {
if (sumMax < sumArr[sumArr.length - 1][i]) {
sumMax = sumArr[sumArr.length - 1][i];
}
}
answer = sumMax;
return answer;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[][] land = {{1,2,3,5},{5,6,7,8},{4,3,2,1}};
System.out.println(solution(land)); // 16
}
}
