N을 사용해 만든 사칙연산 식의 결과가 number이 되도록 할 때 N의 최소 사용횟수를 반환해야한다.
1. NN의 형태는 N을 두 번 사용한 것이다. ex : 55 -> 5를 두 번 사용)
2. 최소값이 8보다 클 경우 -1을 반환한다.
풀이 .
class Solution {
int answer = -1;
public void dfs(int cnt, int calc, int N, int number) {
if(calc == number) {
if(answer == -1 || answer > cnt) { // 정답이 한 번도 들어온 적이 없거나 최소값을 갱신한 경우
answer = cnt;
}
return;
}
int temp = N;
for(int i = 1; i <= 8 - cnt; i++) { // N이 8개까지만 사용되도록 함
dfs(cnt + i, calc + temp, N, number);
dfs(cnt + i, calc - temp, N, number);
dfs(cnt + i, calc * temp, N, number);
dfs(cnt + i, calc / temp, N, number);
temp = temp * 10 + N; // N을 하나 더 붙임
}
}
public int solution(int N, int number) {
dfs(0, 0, N, number);
return this.answer;
}
}
분류는 DP이지만 DFS로 풀었다. 솔직히 어떻게 DP로 풀 수 있는지도 모르겠다.
int cnt를 사용해 반복문 내에서 사용할 수 있는 N의 개수를 제한했다.
정답 처리는 됐지만 사실 틀린 코드이다.
5*5+5/5 처럼 사칙연산의 규칙에 의해 연산자의 순서보다 *, / 연산자를 먼저 계산하는 경우는 고려할 수 없기 때문이다.
문제에 "연산자는 무조건 들어온 순서대로 계산된다." 라는 조건이 있어야만 온전히 정답일 수 있는 코드.
사람들의 몸무게가 담긴 int[] people, 구명보트가 버틸 수 있는 최대 무게 int limit 가 주어진다.
구명보트를 사용해 모든 사람을 옮기기 위해 최소 몇 번을 태워야 하는지 반환해야한다.
1. limit은 사람들 중 가장 무거운 사람보다 항상 크게 주어지기 때문에 모두 옮기는 것은 불가능한 경우는 없다.
2. 보트에는 한 번에 2명 까지만 탈 수 있다. (무게가 남더라도)
풀이 .
import java.util.*;
class Solution {
public int solution(int[] people, int limit) {
int answer = 0;
int min = 0;
Arrays.sort(people);
// 몸무게가 가장 무거운 사람부터 판단한다.
for(int max = people.length - 1; min <= max; max--) {
if(people[max] + people[min] > limit) // 가장 작은 수와 함께 탈 수 없다면 가장 큰 수는 반드시 혼자 타야만 한다
answer ++; // 가장 큰 수 먼저 보낸다. min은 그대로 유지하면서 max만 변경한다
else {
answer ++; // 둘을 같이 보낸다
min ++;
}
}
return answer;
}
}
처음에 생각한 방식은 위 코드와 달랐다.
max 부터 검사를 실시하는 건 동일했지만 min과의 짝은 맨 마지막에 검사했다.
(max, max-1), (max, max-2), ... , (max, min) 순으로 검사했다는 이야기.
이유는, 가장 좋은 카드인 min을 처음부터 써버리는 것 보다는.. 무거운 쌍부터 검사해보고 전부 안 될 경우에서야 (max, min) 을 태워 보내는 것이 효율적일 거라고 생각했다.
(가장 좋은 카드인 min을 최대한 아껴놨다는 느낌? min이 나중에 더 요긴하게 사용될 수도 있으니까)
하지만 이런식으로 짰더니 시간초과가 났다.
O(n^2) 이고 n=50,000 이기 때문에 가능할 거라고 생각했는데 아니었다.
(50,000 = 5 * 10^4 = 25 * 10^8 = 25 * 1억 이고 25를 상수로 날리면 1억은 1초에 들어오니까. 근데 이게 틀린 계산이었다. 식은 전개하기 전에 n 앞에 상수가 붙어있을때나 날릴 수 있는거지 전부 전개하고 나서 내 마음대로 25를 날려버린 게 틀렸다.)
number 에서 숫자를 k개 제거했을 때 나올 수 있는 수의 최대값을 String으로 반환해야한다.
(단, number 안에서 유지되는 숫자들의 순서가 바뀌면 안 된다. number의 수들로 가장 큰 조합을 찾아내는 게 아니라는 뜻)
풀이 1.
class Solution {
public String solution(String number, int k) {
// StringBuilder 안 쓰면 시간초과
StringBuilder sb = new StringBuilder();
// j의 범위에 1씩 증가하는 i를 더하는 이유는 뽑아야 하는 숫자가 number.length()-k개에서 하나씩 줄어들기 때문
// 예를들어 length : 7, k : 3 이라면 새로 뽑아야 하는 수는 총 4개
// 즉, 늦어도 [k] 에서는 첫번째 수를 뽑아야 하나는 것
// 이는 다시말하면 뒤에서부터 3개(length - k - 1)는 남겨놓고 나머지 범위에서 하나를 뽑아야 한다는 것
// 숫자를 하나씩 뽑을 때마다 뒤에 남겨놔야 하는 수의 개수도 하나씩 줄어든다.
// 그래서 1씩 증가하는 i를 더해준다
int next = 0;
for(int i = 0; i < number.length() - k; i++) {
char max = '0';
for(int j = next; j <= k + i; j++) {
if(max < number.charAt(j)) {
max = number.charAt(j);
next = j + 1; // 다음 자리수를 선택할 범위의 시작점은 이전 자리수를 선택한 바로 다음으로 잡는다
}
}
sb.append(max);
}
return sb.toString();
}
}
혼자서 답을 생각하지 못하고 다른이의 코드를 참고했다. ( O(n^2) 의 시간 복잡도 )
k개의 숫자를 제거해야한다. 다시말해 number.length - k 개의 숫자를 뽑아야 한다.
각 자리의 숫자를 어디에서 뽑을지 범위를 특정할 수 있다.
(특정 가능한 범위에서 그때마다 가장 큰 수를 뽑으면 되기 때문에 그리디)
첫번째 자리수를 뽑으려면 일단 뒤에서부터 number.length - k - 1 개는 남겨두어야 한다. 그렇지 않으면 남아있는 모든 수를 다 뽑아도 number.length - k 개를 채우지 못할 수도 있기 때문.
이를 풀어서 다시 말하면 첫번째 자리 수는 반드시 [0] ~ [k] 에서 나와야 한다.
이 범위에서 가장 큰 수를 골라 첫번째 자리수로 삼는다.
두번째 자리는 첫번째 자리를 뽑은 바로 다음 인덱스부터 탐색해야한다.(int next) 이번에는 뒤에서부터 number - k - 2 개를 남겨두어야 한다. (뽑은 숫자가 늘어날 때마다 뒤에서부터 남겨둬야 하는 숫자의 개수는 줄어든다)
즉, i 번째 수를 뽑는 반복 for ( int i ) 를 한 번 돌 때마다 그 안에서 실질적으로 i 번째 수를 찾는 역할을 하는 for ( int j )의 범위에 +i 를 해주어야 한다.
다시 말하면 탐색 범위의 끝 인덱스는 [k], [k+1], [k+2] ... 이렇게 늘어난다는 이야기.
풀이 2.
import java.util.Stack;
class Solution {
public String solution(String number, int k) {
char[] result = new char[number.length() - k];
Stack<Character> stack = new Stack<>();
for (int i=0; i<number.length(); i++) {
char c = number.charAt(i);
while (!stack.isEmpty() && stack.peek() < c && k-- > 0) {
stack.pop();
}
stack.push(c);
}
for (int i=0; i<result.length; i++) {
result[i] = stack.get(i);
}
return new String(result);
}
}
'다른 사람의 풀이' 에서 보고 배운 코드이다. ( O(n) 의 시간 복잡도 )
문자열을 반복을 돌면서 전부 스택에 집어넣는다.
이때 새로 들어오는 문자가 가장 최근에 들어온 문자보다 크다면 최근에 들어온 문자는 빼버린다.
A를 name.length()만큼 이어붙인 문자열에서 name을 만들기 위해 필요한 최소 이동값을 반환해야한다.
1. 최초 커서는 첫 번째 칸에 위치한다. 좌 or 우 한 번의 이동으로 옆 칸으로 이동이 가능하다.
2. 커서가 위치한 문자를 위 or 아래 이동을 통해 변경할 수 있다. (ex : A위 -> B, A아래 -> Z)
풀이 1. (틀린 코드지만 정답처리됨)
import java.util.*;
class Solution {
public int solution(String name) {
int answer = 0;
// 문제의 설명은 AAA -> JAN으로 만들어야 하는 것이지만
// 코드는 JAN -> AAA으로 만드는 식으로 짰다
ArrayList<Boolean> check = new ArrayList<Boolean>(Arrays.asList(new Boolean[name.length()]));
Collections.fill(check, Boolean.FALSE);
for(int i = 0; i < check.size(); i++) {
if(name.charAt(i) == 'A') { // A인 것은 true, 나머지는 전부 false로 봤다
check.set(i, true);
}
}
int cursor = 0; // 커서를 옮겨가며 진행
while(check.contains(false)) {
// 커서가 위치한 곳이 A가 아니라면 A로 만들어주면서 카운트
if(check.get(cursor) == false) {
int upCnt = name.charAt(cursor) - 'A';
int downCnt = 25 - upCnt + 1;
if(upCnt < downCnt) { // 위, 아래 중 최소경로를 적용
answer += upCnt;
}else {
answer += downCnt;
}
check.set(cursor, true); // A로 만들어줌
}
// 커서를 왼쪽, 오른쪽 중 어디로 이동할 것인가?
int left = cursor - 1, leftCnt = 1;
int right = cursor + 1, rightCnt = 1;
while(check.contains(false)) { // A가 아닌 문자를 찾을 때까지 좌우 번갈아가며 검사
// 인덱스 범위 벗어나는 이동에 대한 처리
if(left == -1) {
left = name.length() - 1;
}
if(right == name.length()) {
right = 0;
}
// 양 옆의 문자를 한칸씩 확인하여 A가 아닌 것이 있다면 그쪽으로 이동
// 한칸씩 번갈아가며 화인한다고 하더라도 그 한 칸을 왼,오 어느쪽부터 볼 것인지를 선택해야한다
// 어떻게 선택해야할지 모르겠어서 그냥 오른쪽 먼저 검사하는 것으로 했다
// ex : (B)(Cursor)(B) 일 때 오른쪽을 우선으로 이동
if(check.get(right) == false) {
cursor = right;
answer += rightCnt;
break;
}
if(check.get(left) == false) {
cursor = left;
answer += leftCnt;
break;
}
left--; leftCnt++;
right++; rightCnt++;
}
}
return answer;
}
}
(문제의 설명은 AAA -> JAN으로 만들어야 하는 것이지만 코드는 JAN -> AAA으로 만드는 식으로 짰다)
커서를 하나 두고 A가 아닌 곳을 찾아 이동해가며 문자를 변경했다.
커서가 위치한 곳에서 왼쪽, 오른쪽 방향으로 A가 아닌 문자가 가장 가깝게 위치한 곳을 다음 커서로 삼았다.
이때 커서 양 옆에 동일한 간격으로 A가 아닌 문자가 존재할 때 문제가 발생한다.
왼쪽, 오른쪽 어느 방향에 우선순위를 둬야할지 기준이 모호한 것이다.
잘 모르겠어서 그냥 에라 모르겠다 하고 오른쪽에 우선순위를 두고 풀었다.
정답처리가 되긴 했지만 결과적으로 틀린 코드이다. 프로그래머스의 테스트케이스가 부실해서 틀린 코드도 정답처리가 되어버렸다.
(반례)
ABBAAAAAAAAAB 정답 7 -> 8 나온다
BABAAAAAAAAAAAABAAAB 정답 13 -> 15 나온다
풀이 2. (정답 코드)
import java.util.*;
class Solution {
public int solution(String name) {
int answer = 0;
ArrayList<Integer> ansList = new ArrayList<>();
ArrayList<Character> cList = new ArrayList<>();
for (int i = 0; i < name.length(); i++) {
cList.add(name.charAt(i));
}
// 일단 위아래 이동부터
int upDown = 0;
for (int i = 0; i < cList.size(); i++) {
char ch = cList.get(i);
int upCnt = ch - 'A';
int downCnt = 26 - upCnt;
upDown += Math.min(upCnt, downCnt);
}
// 쭉 오른쪽
int rightAns = 0, lastRightIndex = 0;
for (int i = cList.size() - 1; i >= 0; i--) {
if (cList.get(i) != 'A') {
lastRightIndex = i;
break;
}
}
rightAns = lastRightIndex;
ansList.add(upDown + rightAns);
// 쭉 왼쪽
int leftAns = 0, lastLeftIndex = 0;
for (int i = 1; i < cList.size(); i++) {
if (cList.get(i) != 'A') {
lastLeftIndex = i;
break;
}
}
leftAns = cList.size() - lastLeftIndex;
ansList.add(upDown + leftAns);
// 오른쪽 가다가 왼쪽
lastLeftIndex = 0; // i보다 큰 인덱스 중에서 가장 왼쪽에 있는 A가 아닌 인덱스
for (int i = 1; i < cList.size(); i++) { // i : 방향전환점
int leftRight = i * 2; // i까지 이동했다 다시 [0]으로 돌아옴
for (int j = i + 1; j < cList.size(); j++) { // lastLeftIndex 찾기
if (cList.get(j) != 'A') {
lastLeftIndex = j;
break;
}
}
leftRight += cList.size() - lastLeftIndex;
ansList.add(upDown + leftRight);
}
// 왼쪽 가다가 오른쪽
lastRightIndex = 0;
for (int i = 1; i < cList.size(); i++) {
int leftRight = (cList.size() - i) * 2; // i까지 이동했다 다시 [0]으로 돌아옴
for (int j = i - 1; j >= 1; j--) {
if (cList.get(j) != 'A') {
lastRightIndex = j;
break;
}
}
leftRight += lastRightIndex;
ansList.add(upDown + leftRight);
}
answer = Collections.min(ansList);
return answer;
}
}
(문제의 설명은 AAA -> JAN으로 만들어야 하는 것이지만 코드는 JAN -> AAA으로 만드는 식으로 짰다)
일단 좌우 이동을 신경쓰기 전에 문자를 변경하는 데 사용되는 위아래 이동부터 한꺼번에 먼저 체크했다.
그 이후 좌우 이동을 체크했는데, 이동 가능한 모든 경로에 대한 이동수를 저장하여 그 중 최소값으로 정답을 찾아냈다.
아래와 같은 네 가지 경로로 이동이 가능하다.
1. 처음부터 쭉 오른쪽으로만 가기
2. 처음부터 쭉 왼쪽으로만 가기
3. 처음엔 오른쪽으로 가다가 중간에 꺾어서 왼쪽으로 가기
4. 처음엔 왼쪽으로 가다가 중간에 꺾어서 오른쪽으로 가기
1, 2번 경우의 이동 수는 그냥 인덱스를 계산하여 쉽게 구할 수 있다.
문제는 3, 4번 경우인데, "중간에 꺾어서"의 중간점을 어디로 잡아야 하는지였다.
이것도 그냥 다 해봤다. ( [1] ~ [size()-1] 각각의 점을 꺾는 포인트로 잡고 모든 경우를 계산했다.)
전체 학생 수 int n, 체육복을 도둑맞은 학생 번호 int[] lost, 여벌 체육복을 가져온 학생 번호 int[] reserve 가 주어진다.
도둑맞은 학생들이 여벌을 가져온 학생들에게 체육복을 빌려 입었을 때 체육수업에 가장 많이 참여할 수 있는 학생의 수를 반환해야한다.
단, 여벌을 가져온 학생은 자신의 앞, 뒤 번호 학생에게만 빌려줄 수 있다. (ex : 4번은 3, 5번에게만 빌려줄 수 있다.)
(여벌을 가져온 학생이 체육복을 도난당했을 경우 1개만 도난당한 것으로 한다.)
풀이 .
import java.util.*;
class Solution {
public int solution(int n, int[] lost, int[] reserve) {
int answer = 0;
// 일단 정렬
List<Integer> lostList = new ArrayList<>();
List<Integer> reserveList = new ArrayList<>();
for (int num : lost) lostList.add(num);
for (int num : reserve) reserveList.add(num);
Collections.sort(lostList);
Collections.sort(reserveList);
// 여벌을 가져왔어도 도난당했다면 빌려줄 수 없다
for (int i = 0; i < reserveList.size(); i++) {
int num = reserveList.get(i);
if (lostList.contains(num)) {
lostList.remove((Integer) num); // remove(Object o) 사용
reserveList.remove((Integer) num);
i--; // 인덱스 당겨줘야 함
}
}
// 작은 번호에게 우선적으로 빌려준다
for (int num : reserveList) {
if (lostList.contains(num - 1)) {
lostList.remove((Integer)(num - 1));
continue;
}
if (lostList.contains(num + 1)) {
lostList.remove((Integer)(num + 1));
continue;
}
}
answer = n - lostList.size();
return answer;
}
}
여벌을 가져온 사람은 나보다 1 작은, 나보다 1 큰 사람에게 빌려줄 수 있다.
이때 무조건 나보다 작은 사람을 우선적으로 빌려주는 식으로 진행하면 된다.
반복을 돌리기 위해 정렬을 먼저 해주고 도난, 여벌 동시에 해당되는 놈들을 목록에서 제거해준다.
(주의)
ArrayList에는 remove(int index), remove(Object o) 두 가지 remove가 있다.
ArrayList<Integer> 에서는 remov(숫자)를 사용하면 무조건 remove(int index)가 호출된다.
(이것 때문에 OutOfBoundsException이 발생했다.)
remove(Object o)를 사용하고 싶다면
remove(Integer.valueOf(int)), remove(new Integer(int)) or remove((Integer) int) 세 가지 방법을 사용할 수 있다.
이유는 모르지만 마지막의 remove((Integer) int)가 가장 효율적이라고 한다.
numbers를 이루는 각 숫자들로 만들 수 있는 모든 숫자들의 조합에서 소수가 몇 개인지 반환해야한다.
단, 11과 011은 같은 것으로 치고 하나만 센다.
풀이 1.
import java.util.*;
class Solution {
ArrayList<Integer> pList = null;
boolean[] check = null;
int ans = 0;
public boolean isPrime(int num) {
if(num == 2 && !pList.contains(num)) {
pList.add(num);
return true;
}
if(num == 0 || num == 1 || num % 2 == 0 || pList.contains(num)) {
return false;
}
for(int i = 3; i <= Math.sqrt(num); i+=2) {
if(num % i == 0) {
return false;
}
}
pList.add(num);
return true;
}
public void dfs(int dept, int deptNow, String comb, String numbers) {
if(dept == deptNow) { // 목표 자리수에 도달했다면 prime 검사 후 return
int num = Integer.parseInt(comb);
if(isPrime(num)) {
this.ans++;
}
return;
}
// 백트래킹을 통해 모든 조합 구현
for(int i = 0; i < numbers.length(); i++) {
if(check[i] == false) {
String temp = comb; // 다시 돌아오기 위해 저장
comb += String.valueOf(numbers.charAt(i));
check[i] = true;
dfs(dept, deptNow + 1, comb, numbers);
// 백트래킹
comb = temp;
check[i] = false;
}
}
}
public int solution(String numbers) {
int answer = 0;
pList = new ArrayList<>();
check = new boolean[numbers.length()];
// 1~number.length() 모든 자리수의 조합을 구한다
for(int i = 1; i <= numbers.length(); i++) {
dfs(i, 0, "", numbers);
}
answer = this.ans;
return answer;
}
}
주어진 문자열로 만들어낼 수 있는 모든 조합을 구한다.
조합이 하나 완성될 때마다 소수에 해당되는지 검사한다.
1. 소수 검사
기본적으로 나머지 연산을 사용한다. 이때 1 ~ num을 모두 나머지 연산 하는 것은 비효율적이다.
0, 1, 2에 대한 검사를 마친 후 3~num^(1/2) 까지만 검사하면 된다. 왜인지는 모른다.
2. 조합 생성
백트래킹을 사용하여 구할 수 있는 모든 조합을 구했다.
조금 걸리는 부분이 있는데.. 이렇게 짜면 number = "444333" 이렇게 같은 숫자가 반복되는 String이 주어졌을 때 똑같은 조합을 여러번 구하는 낭비가 일어난다.
444333이란 조합은 총 36개가 나오게 된다. (3! * 3!)
이 문제에서는 numbers의 최대길이는 7이고 7! = 5040 개의 초합이 최대이기 때문에 시간초과는 나지 않지만 n이 조금만 더 커지면 굉장히 불안해진다..
어떻게 해결할 지 생각해 봐야겠다.
풀이 2.
// 백트래킹을 통해 모든 조합 구현
ArrayList<Character> used = new ArrayList<>();
for(int i = 0; i < numbers.length(); i++) {
// 다음 숫자가 이번 자리수에서 쓰인 적 있는지 검사
if(used.contains(numbers.charAt(i))) continue;
if(check[i] == false) {
String temp = comb; // 다시 돌아오기 위해 저장
comb += String.valueOf(numbers.charAt(i));
used.add(numbers.charAt(i)); // 이번 자리수에서 사용된 숫자 표시
check[i] = true;
dfs(dept, deptNow + 1, comb, numbers);
// 백트래킹
comb = temp;
check[i] = false;
}
}
위 코드에서 dfs()에 코드 몇 줄을 추가하여 효율성 문제를 해결했다. (수정 전에도 시간초과 안 뜨긴 했지만)
각각의 dfs()는 deptNow번째 자리수에 새로운 숫자를 집어넣고 deptNow+1 번째 자리수로 재귀한다.
이때 각 dfs()마다 ArrayList를 두어 해당 자리수에서 한 번 사용된 숫자는 다시 사용될 수 없도록 하여 중복조합의 경우를 모두 제거했다.
n이 커질 경우 이를 통해 시간을 대폭 감소시킬 수 있다.
반복해서 생성되는 ArrayList 때문에 메모리 초과가 나지 않을까 싶긴 하지만.. 그래도 이 방법이 더 나은 듯 싶다.