프로그래머스: 튜플

2020/06/29

문제

https://programmers.co.kr/learn/courses/30/lessons/64065

코드

public int[] solution(String s) {
    String[] strArray = getStringArray(s);
    List<Integer[]> list = convertStringArrayToIntegerArrayList(strArray);
    sortByArraylength(list);

    List<Integer> tuple = getTuple(list);
    int[] answer = convertIntegerArrayToIntArray(tuple);

    return answer;
}

private String[] getStringArray(String s) {
    String[] array = s.substring(2, s.length()-2).replace("},{", "@").split("@");

    return array;
}

private List<Integer[]> convertStringArrayToIntegerArrayList(String[] strArray) {
    List<Integer[]> list = new ArrayList<>();
    for (String str : strArray) {
        String[] stringNumbers = str.split(",");
        Integer[] array = convertStringArrayToIntegerArray(stringNumbers);

        list.add(array);
    }

    return list;
}

private Integer[] convertStringArrayToIntegerArray(String[] stringNumbers) {
    Integer[] array = new Integer[stringNumbers.length];
    int i = 0;
    for (String str2 : stringNumbers) {
        array[i++] = Integer.parseInt(str2);
    }

    return array;
}

private void sortByArraylength(List<Integer[]> list) {
    Collections.sort(list, new Comparator<Integer[]>() {
        @Override
        public int compare(Integer[] o1, Integer[] o2) {
            return o1.length - o2.length;
        }
    });
}

private List<Integer> getTuple(List<Integer[]> list) {
    List<Integer> tuple = new ArrayList<>();

    for (int i = 0; i < list.size(); i++) {
        Integer[] elements = list.get(i);

        for (Integer element : elements) {
            if (!tuple.contains(element)) {
                tuple.add(element);
            }
        }
    }

    return tuple;
}

private int[] convertIntegerArrayToIntArray(List<Integer> list) {
    int[] answer = new int[list.size()];
    int j = 0;
    for (int i : list) {
        answer[j++] = i;
    }

    return answer;
}

흐름

문자열을 각각 숫자를 저장한 문자열 배열로 만든다. (getStringArray)
만든 문자열 배열에 저장된 문자열을 “,”로 나눠서 각각 Integer 배열에 저장하고 그 Integer 배열을 담는 List에 저장한다. (convertStringArrayToIntegerArrayList)
List에 저장된 Integer 배열을 배열의 길이가 짧은 순으로 sorting 한다. (sortByArraylength)
정렬한 list를 돌면서 Integer 배열을 꺼내고 다시 배열을 돌면서 튜플을 저장할 List에 담는데, 이 때 저장하기 전에 이미 List에 저장된 숫자인 경우엔 담을 필요가 없으므로 contain() 를 사용해서 List에 저장되지 않은 숫자만 add 한다.
List형 이었으므로 문제에 맞게 int 배열 형으로 변환해서 return한다.
끝

최다 좋아요 코드

public int[] solution(String s) {
    Set<String> set = new HashSet<>();
    String[] arr = s.replaceAll("[{]", " ").replaceAll("[}]", " ").trim().split(" , ");
    Arrays.sort(arr, (a, b)->{return a.length() - b.length();});
    int[] answer = new int[arr.length];
    int idx = 0;
    for(String s1 : arr) {
        for(String s2 : s1.split(",")) {
            if(set.add(s2)) answer[idx++] = Integer.parseInt(s2);
        }
    }
    return answer;
}

마찬가지로 우선 String을 String[]로 만들고
배열 길이 순으로 정렬한 다음에
2중 for문을 돌면서 숫자를 배열에 저장하는데,
Set을 통해 이미 저장된 숫자는 저장하지 않는다.

결과

번호	속도
테스트 1	통과 (2.12ms, 52.3MB)
테스트 2	통과 (2.16ms, 52.2MB)
테스트 3	통과 (2.03ms, 50.3MB)
테스트 4	통과 (2.58ms, 52.4MB)
테스트 5	통과 (6.02ms, 52.4MB)
테스트 6	통과 (7.96ms, 50.9MB)
테스트 7	통과 (38.39ms, 53.8MB)
테스트 8	통과 (68.47ms, 61.7MB)
테스트 9	통과 (51.85ms, 57.6MB)
테스트 10	통과 (142.71ms, 62.2MB)
테스트 11	통과 (91.56ms, 65.7MB)
테스트 12	통과 (111.69ms, 74.1MB)
테스트 13	통과 (104.26ms, 72.1MB)
테스트 14	통과 (113.99ms, 74.5MB)
테스트 15	통과 (1.84ms, 50MB)

테스트 케이스

assertArrayEquals(new int[]{2,1,3,4}, test.solution("{{2},{2,1},{2,1,3},{2,1,3,4}}"));
assertArrayEquals(new int[]{2,1,3,4}, test.solution("{{1,2,3},{2,1},{1,2,4,3},{2}}"));
assertArrayEquals(new int[]{111,20}, test.solution("{{20,111},{111}}"));
assertArrayEquals(new int[]{123}, test.solution("{{123}}"));
assertArrayEquals(new int[]{3,2,4,1}, test.solution("{{4,2,3},{3},{2,3,4,1},{2,3}}"));
assertArrayEquals(new int[]{3,2,4,1,100}, test.solution("{{4,2,3},{3},{2,3,4,1},{2,3},{2,3,4,1,100}}"));
assertArrayEquals(new int[]{3,2,4,1,100}, test.solution("{{4,2,3},{3},{2,3,4,1},{2,3},{2,3,4,1,100}}"));

댓글 공유

프로그래머스: 숫자의 표현

2020/06/28

문제

https://programmers.co.kr/learn/courses/30/lessons/12924

코드

삽질 코드

public int solution(int n) {
    int answer = 0;
    int[] sumArray = new int[n + 1];

    Queue<Integer> queue = initQueue(n);

    int sum = 0;
    for (int i = 1; i < n + 1; i++) {
        sum += i;
        sumArray[i] = sum;

        if (sum == n) {
            ++answer;

            int nextValue = i+1;

            while (!queue.isEmpty()) {
                int sumValue = sumArray[queue.peek()];

                if (nextValue <= sumValue) {
                    i = queue.peek();
                    sum = 0;
                    break;
                }

                queue.poll();
            }
        } else if (sum > n) {
            int value = sum - n;

            while (!queue.isEmpty()) {
                int sumValue = sumArray[queue.peek()];

                if (value <= sumValue) {
                    i = queue.poll();
                    sum = 0;
                    break;
                }

                queue.poll();
            }
        }
    }

    return answer;
}

합계를 저장 할 array와 배열의 index를 저장 할 queue를 생성하고 queue에 index를 순서대로 할당해놓는다.
i를 증가 시키면서 sum을 저장하고 sum == n 이 되면 answer을 증가시키고, 그 다음 index의 값을 구해서 그 다음 값 만큼 이전에 더한 값들을 빼고 뺀 값 다음 index부터 실행하기 위해 index를 queue에서 가져온다.
- 1 + 2 + 3 + 4 + 5 = 15 였으면 다음 값은 6 이므로 6을 만큼을 빼기 위해 1, 2 3을 뺀다.
sum이 n보다 크다면 sum에서 n을 뺀 값 만큼 더했던 값에서 빼고 뺀 값 다음 index부터 실행하기 위해 index를 queue에서 가져온다.
- 5 + 6 + 7 = 18 이므로 15를 뺀 3보다 크거나 같은 값을 앞에서부터 빼야되는데 5는 이미 3보다 크므로 5를 queue에서 poll해서 뺀다.
위를 반복해서 연속된 자연수의 개수를 구한다.
끝

숫자가 커지면 반복 할 때 효율성에서 걸릴까 싶어서 큐도쓰고 해봤는데 보기도 안좋고 속도도 안좋고 모든 면에서 안좋았다

정석 코드

public int solution(int n) {
    int answer = 0;

    for(int i = 1; i <= (n / 2) ; i++) {
        int sum = 0;
        int index = i;

        while (sum < n) {
            sum += index;
            ++index;
        }

        if (sum == n) {
            ++answer;
        }
    }

    return answer + 1;
}

n의 절반을 넘어가면 그 이상 더 해봤자 n을 넘어가므로 n / 2까지만 반복한다.
sum이 n 보다 작으면 반복해서 sum에 index를 증가시켜 가며 더한다.
sum이 n보다 작지 않아지면 빠져나와서 sum == n이 판단하고 같으면 answer을 증가시킨다.
마지막에 자기자신이 들어가므로 + 1을 하고 return한다.

결과

뻘짓 코드

정확성

번호	속도
테스트 1	통과 (1.02ms, 52.4MB)
테스트 2	통과 (2.01ms, 50.3MB)
테스트 3	통과 (1.64ms, 52.5MB)
테스트 4	통과 (1.83ms, 50.7MB)
테스트 5	통과 (1.13ms, 52.5MB)
테스트 6	통과 (0.95ms, 52.5MB)
테스트 7	통과 (1.68ms, 52.3MB)
테스트 8	통과 (1.41ms, 50.1MB)
테스트 9	통과 (0.93ms, 50MB)
테스트 10	통과 (2.25ms, 52.8MB)
테스트 11	통과 (2.15ms, 50.5MB)
테스트 12	통과 (1.78ms, 52.6MB)
테스트 13	통과 (1.86ms, 52MB)
테스트 14	통과 (1.68ms, 52.7MB)

효율성

번호	속도
테스트 1	통과 (9.68ms, 52.5MB)
테스트 2	통과 (6.16ms, 52.2MB)
테스트 3	통과 (7.96ms, 52MB)
테스트 4	통과 (7.72ms, 51MB)
테스트 5	통과 (8.29ms, 50.6MB)
테스트 6	통과 (10.67ms, 52.4MB)

정석 코드

정확성

번호	속도
테스트 1	통과 (0.77ms, 50.2MB)
테스트 2	통과 (0.94ms, 50.6MB)
테스트 3	통과 (0.81ms, 50.4MB)
테스트 4	통과 (0.86ms, 51MB)
테스트 5	통과 (0.80ms, 52.1MB)
테스트 6	통과 (0.77ms, 52.2MB)
테스트 7	통과 (0.90ms, 52.5MB)
테스트 8	통과 (0.84ms, 52.4MB)
테스트 9	통과 (0.69ms, 50.2MB)
테스트 10	통과 (0.87ms, 52.2MB)
테스트 11	통과 (0.91ms, 52.1MB)
테스트 12	통과 (0.89ms, 52.3MB)
테스트 13	통과 (0.79ms, 50.4MB)
테스트 14	통과 (0.84ms, 50.2MB)

효율성

번호	속도
테스트 1	통과 (1.48ms, 52.9MB)
테스트 2	통과 (1.12ms, 52.2MB)
테스트 3	통과 (1.21ms, 50.8MB)
테스트 4	통과 (1.28ms, 50MB)
테스트 5	통과 (1.52ms, 50.1MB)
테스트 6	통과 (1.50ms, 52.3MB)

테스트 케이스

assertEquals(4, test.solution(15));
assertEquals(2, test.solution(20));
assertEquals(4, test.solution(30));
assertEquals(2, test.solution(106));
assertEquals(2, test.solution(1567));
assertEquals(1, test.solution(16));
assertEquals(4, test.solution(782));
assertEquals(5, test.solution(10000));
assertEquals(12, test.solution(9999));
assertEquals(4, test.solution(7787));
assertEquals(8, test.solution(4578));
assertEquals(2, test.solution(1234));
assertEquals(1, test.solution(1));
assertEquals(2, test.solution(5));
assertEquals(3, test.solution(49));

P.S

주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는 주어진 수의 홀수 약수의 개수와 같다.

이 문제의 최다 좋아요를 받은 코드는 위의 정수론 정리를 이용한 풀이가 있는데 정의의 출처를 찾지 못했다.
해당 정의를 가지고 푼 코드가 가장 짧고 가장 빠르게 실행된다.
한참 멀었구나 싶다.

댓글 공유

프로그래머스: 피보나치 수

2020/06/27

문제

https://programmers.co.kr/learn/courses/30/lessons/12945

코드

private static final int DIVIDE_NUMBER = 1234567;

public int solution(int n) {
    int[] cache = new int[n+1];

    cache[1] = 1;

    for (int i = 2; i < n+1; i++) {
        cache[i] = ((cache[i-1]) % DIVIDE_NUMBER + (cache[i-2]) % DIVIDE_NUMBER) % DIVIDE_NUMBER;
    }

    int answer = cache[n];
    return answer;
}

흐름

n+1 크기 배열을 생성하는데 이 때 이번 문제에서 n은 1 <= n <= 100,000 이하이다.
n이 1 일땐 1을 return 해야하므로 배열 1 번째엔 1을 할당 해놓아야 한다.
2부터 n + 1 까지 반복하면서 피보나치 수열 계산하는 것 처럼 i - 1, i - 2 배열에 저장된 값을 더하는데
문제에서 1234567을 나눈 나머지 값을 return 하라고 하였으므로 % 1234567을 해준다.
cache 배열에서 n 번째에 있는 값을 return하면 끝

결과

번호	속도
테스트 1	통과 (0.85ms, 52.8MB)
테스트 2	통과 (0.80ms, 52.2MB)
테스트 3	통과 (0.78ms, 51.3MB)
테스트 4	통과 (0.81ms, 53.1MB)
테스트 5	통과 (0.84ms, 52.6MB)
테스트 6	통과 (0.85ms, 50.3MB)
테스트 7	통과 (0.95ms, 52.4MB)
테스트 8	통과 (0.86ms, 50.5MB)
테스트 9	통과 (0.86ms, 52MB)
테스트 10	통과 (0.89ms, 51.4MB)
테스트 11	통과 (0.84ms, 51MB)
테스트 12	통과 (0.86ms, 52.4MB)
테스트 13	통과 (3.99ms, 52.7MB)
테스트 14	통과 (3.98ms, 50.4MB)

테스트 케이스

assertEquals(2, test.solution(3));
assertEquals(5, test.solution(5));
assertEquals(987, test.solution(16));
assertEquals(256379, test.solution(1234156));
assertEquals(473509, test.solution(100001));
assertEquals(1168141, test.solution(100000));
assertEquals(547662, test.solution(124126347));

참고 사이트

피보나치 알고리즘을 해결하는 다섯가지 방법

댓글 공유

프로그래머스: 후보키

2020/06/26

문제

https://programmers.co.kr/learn/courses/30/lessons/42890

코드

코드 출처 https://leveloper.tistory.com/106

public int solution(String[][] relation) {

    int columnCount = relation[0].length;
    int rowCount = relation.length;

    List<Integer> list = new ArrayList<Integer>();
    for (int i = 1; i < (1 << columnCount); i++) {
        if (!isUniqueness(relation, i, columnCount, rowCount)) {
            continue;
        }

        if (!isMinimality(i, list)) {
            continue;
        }

        list.add(i);
    }

    return list.size();
}

private boolean isUniqueness(String[][] relation, int set, int columnCount, int rowCount) {
    ArrayList<Integer> columnIndexList = getColumnIndex(set, columnCount);

    HashSet<String> hashSet = new HashSet<>();
    for (int row = 0; row < rowCount; row++) {
        StringBuilder sb = new StringBuilder();

        for (int column : columnIndexList) {
            sb.append(relation[row][column]);
        }

        hashSet.add(sb.toString());
    }

    return hashSet.size() == rowCount;
}

private ArrayList<Integer> getColumnIndex(int set, int colSize) {
    ArrayList<Integer> result = new ArrayList<>();
    for (int i = 0; i < colSize; i++) {
        if (((set >> i) & 1) == 1) {
            result.add(i);
        }
    }

    return result;
}

private boolean isMinimality(int set, List<Integer> list) {
    boolean isMinimality = true;

    for (int i : list) {
        if ((set & i) == i) {
            isMinimality = false;
            break;
        }
    }

    return isMinimality;
}

코드 출처 https://leveloper.tistory.com/106

흐름

예제

예제의 경우의 수

10진수	2진수	부분 집합
1	1	학번
2	10	이름
3	11	학번 이름
4	100	전공
5	101	학번 전공
6	110	전공 이름
7	111	학번 이름 전공
8	1000	학년
9	1001	학번 학년
10	1010	이름 학년
11	1011	학번 이름 학년
12	1100	전공 학년
13	1101	학번 전공 학년
14	1110	이름 전공 학년
15	1111	학번 이름 전공 학년

부분 집합에 매핑되는 2진수

학년	전공	이름	학번
			1
		1	0
		1	1
	1	0	0
	1	0	1
	1	1	0
	1	1	1
1	0	0	0
1	0	0	1
1	0	1	0
1	0	1	1
1	1	0	0
1	1	0	1
1	1	1	0
1	1	1	1

1
2
3

for (int i = 1; i < (1 << columnCount); i++) {
    ...
}

모든 경우의 수 만큼 반복하기 위해 테이블의 컬럼 수 만큼 1을 왼쪽 시프트 한다.
column이 4 이면 1부터해서 1, 10, 100, 1000, 10000이 되고 10진수로 16이 된다.
후보키의 조건인 유일성와 최소성을 만족하는 지 확인한다.
유일성과 최소성을 모두 만족한다면 해당하는 값을 List에 추가한다.
모든 반복이 끝나면 List의 크기를 return 한다.
끝

유일성 확인

private ArrayList<Integer> getColumnIndex(int set, int colSize) {
    ArrayList<Integer> result = new ArrayList<>();
    for (int i = 0; i < colSize; i++) {
        if (((set >> i) & 1) == 1) {
            result.add(i);
        }
    }

    return result;
}

10진수를 2진수로 치환하기 위해 오른쪽 시프트 연산자와 And 비트 연산자를 이용한다.
처음은 1부터 이므로 1을 오른쪽으로 0만큼 시프트하면 그대로 1이고 1과 1을 And 하면 값은 1과 같으므로 리스트에 담는다.
1을 0 이상 시프트 한다면 0이 되므로 list에는 더 이상 추가 될 수 없다.
set에 2가 들어온 경우엔 2는 위 표에 적힌 것 처럼 2진수로 10이므로 10을 오른쪽으로 0번 시프트하면 10 이므로 1과 and 연산을 하면 0이 된다.
10을 오른쪽으로 1번 시프트하면 1이 되고 and 연산하면 1이 맞으므로 list에 1을 추가하고 그 이상 시프트 연산해봤자 0이 된다.
set에 3이 들어온 경우엔 3은 위 표에 적힌 것 처럼 2진수로 11이므로 11을 오른쪽으로 0번 시프트하면 11이므로 1과 and 연산하면 1이 맞으므로 list에 0을 추가한다.
11을 오른쪽으로 1번 시프트하면 1이므로 1과 and 연산하면 1이 맞으므로 list에 1을 추가한다.
이 처럼 쭉 모든 수를 반복해서 colmn의 index를 구한다.

private boolean isUniqueness(String[][] relation, int set, int columnCount, int rowCount) {
    ArrayList<Integer> columnIndexList = getColumnIndex(set, columnCount);

    HashSet<String> hashSet = new HashSet<>();
    for (int row = 0; row < rowCount; row++) {
        StringBuilder sb = new StringBuilder();

        for (int column : columnIndexList) {
            sb.append(relation[row][column]);
        }

        hashSet.add(sb.toString());
    }

    return hashSet.size() == rowCount;
}

구한 컬럼 index를 가지고 row 만큼 반복하면서 문자열을 연결하고 hashset에 담는다.
set은 중복된 값이 담기지 않으므로 중북된 값이 없다면 set size와 row의 수가 같을 것이므로 같으면 유일성안 만족한다고 판단한다.

최소성 확인

private boolean isMinimality(int set, List<Integer> list) {
    boolean isMinimality = true;

    for (int i : list) {
        if ((set & i) == i) {
            isMinimality = false;
            break;
        }
    }

    return isMinimality;
}

유일성을 만족하는 슈퍼키들(list) 중에 최소성을 만족하는 값을 찾는다.
예제에선 학번은 유일성과 최소성을 만족해서 list에 1이 추가 되지만 이름이 중복되므로 2는 유일성을 만족하지 list에 저장되지 못한다.
set이 3인 경우 list에 저장된 1과 and 연산하면 11 & 1 이므로 1이 되어 1과 같으므로 최소성을 만족하지 못하고 false가 return 된다.
결국 list에 저장된 학번이 포함된 슈퍼키들은 모두 제외되고 2진수와 매핑되는 표에서 보면 {학번, 이름}(11), {학번, 전공}(101), {학번, 이름, 전공}(111), {학번 학년}(1001) … 등은 모두 제외되는 것이다.
그럼 결국 학번이 포함되지 않은 것들 중에 유일성을 만족하면서 최소성을 만족하는지 판단하게 된다.

결과

번호	속도
테스트 1	통과 (0.90ms, 50.4MB)
테스트 2	통과 (1.03ms, 51.8MB)
테스트 3	통과 (0.93ms, 51.9MB)
테스트 4	통과 (1.05ms, 52.8MB)
테스트 5	통과 (0.98ms, 52.1MB)
테스트 6	통과 (0.94ms, 50.4MB)
테스트 7	통과 (0.97ms, 50.6MB)
테스트 8	통과 (0.96ms, 52.4MB)
테스트 9	통과 (1.08ms, 50MB)
테스트 10	통과 (1.21ms, 52.3MB)
테스트 11	통과 (1.33ms, 54.7MB)
테스트 12	통과 (5.01ms, 52.9MB)
테스트 13	통과 (1.39ms, 52MB)
테스트 14	통과 (0.98ms, 54MB)
테스트 15	통과 (0.90ms, 52.5MB)
테스트 16	통과 (1.05ms, 50.8MB)
테스트 17	통과 (1.06ms, 50.5MB)
테스트 18	통과 (8.04ms, 54.5MB)
테스트 19	통과 (4.60ms, 52.9MB)
테스트 20	통과 (7.92ms, 50.5MB)
테스트 21	통과 (6.33ms, 54.7MB)
테스트 22	통과 (4.12ms, 50.7MB)
테스트 23	통과 (1.09ms, 52.7MB)
테스트 24	통과 (5.30ms, 52.5MB)
테스트 25	통과 (8.25ms, 54.4MB)
테스트 26	통과 (5.85ms, 52.3MB)
테스트 27	통과 (1.61ms, 52.8MB)
테스트 28	통과 (2.01ms, 52MB)

테스트 케이스

String[][] args = new String[][] {{"100","ryan","music","2"},{"200","apeach","math","2"},{"300","tube","computer","3"},{"400","con","computer","4"},{"500","muzi","music","3"},{"600","apeach","music","2"}};
assertEquals(2, test.solution(args));

String[][] args1 = new String[][] {
        {"4", "4", "사랑", "2020-07-03 오전 12:00:00", "love"}
        , {"5", "4", "같은, 좋은, 와 비슷한", "2020-07-03 오전 12:00:00", "like"}
        , {"6", "4", "사과,대도시", "2020-07-03 오전 12:00:00", "apple"}
        , {"7", "4", "빌다,기도하다,에게 간청하다", "2020-07-03 오전 12:00:00", "pray"}
        , {"8", "3", "빌다,기도하다,에게 간청하다", "2020-06-27 오전 12:00:00", "pray"}
        , {"9", "4", "안녕", "2020-07-03 오전 12:00:00", "hi"}
        , {"10", "3", "같은, 좋은", "2020-06-29 오전 12:00:00", "like"}
        , {"11", "2", "나는 모자를 벗는다", "2020-06-27 오전 12:00:00", "I take off my hat"}};

assertEquals(5, test.solution(args1));

String[][] args2 = new String[][] {
        {"4", "4", "사랑", "2020-07-03 오전 12:00:00", "love"}
        , {"5", "4", "같은, 좋은, 와 비슷한", "2020-07-03 오전 12:00:00", "like"}
        , {"6", "4", "사과,대도시", "2020-07-03 오전 12:00:00", "apple"}
        , {"7", "4", "빌다,기도하다,에게 간청하다", "2020-07-03 오전 12:00:00", "pray"}
        , {"8", "4", "빌다,기도하다,에게 간청하다", "2020-06-27 오전 12:00:00", "pray"}
        , {"9", "4", "안녕", "2020-07-03 오전 12:00:00", "hi"}
        , {"10", "3", "같은, 좋은", "2020-06-29 오전 12:00:00", "like"}
        , {"11", "2", "나는 모자를 벗는다", "2020-06-27 오전 12:00:00", "I take off my hat"}};

assertEquals(3, test.solution(args2));

참고 사이트

댓글 공유

프로그래머스: 단체사진 찍기

2020/06/24

문제

https://programmers.co.kr/learn/courses/30/lessons/1835

코드

private static final int PEOPLE_COUNT = 8;
private static final String[] PEOPLE_NAMES = {"A", "C", "F", "J", "M", "N", "R", "T"};

private static int answer;
public int solution(int n, String[] data) {
    answer = 0;
    perm("", 0, new boolean[8], data);

    return this.answer;
}

private void perm(String perm, int depth, boolean[] isVisit, String[] data) {
    if (depth == PEOPLE_COUNT) {

        if (isCondition(perm, data)) {
            answer++;
        }
    }

    for (int i = 0; i < PEOPLE_COUNT; i++) {
        if (!isVisit[i]) {
            isVisit[i] = true;
            perm(perm + PEOPLE_NAMES[i], depth + 1, isVisit, data);
            isVisit[i] = false;
        }
    }
}

private boolean isCondition(String perm, String[] data) {
    boolean isCondition = true;

    for (int i = 0; i < data.length; i++) {
        char[] tochar = data[i].toCharArray();
        int people1 = perm.indexOf(tochar[0]);
        int people2 = perm.indexOf(tochar[2]);

        int interval = people1 > people2 ? people1 - people2 - 1 : people2 - people1 - 1;

        int requestInterval = tochar[4] - '0';
        if (tochar[3] == '=' && interval != requestInterval) {
            isCondition = false;
            break;
        }

        if (tochar[3] == '<' && interval >= requestInterval) {
            isCondition = false;
            break;
        }

        if (tochar[3] == '>' && interval <= requestInterval) {
            isCondition = false;
            break;
        }
    }

    return isCondition;
}

흐름

{“A”, “C”, “F”, “J”, “M”, “N”, “R”, “T”}로 나올 수 있는 문자열을 모두 만들어서 비교
위 array size 만큼 돌면서 문자열을 만드는데 이미 문자열에 포함된 문자는 추가하지 않기 위해 똑같은 size에 boolean array를 만듬
만들어서 그 boolean array의 index가 true면 이미 문자열에 추가된 문자 이므로 넘어감
문자열에 추가되지 않은 문자라면 다시 추가하지 않기 위해 boolean을 true로 변경
문자열을 이어 붙이기 위해 현재 메서드(perm)를 재귀호출 하는데
현재 문자열(perm)에 추가할 문자 (PEOPLE_NAMES[i])를 더하고, 배열 인덱스가 한 단계 깊어 졌으므로 depth를 +1 해서 호출
반복 하다가 사람 수 만큼(PEOPLE_NAMES) 들어왔으면
이 문자열이 비교와 할 문자열의 조건과 같은지 확인함
{“N~~F=0”, “R~~T>2”} 이런 식으로 되어 있으므로
조건 문자열에서 먼저 0번째와 2번째를 가져와서 지금 만든 문자열에서 해당 문자들이 몇 번째에 위치해 있는지 구함 (indexOf())
구한 값의 차를 구함
조건에서 해당 문자들의 간격이 몇인지 알기 위해 4번째 문자를 가져옴
조건 문자열에서 3번째 문자에 따라 참인지 아닌지 비교함
1. ‘=’ 이면서 구한 간격과 조건의 간격이 같지 않으면 false
2. ‘<’ 이면서 구한 간격이 조건의 간격보다 크거나 같으면 false
3. ‘>’ 이면서 구한 간격이 조건의 간격보다 작거나 같으면 false
모든 조건을 통과하면 경우의 수를 증가시킴
모든 문자열에 대해 비교가 끝나면 끝

부연 설명 boolean[] isVisit의 변화와 문자열이 만들어지는 과정

for (int i = 0; i < PEOPLE_COUNT; i++) {
    if (!isVisit[i]) {
        isVisit[i] = true;
        perm(perm + PEOPLE_NAMES[i], depth + 1, isVisit, data);
        isVisit[i] = false;
    }
}

{false, false, false, false, false, false, false, false} 인 상태에서 위 반복을 돌면서 재귀로 들어감
{true, false, false, false, false, false, false, false}가 된 상태에서 perm 재귀를 타고 반복…
{true, true, true, true, true, true, true, true}이 된 상태로 재귀를 빠져나옴
빠져나오면 isVisit[i] = false 때문에 마지막 7번째 index는 false로 변경되고 반복문이 끝났으므로 재귀를 빠져나옴
재귀를 나왔으니 {true, true, true, true, true, true, true, false}인 상태에서 i는 6이고 6번째 index도 false로 만듬
{true, true, true, true, true, true, false, false} 그럼 이 상태가 되고 여기서 반복문이 돌아서 i는 7이 되고 7번째 index는 true로 변경
{true, true, true, true, true, true, false, true}인 상태로 재귀에 들어가지만 depth가 8이 아니므로 다시 for문을 도는데
{true, true, true, true, true, true, false, true}인 상태이므로 여태 재귀돌면서 만들었던 문자열 마지막에 6번째 문자가 추가되게 됨
1. “ACFJMNT” + 6번째 index인 “R”
위 상황이 반복되면서 8자리 문자열이 계속 반복적으로 생성되고 비교됨

결과

번호	속도
테스트 1	통과 (1723.16ms, 333MB)

테스트 케이스

1 2	assertEquals(3648, test.solution(2, new String[] {"N~F=0", "R~T>2"})); assertEquals(0, test.solution(2, new String[] {"M~C<2", "C~M>1"}));

참고 사이트

https://tech.kakao.com/2017/09/13/code-festival-round-2/

댓글 공유

프로그래머스: 숫자 야구

2020/06/23

문제

https://programmers.co.kr/learn/courses/30/lessons/42841

직접 플레이 해보기

코드


private static final int BEGIN_INDEX = 123;
private static final int END_INDEX = 987;

public int solution(int[][] baseball) {
    List<String> allNumber = getAllNumber();

    int answer = 0;
    for (int i = 0; i < allNumber.size(); i++) {
        if (isAnswer(baseball, allNumber.get(i).toCharArray())) {
            ++answer;
        }
    }

    return answer;
}

private List<String> getAllNumber() {
    List<String> list = new ArrayList<String>();
    for (int i = BEGIN_INDEX; i <= END_INDEX; i++) {
        char[] tochar = String.valueOf(i).toCharArray();

        if (tochar[0] == tochar[1] || tochar[0] == tochar[2] || tochar[1] == tochar[2]) {
            continue;
        }

        if (tochar[0] == '0' || tochar[1] == '0' || tochar[2] == '0') {
            continue;
        }

        list.add(new String(tochar));
    }

    return list;
}

private boolean isAnswer(int[][] baseball, char[] number) {
    boolean isAnswer = true;

    for (int i = 0; i < baseball.length; i++) {
        char[] requestBall = String.valueOf(baseball[i][0]).toCharArray();

        int[] strikeAndBall = getStrikeAndBall(requestBall, number);

        if (baseball[i][1] != strikeAndBall[0] || baseball[i][2] != strikeAndBall[1]) {
            isAnswer = false;
            break;
        }
    }

    return isAnswer;
}

private int[] getStrikeAndBall(char[] requestBall, char[] number) {
    int strike = 0;
    int ball = 0;

    for (int i = 0; i < 3; i++) {
        if (number[i] == requestBall[i]) {
            ++strike;
        }

        if (isBall(requestBall, number[i])) {
            ++ball;
        }
    }

    ball -= strike;

    return new int[] {strike, ball};
}

private boolean isBall(char[] requestBall, char number) {
    boolean isBall = false;
    for (int i = 0; i < 3; i++) {
        if (number == requestBall[i]) {
            isBall = true;
            break;
        }
    }

    return isBall;
}

흐름

숫자 야구에서 나올 수 있는 모든 숫자를 구함(123~987)
구할 때 같은 숫자가 중복 될 수 없고 0이 들어갈 수 없으므로 확인해서 continue
구한 숫자들의 갯수만큼 돌면서 가능한 숫자인지 확인하는데
우선 나올 수 있는 모든 수 중 하나씩 돌면서 그 수와 배열로 받은 상대 수를 비교
받은 수와 뽑은 수를 한 자리씩 비교하면서 자리도 같고 숫자도 같으면 스트라이크
자리는 틀리지만 뽑은 수가 받은 수 안에 포함되어 있으면 볼로 처리
스트라이크이면서 볼인 경우는 있을 수 없기 때문에 볼에서 스트라이크의 갯수를 뻄
구한 스트라이크와 볼의 개수를 받은 수의 스트라이크와 볼 수와 비교해서 둘 중 하나도 같지 않으면 false를 저장하고 반복문을 빠져 나오고
조건에 맞다면 정답의 갯수를 증가 시킴
반복문이 끝나면 정답 갯수 return
끝

결과

번호	속도
테스트 1	통과 (3.49ms, 52.4MB)
테스트 2	통과 (4.55ms, 50.7MB)
테스트 3	통과 (3.33ms, 52.6MB)
테스트 4	통과 (3.48ms, 52MB)
테스트 5	통과 (4.26ms, 50.4MB)
테스트 6	통과 (4.69ms, 52.5MB)
테스트 7	통과 (3.68ms, 50.8MB)
테스트 8	통과 (4.35ms, 52.3MB)
테스트 9	통과 (3.60ms, 52.7MB)
테스트 10	통과 (3.33ms, 50.3MB)

테스트 케이스

1 2	assertEquals(2, test.solution(new int[][] {{123, 1, 1}, {356, 1, 0}, {327, 2, 0}, {489, 0, 1}})); assertEquals(2, test.solution(new int[][] {{659, 0, 1}, {264, 1, 1}, {126, 1, 2}}));

참고 사이트

https://gurumee92.tistory.com/180

댓글 공유

프로그래머스: 가장 큰 정사각형 찾기

2020/06/23

문제

https://programmers.co.kr/learn/courses/18/lessons/1879

코드

public int solution(int[][] board) {

    if (board.length < 2 || board[0].length < 2) {
        return smallSquare(board);
    }

    int answer = nomalSquare(board);
    return answer * answer;
}

private int smallSquare(int[][] board) {
    int size = 0;
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (board[i][j] == 1) {
                size = 1;
                break;
            }
        }

        if (size == 1) {
            break;
        }
    }

    return size;
}

private int nomalSquare(int[][] board) {
    int answer = 0;

    int min = Integer.MAX_VALUE;
    for (int i = 1; i < board.length; i++) {
        for (int j = 1; j < board[0].length; j++) {
            if (board[i][j] == 0) {
                continue;
            }

            board[i][j] = Math.min(board[i-1][j-1], Math.min(board[i-1][j], board[i][j-1])) + 1;

            if (board[i][j] > answer) {
                answer = board[i][j];
            }
        }
    }

    return answer;
}

흐름

배열의 크기가 2보다 작은 경우엔 크기가 1인 정사각형 밖에 존재 할 수 없으므로, 배열의 크키가 2 이하인 배열에 1이 들어있는지 확인
배열을 [1,1] 부터 반복
현재 위치의 값이 0인 경우엔 절대 정사각형 일 수 없으므로 더 이상 돌지 않고 continue
현재 위치(1,1)의 좌상(0,0)과 상(0,1) 좌(1,0)의 값들중 최소값을 구함
구한 최소값에 1을 더해서 현재 위치에 할당
구한 최소값이 현재 가장 큰 정사각형의 크기 보다 크면 정사각형의 크기를 구한 최소값으로 변경
반복
끝

흐름 이미지 설명

사각형

결과

정확성 테스트

번호	속도
테스트 1	통과 (0.86ms, 52.4MB)
테스트 2	통과 (0.77ms, 52.2MB)
테스트 3	통과 (0.83ms, 52.6MB)
테스트 4	통과 (0.75ms, 50.4MB)
테스트 5	통과 (0.72ms, 52.8MB)
테스트 6	통과 (0.83ms, 52.7MB)
테스트 7	통과 (0.79ms, 50.4MB)
테스트 8	통과 (0.83ms, 54.1MB)
테스트 9	통과 (0.79ms, 52.4MB)
테스트 10	통과 (0.83ms, 52.3MB)
테스트 11	통과 (0.75ms, 52.2MB)
테스트 12	통과 (0.79ms, 52.3MB)
테스트 13	통과 (0.76ms, 52.1MB)
테스트 14	통과 (0.83ms, 49.9MB)
테스트 15	통과 (0.75ms, 50.5MB)
테스트 16	통과 (0.91ms, 50MB)
테스트 17	통과 (0.83ms, 52.4MB)
테스트 18	통과 (0.92ms, 52.3MB)
테스트 19	통과 (1.06ms, 52MB)

효율성 테스트

번호	속도
테스트 1	통과 (24.74ms, 97.5MB)
테스트 2	통과 (25.24ms, 99.6MB)
테스트 3	통과 (26.48ms, 99.8MB)

테스트 케이스

1
2
3

assertEquals(9, test.solution(new int[][]{{0,1,1,1} ,{1,1,1,1},{1,1,1,1},{0,0,1,0}}));
assertEquals(4, test.solution(new int[][]{{0,0,1,1} ,{1,1,1,1}}));
assertEquals(1, test.solution(new int[][]{{0,0,1,1}}));

참고 사이트

https://blog.sonim1.com/212

댓글 공유

프로그래머스: 소수 만들기

2020/06/17

문제

https://programmers.co.kr/learn/courses/30/lessons/12977

코드

public int solution(int[] nums) {
    int answer = 0;

    List<Long> list = getSumList(nums);

    for (long i : list) {
        boolean isNotPrime = false;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                isNotPrime = true;
                break;
            }
        }

        if (!isNotPrime) {
            ++answer;
        }
    }

    return answer;
}

private List<Long> getSumList(int[] nums) {
    List<Long> list = new ArrayList<Long>();

    int arrayLength = nums.length;
    for (int i = 0; i < arrayLength; i++) {
        for (int j = i + 1; j < arrayLength; j++) {
            if (j == arrayLength - 1) {
                break;
            }

            for (int k = j + 1; k < arrayLength; k++) {
                list.add((long) (nums[i] + nums[j] + nums[k]));
            }
        }
    }

    return list;
}

흐름

3개이므로 3중 for문으로 돌면서 경우의 수 모두 돌면서 더한 값을 list에 저장
arrayoutofrange가 발생하지 않도록 length -1 인 경우 끝냄
모든 합이 저장된 list를 돌면서 소수인지 확인함
구한 값이 소수이면 값을 증가시킴
반복이 끝나면 return
끝

결과

번호	속도
테스트 1	통과 (2.48ms, 52.7MB)
테스트 2	통과 (3.29ms, 52.2MB)
테스트 3	통과 (1.36ms, 52.4MB)
테스트 4	통과 (1.32ms, 52.8MB)
테스트 5	통과 (4.94ms, 50.4MB)
테스트 6	통과 (5.02ms, 52.3MB)
테스트 7	통과 (1.10ms, 53MB)
테스트 8	통과 (8.70ms, 52.2MB)
테스트 9	통과 (1.78ms, 52.1MB)
테스트 10	통과 (8.33ms, 52.5MB)
테스트 11	통과 (1.06ms, 52.1MB)
테스트 12	통과 (0.95ms, 52.3MB)
테스트 13	통과 (1.03ms, 50.5MB)
테스트 14	통과 (0.94ms, 52.4MB)
테스트 15	통과 (0.82ms, 50MB)
테스트 16	통과 (8.65ms, 52.8MB)
테스트 17	통과 (7.43ms, 52.4MB)
테스트 18	통과 (0.95ms, 52.9MB)
테스트 19	통과 (0.83ms, 50.3MB)
테스트 20	통과 (9.97ms, 52.5MB)
테스트 21	통과 (10.12ms, 52.6MB)
테스트 22	통과 (2.31ms, 52.3MB)
테스트 23	통과 (0.83ms, 52.1MB)
테스트 24	통과 (9.64ms, 50.8MB)
테스트 25	통과 (9.52ms, 50.5MB)
테스트 26	통과 (0.89ms, 52.1MB)

테스트 케이스

1 2	assertEquals(1, test.solution(new int[] {1,2,3,4})); assertEquals(4, test.solution(new int[] {1,2,7,6,4}));

여담

당연히 속도 제한에 걸릴 줄 알고 제출했는데 통과되었다
썩 만족스럽지 못한 코드
만약 서로 다른 3개가 아니라 임의 수 n 이었다면?
고민을 좀 더 해봐야 할 듯 싶다.

댓글 공유

프로그래머스: 괄호 변환

2020/06/16

문제

https://programmers.co.kr/learn/courses/30/lessons/60058

코드

private static final Character LEFT = '(';
private static final Character RIGHT = ')';

public String solution(String p) {
    String answer = getDivide(p);
    return answer;
}

private String getDivide(String w) {
    if (w.isEmpty()) {
        return w;
    }

    String[] uAndv = getUAndV(w);
    String u = uAndv[0];
    String v = uAndv[1];

    if (!isPerfectBracket(u)) {
        return createPerfectBracket(u, v);
    }

    return u + getDivide(v);
}

private String[] getUAndV(String w) {
    StringBuilder sb = new StringBuilder();
    char[] tochar = w.toCharArray();
    Stack<Character> stack = new Stack<>();
    char popChar = (tochar[0] == LEFT) ? RIGHT : LEFT;

    for (char ch : tochar) {
        if (ch == popChar) {
            stack.pop();
            sb.append(popChar);
        } else {
            sb.append(stack.push(ch));
        }

        if (stack.isEmpty()) {
            break;
        }
    }

    String[] uAndv = new String[2];
    uAndv[0] = sb.toString();
    uAndv[1] = new String(tochar, uAndv[0].length(), tochar.length - uAndv[0].length());

    return uAndv;
}

private boolean isPerfectBracket(String u) {
    int sum = 0;
    for (int i = 0; i < u.length(); i++) {
        sum += (u.charAt(i) == LEFT) ? +1 : -1;

        if (sum < 0) {
            break;
        }
    }

    return sum == 0;
}

private String createPerfectBracket(String u, String v) {
    StringBuilder str = new StringBuilder();

    str.append(LEFT);
    str.append(getDivide(v));
    str.append(RIGHT);

    char[] newU = u.substring(1, u.length() -1).toCharArray();
    str.append(getChange(newU));

    return str.toString();
}

private char[] getChange(char[] newU) {
    for (int i = 0; i < newU.length; i++) {
        newU[i] = (newU[i] == LEFT) ? RIGHT : LEFT;
    }

    return newU;
}

흐름

문제에 있는 그대로 작성하면 됨

입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
문자열 w를 두 “균형잡힌 괄호 문자열” u, v로 분리합니다.
단, u는 “균형잡힌 괄호 문자열”로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
문자열 u가 “올바른 괄호 문자열” 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
문자열 u가 “올바른 괄호 문자열”이 아니라면 아래 과정을 수행합니다.
1. 빈 문자열에 첫 번째 문자로 ‘(‘를 붙입니다.
2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
3. ‘)’를 다시 붙입니다.
4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
5. 생성된 문자열을 반환합니다.

결과

번호	속도
테스트 1	통과 (32.01ms, 55.5MB)
테스트 2	통과 (1.42ms, 52.3MB)
테스트 3	통과 (30.81ms, 55.3MB)
테스트 4	통과 (30.93ms, 52.9MB)
테스트 5	통과 (30.16ms, 55.5MB)
테스트 6	통과 (29.55ms, 55.3MB)
테스트 7	통과 (35.55ms, 53MB)
테스트 8	통과 (29.41ms, 55.2MB)
테스트 9	통과 (28.63ms, 53.6MB)
테스트 10	통과 (30.95ms, 54.9MB)
테스트 11	통과 (30.81ms, 55.9MB)
테스트 12	통과 (28.73ms, 55.3MB)
테스트 13	통과 (30.50ms, 55.7MB)
테스트 14	통과 (38.62ms, 53.5MB)
테스트 15	통과 (31.72ms, 53.5MB)
테스트 16	통과 (31.20ms, 55MB)
테스트 17	통과 (30.63ms, 55.2MB)
테스트 18	통과 (33.95ms, 55.4MB)
테스트 19	통과 (31.25ms, 53.6MB)
테스트 20	통과 (33.02ms, 55.5MB)
테스트 21	통과 (33.70ms, 53.5MB)
테스트 22	통과 (33.13ms, 53.5MB)
테스트 23	통과 (32.43ms, 53MB)
테스트 24	통과 (31.24ms, 55.9MB)
테스트 25	통과 (33.63ms, 56MB)

테스트 케이스

assertEquals("(()())()", test.solution("(()())()"));
assertEquals("()", test.solution(")("));
assertEquals("()(())()", test.solution("()))((()"));
assertEquals("(((())))", test.solution(")()()()("));
assertEquals("()()((()))", test.solution("))()))(((("));
assertEquals("()", test.solution("()"));
assertEquals("()()()()()()((()))", test.solution("()()()()()()((()))"));
assertEquals("((((())())))()(())", test.solution("((((())()))))))((("));
assertEquals("(((()())())())((()))", test.solution("))))((((((()())()))("));

댓글 공유

프로그래머스: 탑

2020/06/15

문제

https://programmers.co.kr/learn/courses/30/lessons/42588

코드

본인의 코드가 아닌 해당 문제 최다 좋아요를 받은 코드

public int[] solution(int[] heights) {
    Stack<Tower> st = new Stack<>();
    int[] answer = new int[heights.length];

    for (int i = 0; i < heights.length; i++) {
        Tower tower = new Tower(i + 1, heights[i]);
        int receiveIdx = 0;

        while (!st.isEmpty()) {
            Tower top = st.peek();

            if (top.height > tower.height) {
                receiveIdx = top.idx;
                break;
            }

            st.pop();
        }

        st.push(tower);
        answer[i] = receiveIdx;
    }

    return answer;
}

class Tower {
    int idx;
    int height;

    public Tower(int idx, int height) {
        this.idx = idx;
        this.height = height;
    }
}

본인의 코드가 아닌 해당 문제 최다 좋아요를 받은 코드

흐름

탑의 index와 높이를 저장 할 Tower class 생성
탑의 개수만큼 반복
1 번쨰부터 시작되야하므로 현재 index에서 +1 한 index와 현재 높이를 갖는 tower를 생성
tower가 저장된 stack이 비었는지 체크
비어 있지 않다면 stack의 맨 위를 가져와서 현재 tower의 높이와 비교함
stack에 저장된 stack이 더 크다면 현재 타워에 전파를 받을 타워이므로 index를 receiveIdx 변수에 할당
크지 않다면 stack에 저장된 tower를 pop함
stack에 현재 tower를 push
answer에 아까 저장한 receiveIdx를 저장
answer return
끝

결과

번호	속도
테스트 1	통과 (1.89ms, 50.7MB)
테스트 2	통과 (1.84ms, 52.6MB)
테스트 3	통과 (1.96ms, 52.3MB)
테스트 4	통과 (2.04ms, 52.5MB)
테스트 5	통과 (2.02ms, 50.8MB)
테스트 6	통과 (2.28ms, 52.7MB)
테스트 7	통과 (1.78ms, 52.6MB)
테스트 8	통과 (2.06ms, 52.1MB)

테스트 케이스

1
2
3

assertArrayEquals(new int[] {0,0,2,2,4}, test.solution(new int[] {6,9,5,7,4}));
assertArrayEquals(new int[] {0,0,0,3,3,3,6}, test.solution(new int[] {3,9,9,3,5,7,2}));
assertArrayEquals(new int[] {0,0,2,0,0,5,6}, test.solution(new int[] {1,5,3,6,7,6,5}));

댓글 공유

문제

코드

흐름

최다 좋아요 코드

결과

테스트 케이스

문제

코드

삽질 코드

정석 코드

결과

뻘짓 코드

정석 코드

테스트 케이스

P.S

문제

코드

흐름

결과

테스트 케이스

참고 사이트

문제

코드

흐름

예제

예제의 경우의 수

부분 집합에 매핑되는 2진수

유일성 확인

최소성 확인

결과

테스트 케이스

참고 사이트

문제

코드

흐름

부연 설명 boolean[] isVisit의 변화와 문자열이 만들어지는 과정

결과

테스트 케이스

참고 사이트

문제

코드

흐름

결과

테스트 케이스

참고 사이트

문제

코드

흐름

흐름 이미지 설명

결과

정확성 테스트

효율성 테스트

테스트 케이스

참고 사이트

문제

코드

흐름

결과

테스트 케이스

여담

문제

코드

흐름

결과

테스트 케이스

문제

코드

흐름

결과

테스트 케이스

Junggu Ji