더 이상 물러설 곳이 없다

programmers.co.kr/learn/courses/30/lessons/42860

완성해야할 이름 String name이 주어진다.

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] 각각의 점을 꺾는 포인트로 잡고 모든 경우를 계산했다.)

주어지는 문자열의 최대 길이가 20밖에 안 되기 때문에 이 방법을 사용할 수 있었다.

시간을 너무 많이 들였다... 이렇게까지 시간을 들여서 푸는 게 의미가 있나 싶다.

솔직히 코드도 막무가내 구현 식으로 엉망인 것 같다;

programmers.co.kr/learn/courses/30/lessons/42862

전체 학생 수 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)가 가장 효율적이라고 한다.

programmers.co.kr/learn/courses/30/lessons/42842

노란색, 갈색으로 이뤄진 격자 모양의 카펫이 있다.

이 카펫의 노란색, 갈색 격자 개수가 주어질 때 카펫의 가로, 세로 크기를 배열에 담아 반환해야한다.

1. 카펫의 테두리는 모두 갈색 한 줄로 둘러싸여있고 나머지는 전부 노란색이다.

2. 가로 길이는 세로 길이와 같거다 더 길다.

3. 노란색 격자는 최소 1칸은 존재한다.

풀이 .

class Solution {
    public int[] solution(int brown, int yellow) {
        // b = 2w + 2h - 4
        //   -> w + h = (b + 4) / 2
        //   -> h < (b + 4) / 2
        // y = (w - 2) * (h - 2)

        int[] answer = new int[2];
        for(int h = 3; h < (brown + 4) / 2; h++) {  // y는 최소 1칸 -> h는 최소 3이상
            int w = (brown + 4) / 2 - h;
            if(yellow == (w - 2) * (h - 2)) {
                answer[0] = w;
                answer[1] = h;
                break;
            }
        }
        return answer;
    }
}

다른 블로그의 코드를 찾아보고 이해했다.

카펫의 형태를 유추하여 몇가지 식을 세울 수 있다.

가로는 세로보다 짧을 수 없다는 조건이 있기 때문에 h를 최소값부터 탐색하다 처음 나오는 w 값이 정답이 된다.

(w, h 값을 역전시키면 yellow에 대한 식은 맞지만 세로가 더 길어지므로 정답이 될 수 없음)

programmers.co.kr/learn/courses/30/lessons/42839

숫자 문자열 String numbers가 주어진다.

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 때문에 메모리 초과가 나지 않을까 싶긴 하지만.. 그래도 이 방법이 더 나은 듯 싶다.

programmers.co.kr/learn/courses/30/lessons/42840

세 명의 수포자가 모의고사를 치른다. 각 수포자들은 각각 다른 패턴으로 정답을 찍는다.

모의고사의 정답지 int[] answers가 주어질 때, 정답을 가장 많이 맞춘 수포자를 배열에 담아 반환해야한다.

단, 공동 1위가 나온다면 수포자 번호의 오름차순으로 담아 반환한다.

풀이 .

import java.util.*;

class Solution {
    public List<Integer> solution(int[] answers) {
        ArrayList<Integer> answer = new ArrayList<>();

        int[] a = {1, 2, 3, 4, 5};
        int[] b = {2, 1, 2, 3, 2, 4, 2, 5};
        int[] c = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};

        int[] score = new int[3];  // 각 수포자들의 점수 체크
        for(int i = 0; i < answers.length; i++) {
            if(a[i % a.length] == answers[i]) score[0]++;
            if(b[i % b.length] == answers[i]) score[1]++;
            if(c[i % c.length] == answers[i]) score[2]++;
        }

        int max = Math.max(score[0], Math.max(score[1], score[2]));
        if(max == score[0]) answer.add(1);
        if(max == score[1]) answer.add(2);
        if(max == score[2]) answer.add(3);
        return answer;
    }
}

나머지 연산을 잘 써야하는 문제.

n % m 의 결과는 0 ~ m-1만 나온다는 것을 기억하자.

i % a.length 의 결과는 0 ~ a.length-1을 반복한다. 따라서 a[]의 인덱스 범위 내에서만 반복을 돌게 된다.

programmers.co.kr/learn/courses/30/lessons/42746

숫자들의 배열 int[] numbers가 주어진다.

숫자들을 이어붙였을때(String의 합처럼) 만들 수 있는 가장 큰 수를 반환해야한다.

풀이 .

import java.util.*;

class Solution {
    public String solution(int[] numbers) {
        String[] arr = new String[numbers.length];
        for(int i = 0; i < arr.length; i++) {
            arr[i] = String.valueOf(numbers[i]);
        }

        Arrays.sort(arr, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2 + o1).compareTo(o1 + o2);  // 주의, String 끼리는 부등호 연산 사용할 수 없음
            }
        });

        // 예외처리, 맨 앞칸이 0이면 00~0의 형태. 즉, 0
        if(arr[0].equals("0")) {
            return "0";
        }

        StringBuilder sb = new StringBuilder();
        for(String str : arr) {
            sb.append(str);
        }
        return sb.toString();
    }
}

String에 대한 Comparator를 새로 만들어서 문제를 해결했다.

주의할 점은 compare()에서 반드시 compareTo()를 사용해야 한다는 점이다.

return (o1 + o2) < (o2 + o1) ? 1 : -1 을 사용하려고 했으나 String 끼리는 부등호 연산을 사용할 수 없었다.

비슷한 경우로 int 끼리는 compareTo()를 사용할 수 없다. 만약 사용하고 싶다면 Integer를 사용해야한다.

결과 출력에 굳이 StringBuilder를 사용하지 않고 + 연산으로 처리해도 된다.

하지만 시간차가 심하기 때문에 웬만해선 StringBuilder를 사용하는 것이 좋다.

programmers.co.kr/learn/courses/30/lessons/42748

int[] array, int[][] commands가 주어진다.

commands 의 각 행에는 명령을 위한 3개의 int가 들어있다.

[begin, end, K]

명령에 대한 답은 array에서 [begin번째 ~ end번째]만큼을 잘라내고 그 중 K번째로 큰 값이다.

(단, begin, end는 인덱스를 나타내지 않는다. 1부터 시작하는 순서를 나타낼 뿐이다.)

commands 의 각 명령들에 대한 답을 담은 배열을 반환해야한다.

풀이 . 

import java.util.*;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];

        int ansIdx = 0;
        for(int[] command : commands) {
            int begin = command[0];
            int end = command[1];
            int k = command[2];

            int[] temp = new int[end - begin + 1];
            int idx = 0;
            for(int i = begin - 1; i <= end - 1; i++) {  // 인덱스와 순서 혼동 주의
                temp[idx++] = array[i];
            }
            Arrays.sort(temp);
            answer[ansIdx++] = temp[k - 1];
        }

        return answer;
    }
}

 문제에서 시키는 그대로 따라하면 된다.

programmers.co.kr/learn/courses/30/lessons/42628

수행할 명령어들이 담긴 배열 String[] operations가 주어진다.

주어진 명령을 모두 수행한 뒤 남아있는 값 중 최대값, 최소값을 담은 배열을 반환해야한다.

단, 남아있는 값이 하나도 없을 경우 최대값, 최소값은 0으로 한다.

명령

I 숫자 : 숫자 입력

D 1 : 입력된 숫자 중 최대값 삭제

D -1 : 입력된 숫자 중 최소값 삭제

풀이 .

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for(String operation : operations) {
            StringTokenizer st = new StringTokenizer(operation);
            switch(st.nextToken()) {  // work
                case "I" :  // input
                    int input = Integer.parseInt(st.nextToken());
                    minHeap.add(input);
                    maxHeap.add(input);
                    break;
                case "D" :  // delete
                    if(minHeap.isEmpty()) {
                        continue;
                    }
                    if(st.nextToken().equals("1")) {  // 최대값 삭제
                        int max = maxHeap.poll();
                        minHeap.remove(max);
                    }else {  // 최소값 삭제
                        int min = minHeap.poll();
                        maxHeap.remove(min);
                    }
                    break;
            }
        }

        if(minHeap.isEmpty()) {  // 예외처리
            answer[0] = 0;
            answer[0] = 0;
        }else {
            answer[0] = maxHeap.peek();
            answer[1] = minHeap.peek();
        }
        return answer;
    }
}

최대값과 최소값을 동시에 다루기 위해 두 개의 PriorityQueue를 사용하였다.

각 명령을 두 pq에 함께 수행한 뒤 최대, 최소를 반환하면 된다.

pq.remove(Object o)가 가능한 것을 알게 되었다.

백준에선 자주 쓰이지만 프로그래머스에서 StringTokenizer 를 사용한 것은 처음이었다.

(StringTokenizer 를 사용해 " "으로 split한 문자열들을 얻을 수 있다. 다른 것으로 split 하고 싶다면 두 번째 매개변수로 줄 수 있다.)