오른쪽으로 가는것을 기준으로 잡고 풀었다. 좌, 우 이동만 가지고 얘기하자면, 현재 위치를 기준으로 왼쪽/오른쪽 거리를 계산했을 때, 한 번이라도 왼쪽 거리가 짧을 경우 name의 끝에서부터 빼면서 계산했다. 다른 사람의 풀이를 보면 엄청 쉽게 구현하던데 신기하다...

 

탐욕법은 매 순간마다 최적의 값을 찾는다. 탐욕법은 탐욕스러운 선택 조건과 최적 부분 구조 조건을 가지는 특징이 있는데, 탐욕스러운 선택 조건은 앞에서 내가 선택한 것이 이후의 선택에 어떠한 영향을 미치지 않는다는 조건이고 최적 부분 구조 조건은 문제에 대한 최적해가 부분 문제에 대해서도 최적해여야 한다는 특징이 있다. 

 

이 문제에서는 인덱스 0 위치에서 왼쪽으로 갈 경우 문자열의 끝에 갈 수 있지만 문자열의 끝에서 오른쪽으로 갈 경우 인덱스 0위치로 갈 수 없다. 그래서 아래와 같은 결과가 나오게 된다.

ABAAAABAAAAAAAAAAAAB => 최적해 (13) / 실제 계산한 해 (19)

탐욕법 자체가 이미 지나온 길을 되돌아갈 수 없다고 하면 탐욕법이 맞는거 같기도하고.. 아리송하다.

 

public int solution(String name) {
    int answer = 0;
    int notA_Count = 0;
    int curCount = 0;
    int lastIndex = 0;
    char curChar = 'A';
    boolean leftSmallerThanRight = false;

    // A가 아닌 개수 및 A가 아닌 마지막 인덱스 구하기
    for(int i=0; i<name.length(); i++){
        if (name.charAt(i) != 'A'){
            lastIndex = i;
            notA_Count++;
        }
    }

    // 오른쪽으로 갈 수 있는 최대 구하기
    // 인덱스 0을 기준으로 왼쪽으로 갔을 때 몇번째 값이 A가 아닌지 확인 (0의 위치에서 왼쪽으로 갈 경우 거리값이 +1이 되어야 함)
    int leftCount = name.length() - lastIndex;
    int rightCount = 0;
    int curPos = 0;
    int upDownCount = 0;
    for(int i=0; i<name.length(); i++){
        curChar = name.charAt(i);
        if (curChar == 'A'){
            continue;
        }

        // i 위치에서 현재 위치를 빼면 오른쪽으로 몇 번 가야 A가 아닌 문자가 나오는지 알 수 있음
        rightCount = i - curPos;

        // A가 아닌 문자를 만나기 위해 오른쪽으로 간 횟수와 왼쪽으로 간 횟수를 비교
        // 왼쪽으로 간 횟수가 더 적을 경우 빠져나와 맨 오른쪽에서 왼쪽으로 진행하기 위해 빠져나옴
        if (rightCount > leftCount + curPos){
            leftSmallerThanRight = true;
            break;
        }
        else{
            answer += rightCount;
        }

        // 알파벳 구하기
        upDownCount = (curChar - 'A' > 'Z' - curChar + 1)? 'Z' - curChar + 1 : curChar - 'A';
        answer += upDownCount;

        // 현재 위치를 i번째로 옮김
        curPos = i;
        rightCount = 0;
        curCount++;
    }

    // 현재 위치에서 왼쪽으로 가는게 더 빠른 경우가 있을 때
    // 현재 위치부터 왼쪽으로 구해야 하니까 leftCount는 curPos 값으로 변경
    leftCount = curPos;
    if (leftSmallerThanRight){
        for(int i=name.length() - 1; i>=0; i--){
            if (notA_Count == curCount){
                break;
            }

            curChar = name.charAt(i);
            // A면 한 칸 이동
            if (curChar == 'A'){
                leftCount++;
                continue;
            }
            leftCount++;

            upDownCount = (curChar - 'A' > 'Z' - curChar + 1)? 'Z' - curChar + 1 : curChar - 'A';
            answer += upDownCount;
            answer += leftCount;
            leftCount = 0;
            curCount++;
        }
    }

    return answer;
}

 

 

프로그래머스 Level 2의 전화번호 목록을 풀었다. Hash를 이용하라는데, 아무리봐도 안될 것 같아 그냥 이중 for문으로 작성했다.

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        
        for(int i=0; i<phone_book.length; i++){
            for(int j=i + 1; j<phone_book.length; j++){
                if (phone_book[j].indexOf(phone_book[i]) == 0){
                    return false;
                }
                else{
                    break;
                }
            }
        }

        return true;
    }
}

Arrays.sort 를 한 이유는 String을 정렬하면 사전순으로 정렬되기 때문이다. 생각해보니 for문 한 번으로도 될 것 같다. 위와 같이 풀었을 때의 테스트 결과이다.

다른 사람들의 풀이를 보니까 나처럼 푼 사람도 있었고 문제에서 얘기한 HashMap을 사용한 사람도 있었다. 아래는 HashMap을 사용한 사람의 코드이다. 

public boolean solution(String[] phone_book) {
        boolean answer = true;
        HashMap<String,Integer> h =new HashMap<>();
        for(String s : phone_book) {
            h.put(s, h.getOrDefault(s,0)+1);
        }

        for(String s : phone_book) {
            for(int j=1; j<s.length(); j++) {
                if(h.containsKey(s.substring(0,j))) {
                   answer = false; 
                   break;
                }              
            }
        }    



        return answer;
    }

phone_book 배열에서 문자열을 가져와 하나씩 잘라가면서 HashMap에 잘라진 문자열이 키로 존재하는지 확인하고 있다면 false를 반환하는 코드이다. 아래는 위 코드로 실행했을 때의 테스트 결과이다.

확실히 글자수가 적거나 개수가 적을 경우에는 HashMap을 이용하면 상당히 빠른 것 같다. 그런데 굳이 HashMap을 사용할 필요가 있을까 싶은 문제였다..

해당 문제를 푸는데 좀 많은 시간이 소요되었다. 먼저 문제를 살펴보면 아래와 같다.

 

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한사항
  • W, H : 1억 이하의 자연수

즉, 8 x 12에서 흰색칸을 모두 지운 80이라는 값이 반환이 되어야 한다.

먼저 아래처럼 패턴을 나누었다. 패턴을 나누는 기준은 연속되지 않은 흰색 칸을 기준으로 했다.

그럼 패턴이 총 4개가 나오게 된다. 패턴의 길이는 가로 2, 세로 3인데, 이 값들은 가로와 세로를 각각 4로 나눈값이 된다. 하나 더 예시로 작성해 보았다. 

사용 못하는 칸이 모두 연속되어 있으므로 패턴이 1개이고 패턴의 길이는 가로 4, 세로 3이 된다. 패턴의 길이와 총 길이가 같으므로 패턴의 가로와 세로는 각각 1로 나눈 값과 동일하다. 이렇게 5x3, 6x4 등등의 길이의 종이를 위와 같은 방법으로 구해보았다. 

 

그 결과, 각 패턴의 길이는 종이의 가로, 세로값을 최대공약수로 나눈 값이 되며 패턴의 개수는 최대공약수의 값과 동일하다는 결론이 나왔다. 다시 위에 문제로 돌아가 패턴을 살펴보면,

패턴의 가로는 2, 세로는 3이 되는데 여기서 사용할 수 없는 칸은 총 4칸이다. 이 값 또한 가로와 세로를 더한 후 -1을 해주면 된다. 그 이유는 아래와 같다.

그림에서 볼 수 있듯이 3번을 위로, 4번을 왼쪽으로 붙이게 되면 패턴의 가로 + 세로 - 1 이 되기 때문에 사용하지 못하는 개수는 총 4개이다. 위에서 4x3 패턴의 예시도 동일하게 아래 그림처럼 가능하다. 

3, 5번을 왼쪽으로 붙이고 4, 6번을 위로 붙이게 되면 4 + 3 - 1 만큼의 개수를 사용하지 못하게 된다. 

위 내용을 코드로 작성하여 제출했다.

https://github.com/banjjak2/Programmers/blob/main/Level2/%EB%A9%80%EC%A9%A1%ED%95%9C_%EC%82%AC%EA%B0%81%ED%98%95.java

class Solution {
    public long solution(int w, int h) {
        long answer = 0;
        long totalCount = (long)w * h;
        // 패턴 총 개수
        int patternCount = gcd(w, h);

        // 1패턴당 가로 개수
        int widthPerPattern = w / patternCount;
        // 1패턴당 세로 개수
        int heightPerPattern = h / patternCount;
        // 1패턴당 못쓰는 개수
        int unusedCountPerPattern = widthPerPattern + heightPerPattern - 1;

        // 총개수 - (1패턴당 못쓰는 개수 * 패턴 총 개수);
        answer = totalCount - (unusedCountPerPattern * patternCount);
        return answer;
    }

    // 최대공약수 구하기
    public int gcd(int n, int m){
        // 나머지가 0이면
        if (m == 0){
            // 나눈값 반환
            return n;
        }

        // 나눈 수, 나머지 값
        return gcd(m, n % m);
    }
}

[Level 2] 단체사진 찍기 (Java)


프로그래머스의 Level2 문제인 단체사진 찍기를 풀었다. 나같은 경우 해당 문제를 아래와 같이 풀었었다.

  1. 알파벳 8자리에서 나올 수 있는 모든 경우의 수를 모두 구한다. (8! = 40320)
  2. 구한 경우의 수들을 조건에 맞는지 확인 후 조건에 만족할 경우 +1 해준다.
import java.util.*;

public class 단체사진_찍기 {
    public static void main(String[] args) {
        int n = 0;
        // String[] data = {
        //     "N~F=0", 
        //     "R~T>2"
        // };

        String[] data = {
            "M~C<2", 
            "C~M>1"
        };

        System.out.println(solution(n, data));
    }

    
    static char[] friendsAlphabet = new char[] { 'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T' };
    public static int solution(int n, String[] data){
        int answer = 0;
        createAllFriendsRow(0);
        for (String cs : createFriendsRowList) {
            if (checkCondition(cs, data)){
                answer++;
            }
        }
        return answer;
    }

    static boolean[] visited = new boolean[8];
    static List<String> createFriendsRowList = new ArrayList<String>();
    static char[] createFriendsRowArray = new char[8];
    public static void createAllFriendsRow(int index){
        if (index == visited.length){
            createFriendsRowList.add(String.valueOf(createFriendsRowArray));
        }
        else{
            for(int i=0; i<visited.length; i++){
                if (!visited[i]){
                    visited[i] = true;
                    createFriendsRowArray[index] = friendsAlphabet[i];
                    createAllFriendsRow(index + 1);
                    visited[i] = false;
                }
            }
        }
    }

    public static boolean checkCondition(String friendsArray, String[] data){
        String[] splits;
        String startFriend, endFriend;
        String condition;
        int conditionCount = 0;
        int gap;
        int indexGap = 0;
        int endIndex, startIndex;

        for (String c : data) {
            splits = c.split("");

            startFriend = splits[0];
            endFriend = splits[2];
            condition = splits[3];
            gap = Integer.parseInt(splits[4]);

            startIndex = friendsArray.indexOf(startFriend);
            endIndex = friendsArray.indexOf(endFriend);
            indexGap = Math.abs(endIndex - startIndex) - 1;

            switch (condition) {
                case "=":
                    if (indexGap != gap){
                        return false;
                    }
                    conditionCount++;
                    break;
                
                case ">":
                    if (indexGap <= gap){
                        return false;
                    }
                    conditionCount++;
                    break;

                case "<":
                    if (indexGap >= gap){
                        return false;
                    }
                    conditionCount++;
                    break;
            }
        }

        if (conditionCount == data.length){
            return true;
        }
        else{
            return false;
        }
    }
}

그 결과...

8.6초라는 어마어마한 성능을 가지고 있었다;

8! 만큼 2번 (프렌즈의 모든 경우의 수 구할 때, 조건에 맞는지 구할 때)을 돌아서 성능이 저렇게 나온건지 해서 아래와 같이 수정했었다.

  1. 모든 경우의 수를 구함과 동시에 조건에 맞는지 확인한다.
  2. 조건에 맞다면 +1 해준다.

위와 같이 작성해봐도 동일하게 8초 이상이 출력되었다. 그래서 다시 확인한 결과 checkCondition 함수에서 split 메소드로 문자열을 자르는 부분이 있었는데, 이 부분을 split 대신 charAt 메소드를 사용하여 구현해 보았다.

class Solution {
    char[] friendsAlphabet = new char[] { 'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T' };
    public int solution(int n, String[] data){
        int answer = 0;
        createAllFriendsRow(0, data);
        answer = correctCount;
        return answer;
    }

    boolean[] visited = new boolean[8];
    char[] createFriendsRowArray = new char[8];
    int correctCount = 0;
    public void createAllFriendsRow(int index, String[] data){
        if (index == visited.length){
            if (checkCondition(String.valueOf(createFriendsRowArray), data)){
                correctCount++;
            }
        }
        else{
            for(int i=0; i<visited.length; i++){
                if (!visited[i]){
                    visited[i] = true;
                    createFriendsRowArray[index] = friendsAlphabet[i];
                    createAllFriendsRow(index + 1, data);
                    visited[i] = false;
                }
            }
        }
    }

    public boolean checkCondition(String friendsArray, String[] data){
        char startFriend, endFriend;
        char condition;
        int conditionCount = 0;
        int gap;
        int indexGap = 0;
        int endIndex, startIndex;

        for (String c : data) {
            startFriend = c.charAt(0);
            endFriend = c.charAt(2);
            condition = c.charAt(3);
            gap = c.charAt(4) - '0';

            startIndex = friendsArray.indexOf(startFriend);
            endIndex = friendsArray.indexOf(endFriend);
            indexGap = Math.abs(endIndex - startIndex) - 1;

            switch (condition) {
                case '=':
                    if (indexGap != gap){
                        return false;
                    }
                    conditionCount++;
                    break;
                
                case '>':
                    if (indexGap <= gap){
                        return false;
                    }
                    conditionCount++;
                    break;

                case '<':
                    if (indexGap >= gap){
                        return false;
                    }
                    conditionCount++;
                    break;
            }
        }

        if (conditionCount == data.length){
            return true;
        }
        else{
            return false;
        }
    }
}

위와 같이 작성 한 후 다시 제출했더니 아래와 같은 결과가 나왔다.

 

속도와 메모리가 9배 이상 차이가 남을 확인할 수 있었다. 

 

결론.

  - split 대신 charAt을 사용할 수 있는 경우 charAt을 사용하는 것이 성능상에 유리하다. 

+ Recent posts