더 이상 물러설 곳이 없다

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

문제 설명

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.
기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.
단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면,
(각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)

손님 번호주문한 단품메뉴 조합

가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.

코스 종류메뉴 구성설명

[문제]

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

[제한사항]

• orders 배열의 크기는 2 이상 20 이하입니다.
• orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
  • 각 문자열은 알파벳 대문자로만 이루어져 있습니다.
  • 각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
• course 배열의 크기는 1 이상 10 이하입니다.
  • course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬되어 있습니다.
  • course 배열에는 같은 값이 중복해서 들어있지 않습니다.
• 정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return 해주세요.
  • 배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.
  • 만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
  • orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.

[입출력 예]

orderscourseresult

입출력 예에 대한 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
AD가 세 번, CD가 세 번, ACD가 두 번, ADE가 두 번, XYZ 가 두 번 주문됐습니다.
요리 5개를 주문한 손님이 1명 있지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 5개로 구성된 코스요리는 새로 추가하지 않습니다.

입출력 예 #3
WX가 두 번, XY가 두 번 주문됐습니다.
3명의 손님 모두 단품메뉴를 3개씩 주문했지만, 최소 2명 이상의 손님에게서 주문된 구성만 코스요리 후보에 들어가므로, 요리 3개로 구성된 코스요리는 새로 추가하지 않습니다.
또, 단품메뉴를 4개 이상 주문한 손님은 없으므로, 요리 4개로 구성된 코스요리 또한 새로 추가하지 않습니다.

풀이 1. 

import java.util.*;
import java.io.*;

class Solution {
    int max, mapIdx;
    StringBuilder sb;
    Map<String, Integer>[] mapArr;
    boolean[] check;

    public void push() {
        Map<String, Integer> temp = mapArr[mapIdx];
        if(temp.get(sb.toString()) == null) {
            temp.put(sb.toString(), 1);
            max =  Math.max(max, 1);
        }else {
            temp.put(sb.toString(), temp.get(sb.toString()) + 1);
            max = Math.max(max, temp.get(sb.toString()));
        }
    }

    public void dfs(int deptNow, int dept, int idx, String order) {
        if(deptNow == dept) {
            push();  // 해당 조합 추가
            return;
        }

        int len = order.length();
        for(int i = idx; i < len; i++) {
            if(!check[i] && deptNow + (len - idx) >= dept) {
                sb.append(order.charAt(i));
                check[i] = true;

                dfs(deptNow+1, dept, i+1, order);

                sb.deleteCharAt(sb.length() - 1);
                check[i] = false;
            }
        }
    }

    public ArrayList<String> solution(String[] orders, int[] course) {
        // 초기화
        ArrayList<String> answer = new ArrayList<>();
        sb = new StringBuilder();
        mapArr = new HashMap[course.length];
        for(int i = 0; i < course.length; i++) {  // course.length 만큼 Map 가져야 한다
            mapArr[i] =  new HashMap<>();
        }

        // 순서 맞춰주기 위해 정렬
        for(int i = 0; i < orders.length; i++) {
            char[] arr = orders[i].toCharArray();
            Arrays.sort(arr);
            orders[i] = new String(arr);
        }

        // course[i]를 목표 dept로 하는 조합 생성
        for(int i = 0; i < course.length; i++) {
            max = 0;  // max 초기화
            for(int j = 0; j < orders.length; j++) {
                check = new boolean[orders[j].length()];
                dfs(0, course[i], 0, orders[j]);
            }
            mapIdx += 1;

            if(max < 2) continue;  // 최소 두 명 이상에게 주문된 조합이어야 함
            Map<String, Integer> temp = mapArr[i];
            for(String str : temp.keySet()) {
                if(temp.get(str) == max) {
                    answer.add(str);
                }
            }
        }

        Collections.sort(answer);
        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        /**
         *
         * ["XYZ", "XWY", "WXA"]	[2,3,4]	["WX", "XY"]
         */
        Solution sol = new Solution();
        String[] orders = {"XYZ", "XWY", "WXA"};
        int[] course = {2, 3, 4};

        ArrayList<String> ans = sol.solution(orders, course);
        for(String str : ans) {
            System.out.println(str);
        }
    }
}

풀이 2.

import java.util.*;
import java.io.*;

class Solution {
    int max, mapIdx;
    StringBuilder sb;
    Map<String, Integer>[] mapArr;

    public void push() {
        Map<String, Integer> temp = mapArr[mapIdx];
        if(temp.get(sb.toString()) == null) {
            temp.put(sb.toString(), 1);
            max =  Math.max(max, 1);
        }else {
            temp.put(sb.toString(), temp.get(sb.toString()) + 1);
            max = Math.max(max, temp.get(sb.toString()));
        }
    }

    public void dfs(int deptNow, int dept, int idx, String order) {
        if(deptNow == dept) {
            push();  // 해당 조합 추가
            return;
        }

        int len = order.length();
        if(idx < len && deptNow + (len - idx) >= dept) {
            // idx번째 포함
            sb.append(order.charAt(idx));
            dfs(deptNow+1, dept, idx+1, order);
            sb.deleteCharAt(sb.length() - 1);
            
            // idx번째 미포함
            dfs(deptNow, dept, idx+1, order);
        }
    }

    public ArrayList<String> solution(String[] orders, int[] course) {
        // 초기화
        ArrayList<String> answer = new ArrayList<>();
        sb = new StringBuilder();
        mapArr = new HashMap[course.length];
        for(int i = 0; i < course.length; i++) {  // course.length 만큼 Map 가져야 한다
            mapArr[i] =  new HashMap<>();
        }

        // 순서 맞춰주기 위해 정렬
        for(int i = 0; i < orders.length; i++) {
            char[] arr = orders[i].toCharArray();
            Arrays.sort(arr);
            orders[i] = new String(arr);
        }

        // course[i]를 목표 dept로 하는 조합 생성
        for(int i = 0; i < course.length; i++) {
            max = 0;  // max 초기화
            for(int j = 0; j < orders.length; j++) {
                dfs(0, course[i], 0, orders[j]);
            }
            mapIdx += 1;

            if(max < 2) continue;  // 최소 두 명 이상에게 주문된 조합이어야 함
            Map<String, Integer> temp = mapArr[i];
            for(String str : temp.keySet()) {
                if(temp.get(str) == max) {
                    answer.add(str);
                }
            }
        }

        Collections.sort(answer);
        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        /**
         *
         * ["XYZ", "XWY", "WXA"]	[2,3,4]	["WX", "XY"]
         */
        Solution sol = new Solution();
        String[] orders = {"XYZ", "XWY", "WXA"};
        int[] course = {2, 3, 4};

        ArrayList<String> ans = sol.solution(orders, course);
        for(String str : ans) {
            System.out.println(str);
        }
    }
}

조건

1. 최소 2명 이상에게 주문된 적 있는 조합.

2. 목표 dept에서 최다 주문 조합이 여러 개 존재한다면 모두 정답 처리.

courser[i] 마다 Map<String, Integer>를 하나씩 갖는다.

max값을 갱신해가며 key, value쌍을 업데이트 하고 마지막에 max값과 같은 value를 가진 key들을 모두 정답처리한다.

주의할 점,

입력된 값들이 오름차순임이 보장되지 않는다.

따라서 시작하기 전에 orders의 모든 원소들을 오름차순 정렬 처리를 먼저 해줘야 한다.

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

문제 설명

일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다.

1. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다.
2. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다.

여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다. 즉, 어떤 시점에서 인접한 두 풍선 중 번호가 더 작은 풍선을 터트렸다면, 그 이후에는 인접한 두 풍선을 고른 뒤 번호가 더 큰 풍선만을 터트릴 수 있습니다.

당신은 어떤 풍선이 최후까지 남을 수 있는지 알아보고 싶습니다. 위에 서술된 조건대로 풍선을 터트리다 보면, 어떤 풍선은 최후까지 남을 수도 있지만, 어떤 풍선은 무슨 수를 쓰더라도 마지막까지 남기는 것이 불가능할 수도 있습니다.

일렬로 나열된 풍선들의 번호가 담긴 배열 a가 주어집니다. 위에 서술된 규칙대로 풍선들을 1개만 남을 때까지 터트렸을 때 최후까지 남기는 것이 가능한 풍선들의 개수를 return 하도록 solution 함수를 완성해주세요.

제한 사항

• a의 길이는 1 이상 1,000,000 이하입니다.
  • a[i]는 i+1 번째 풍선에 써진 숫자를 의미합니다.
  • a의 모든 수는 -1,000,000,000 이상 1,000,000,000 이하인 정수입니다.
  • a의 모든 수는 서로 다릅니다.

입출력 예

aresult

입출력 예 설명

입출력 예 #1

• 첫 번째 풍선(9가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [9, -5] 에서 9, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 두 번째 풍선(-1이 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -5가 써진 풍선(번호가 더 작은 것)을 터트립니다.
• 세 번째 풍선(-5가 써진 풍선)을 최후까지 남기는 방법은 다음과 같습니다.
  1. [9, -1, -5] 에서 9, -1이 써진 풍선을 고른 뒤, 9가 써진 풍선(번호가 더 큰 것)을 터트립니다.
  2. [-1, -5] 에서 -1, -5가 써진 풍선을 고른 뒤, -1이 써진 풍선(번호가 더 큰 것)을 터트립니다.
• 3개의 풍선이 최후까지 남을 수 있으므로, 3을 return 해야 합니다.

입출력 예 #2

• 최후까지 남을 수 있는 풍선은 -16, -92, -71, -68, -61, -33이 써진 풍선으로 모두 6개입니다.

풀이 .

class Solution {
    public int solution(int[] a) {
        int answer = 2;
        int left = a[0], right = a[a.length - 1];

        int[][] ans = new int[a.length][2];  // [i][0], [i][1] 중 하나만 1이면 지울 수 있음을 의미
        for(int i = 1; i <= a.length - 2; i++) {
            if(left > a[i]) {  // 끝점보다 작으면 지울 수 있다
                left = a[i];  // 더 작은 놈이 나왔으니 왼쪽 최소값 변경
                ans[i][0] = 1;
            }
        }
        for(int i = a.length - 2; i >= 1; i--) {
            if(right > a[i]) {  // 끝점보다 작으면 지울 수 있다
                right = a[i];  // 더 작은 놈이 나왔으니 오른쪽 최소값 변경
                ans[i][1] = 1;
            }
        }
        for(int i = 1; i <= a.length - 2; i++) {
            if(ans[i][0] == 1 || ans[i][1] == 1) {
                answer += 1;
            }
        }

        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] a = {-16, 27, 65, -2, 58, -92, -71, -68, -61, -33};
        int ans = sol.solution(a);
        System.out.println(ans);
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

( 절취선 나오기 전까지 푸념 주의 )

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

좌절감의 끝을 맛봤다.

도저히 혼자서는 방법을 떠올릴 수 없었다. 답을 봐도 한참동안 이해가 안 됐다.

나는 이런 유형의 문제가 너무 싫다.

DFS, BFS, 백트래킹, 브루트포스, 문자열.. 하다못해 그 DP마저도 풀다보면 유형이 익숙해지고 문제를 읽었을 때 "아, 이걸 적용해야겠구나" 하는 감이 왔다. (사실 이것도 완벽하게는 아니지만.. 그래도 확실히 어느정도는 느낌이 왔다)

근데 이런 식의 관찰력? 직관력?을 통해 조건을 찾아내고 그 조건에 따라 전개하는 방식은 도저히, 정말 도저히 모르겠다.

알고리즘이라는 영역이 애초에 지능의 영역이긴 하지만 그래도 몇몇 유형들은 경험치를 쌓아나갈수록 어느정도는 성장하는 느낌을 받을 수 있었지만.. 이건 그것조차 안 되는 거 같다. 

답을 확인해도 "이게 뭔소리지?" 그러다가 겨우겨우 이해를 하면 "대체 어떻게 이런 생각을 하지?" 그냥 사람을 너무 초라하게 만든다.

근데 이런 게 또 남들이 볼 때는 그렇게 엄청 어려운 문제는 아닌 듯 하다. 그 사실이 좌절감을 더 증폭시킨다.

사실 아직도 완벽하게 이해하진 못했다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

문제의 키 포인트는 다음 문장이다.

"인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다."

일단, 처음으로 양 끝 기준점이 되는 첫 원소와 마지막 원소 둘은 반드시 정답에 포함될 수 있다.

(이것도 왜 그런지 모르겠다..)

마지막까지 살릴 수 있는지 없는지를 판단하는 원소의 양 옆에 기준점 두 개를 잡는다.

대상 원소 하나 + 기준점 원소 둘 이 셋 중에서 대상 원소가 가장 큰 원소가 아니라면 대상 원소를 지울 수 있다.

다른 원소들을 전부 먼저 지우고 이 셋만 남아있을 때 (이떄 세 원소는 연속하는 위치일 것임) 만약 가운데에 위치한 대상 원소가 가장 크다면? 그럼 더 작은 양 옆의 원소를 모두 날릴 수 없다. (더 작은 원소 삭제는 한 번만 가능하니까)

(근데.. 더 큰 원소만 지우면서  이 셋만 남기는 게 가능하다는 것이 어떻게 보장되지? 이걸 모르겠다)

양 쪽 끝점에 대한 검사를 반복 한 번으로 동시에 하는 코드도 있었지만 그건 이해를 못 하겠어서 다른 방법을 보고 풀었다. (엄밀히 말하면 내가 푼 것도 아니긴 하지만)

1. 왼쪽 끝점보다 대상 원소가 작은지 검사. 

2. 오른쪽 끝점보다 대상 원소가 작은지 검사.

(1, 2 단계에서 대상 원소가 더 작아서 정답에 포함되는 경우엔 끝점을 변경. 이것도 왜 하는지 이해 못했다)

3. 둘 중 하나라도 1이라면 어쨌든 세 원소 중 가장 큰 건 아니라는 뜻이니 정답에 포함됨.

다 적고보니 그냥 아는 게 없는 수준이네 ㅋㅋ 이 글 자체를 쓰지 말 걸 그랬나.. 

하

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

문제 설명

카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다.
수정해야 할 소스 파일이 너무 많아서 고민하던 콘은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.

용어의 정의

'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다.
그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다.
예를 들어, "(()))("와 같은 문자열은 균형잡힌 괄호 문자열 이지만 올바른 괄호 문자열은 아닙니다.
반면에 "(())()"와 같은 문자열은 균형잡힌 괄호 문자열 이면서 동시에 올바른 괄호 문자열 입니다.

'(' 와 ')' 로만 이루어진 문자열 w가 균형잡힌 괄호 문자열 이라면 다음과 같은 과정을 통해 올바른 괄호 문자열로 변환할 수 있습니다.

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.

2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.

3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.

    3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.

4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.

    4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.

    4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.

    4-3. ')'를 다시 붙입니다.

    4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.

    4-5. 생성된 문자열을 반환합니다.

균형잡힌 괄호 문자열 p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 올바른 괄호 문자열로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.

매개변수 설명

• p는 '(' 와 ')' 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수입니다.
• 문자열 p를 이루는 '(' 와 ')' 의 개수는 항상 같습니다.
• 만약 p가 이미 올바른 괄호 문자열이라면 그대로 return 하면 됩니다.

입출력 예

presult

입출력 예에 대한 설명

입출력 예 #1
이미 올바른 괄호 문자열 입니다.

입출력 예 #2

• 두 문자열 u, v로 분리합니다.
  • u = ")("
  • v = ""
• u가 올바른 괄호 문자열이 아니므로 다음과 같이 새로운 문자열을 만듭니다.
  • v에 대해 1단계부터 재귀적으로 수행하면 빈 문자열이 반환됩니다.
  • u의 앞뒤 문자를 제거하고, 나머지 문자의 괄호 방향을 뒤집으면 ""이 됩니다.
  • 따라서 생성되는 문자열은 "(" + "" + ")" + ""이며, 최종적으로 "()"로 변환됩니다.

입출력 예 #3

• 두 문자열 u, v로 분리합니다.
  • u = "()"
  • v = "))((()"
• 문자열 u가 올바른 괄호 문자열이므로 그대로 두고, v에 대해 재귀적으로 수행합니다.
• 다시 두 문자열 u, v로 분리합니다.
  • u = "))(("
  • v = "()"
• u가 올바른 괄호 문자열이 아니므로 다음과 같이 새로운 문자열을 만듭니다.
  • v에 대해 1단계부터 재귀적으로 수행하면 "()"이 반환됩니다.
  • u의 앞뒤 문자를 제거하고, 나머지 문자의 괄호 방향을 뒤집으면 "()"이 됩니다.
  • 따라서 생성되는 문자열은 "(" + "()" + ")" + "()"이며, 최종적으로 "(())()"를 반환합니다.
• 처음에 그대로 둔 문자열에 반환된 문자열을 이어 붙이면 "()" + "(())()" = "()(())()"가 됩니다.

풀이 .

class Solution {
    public boolean isRight(String str) {
        int len = str.length();
        int lCnt = 0, rCnt = 0;
        for(int i = 0; i < len; i++) {
            char c = str.charAt(i);
            if(c == '(') lCnt += 1;
            else rCnt += 1;
            if(rCnt > lCnt) return false;
        }
        // balanced 는 항상 보장되므로 반복 이후에 또 검사할 필요 없음
        return true;
    }

    public String changeBracket(String str) {
        StringBuilder result = new StringBuilder();
        int len = str.length();
        for(int i = 0; i < len; i++) {
            char c = str.charAt(i);
            if(c == '(') result.append(')');
            else result.append('(');
        }
        return result.toString();
    }

    public String recursive(String input) {
        if(input.equals("")) {
            return input;
        }

        StringBuilder w = new StringBuilder();
        StringBuilder u = new StringBuilder();
        StringBuilder v = new StringBuilder();
        w.append(input);

        // w -> u, v 반으로 가르기
        int lCnt = 0, rCnt = 0;
        int idx = 0;
        for(idx = 0; idx < w.length(); idx++) {
            char c = w.charAt(idx);
            u.append(c);
            if(c == '(') lCnt += 1;
            else rCnt += 1;
            if(lCnt == rCnt) break;  // 최소 단위의 균형잡힌 문자열 u 생성
        }
        for(int i = idx + 1; i < w.length(); i++) {
            char c = w.charAt(i);
            v.append(c);
        }

        if(isRight(u.toString())) {
            String processedV = recursive(v.toString());
            u.append(processedV);
            return u.toString();
        }else {
            String processedV = recursive(v.toString());
            StringBuilder ans = new StringBuilder();
            ans.append('(');
            ans.append(processedV);
            ans.append(')');

            u.deleteCharAt(0);  // 양 끝 제거
            u.deleteCharAt(u.length() - 1);
            ans.append(changeBracket(u.toString()));  // 모든 괄호 바꾼 U 붙이기

            return ans.toString();
        }
    }

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

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        String p = "()))((()";
        String ans = sol.solution(p);
        System.out.println(ans);
    }
}

기본적인 구현력을 묻는 문제.

문제에서 시킨대로 그대로 짜면 잘 돌아간다. 

솔직히 문제 설명이 보자마자 딱! 알아들을 수 있을 만큼 명확하지는 않은 듯 하다.

푸는 것 보다 문제를 이해하는 게 더 어려웠던 문제.

주의할 점을 몇 가지 적어보자면..

1. W -> U, V를 무슨 기준으로 나누라는 말인가? 내 맘대로?

U는 W의 왼쪽 편에서 뽑아낼 수 있는 최소 크기의 "균형잡힌 문자열"이다. 

(u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 한다. 라는 부분)

사실 문제에 명확히 설명되어있긴 한데 왜 눈에 잘 안 들어오는지 모르겠다.

2. 균형잡힌 문자열인지 확인하는 절차는 굳이 거칠 필요가 없다.

매개변수 P에 대해서 균형잡힌 문자열이 보장된다고 명시되어 있다.

U는 애초에 균형잡힌 문자열을 빼라고 명시되어 있고 W에서 U를 뺀 나머지 V도 필연적으로 균형잡힌 문자열일 수밖에 없다.

3. 지시사항 4-4의 함정

다른 건 다 잘 이해했는데 이 부분을 잘못 이해해서 틀렸었다.

지시사항 4-4는 양 옆을 제거하고 남은 U 문자열의 방향을 반대로 돌리라는 말이 아니다.

자세히 읽어보면 "문자열의 방향을 뒤집어라"가 아니라 "문자열의 괄호의 방향을 뒤집어라"라고 되어있다.

문제를 정말 '자세히' 읽어야 했던 문제.

구현 자체는 재귀와 StringBuilder를 사용해 쉽게 해결할 수 있었다.

문제 설명

카카오 프렌즈 컬러링북

출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.)

그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자.

위의 그림은 총 12개 영역으로 이루어져 있으며, 가장 넓은 영역은 어피치의 얼굴면으로 넓이는 120이다.

입력 형식

입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n 크기의 2차원 배열 picture로 주어진다. 제한조건은 아래와 같다.

• 1 <= m, n <= 100
• picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다.
• picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.

출력 형식

리턴 타입은 원소가 두 개인 정수 배열이다. 그림에 몇 개의 영역이 있는지와 가장 큰 영역은 몇 칸으로 이루어져 있는지를 리턴한다.

예제 입출력

mnpictureanswer

예제에 대한 설명

예제로 주어진 그림은 총 4개의 영역으로 구성되어 있으며, 왼쪽 위의 영역과 오른쪽의 영역은 모두 1로 구성되어 있지만 상하좌우로 이어져있지 않으므로 다른 영역이다. 가장 넓은 영역은 왼쪽 위 1이 차지하는 영역으로 총 5칸이다.

풀이 .

class Solution {
    int m, n;
    int numberOfArea;
    int sizeOfArea, maxSizeOfOneArea;
    int[] rArr = {-1, 1, 0, 0};
    int[] cArr = {0, 0, -1, 1};

    public void dfs(int r, int c, int dept, int[][] map, boolean[][] check) {
        for(int i = 0; i < 4; i++) {
            int nr = r + rArr[i];
            int nc = c + cArr[i];
            if(-1 < nr && nr < m && -1 < nc && nc < n) {
                if(!check[nr][nc] && map[nr][nc] == map[r][c]) {
                    sizeOfArea += 1;
                    check[nr][nc] = true;
                    dfs(nr, nc, dept + 1, map, check);
                }
            }
        }
    }

    public int[] solution(int m, int n, int[][] picture) {
        this.m = m;
        this.n = n;

        boolean[][] check = new boolean[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(!check[i][j] && picture[i][j] != 0) {
                    sizeOfArea = 1;
                    check[i][j] = true;
                    dfs(i, j, 1, picture, check);
                    maxSizeOfOneArea = Math.max(maxSizeOfOneArea, sizeOfArea);
                    numberOfArea += 1;
                }
            }
        }

        int[] answer = new int[2];
        answer[0] = numberOfArea;
        answer[1] = maxSizeOfOneArea;
        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
    }
}

기본적인 DFS 문제. 

단지번호 붙이기 문제 (codeung.tistory.com/178) 와 거의 동일한 문제이다.

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

문제 설명

2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT

입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 TUE를 반환하세요.

제한 조건

• 2016년은 윤년입니다.
• 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다)

입출력 예

abresult

풀이 .

class Solution {
    public String solution(int a, int b) {
        String answer = "";

        int[] months = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        String[] days = {"THU", "FRI", "SAT", "SUN", "MON", "TUE", "WED"};
        int total = 0;
        for(int i = 0; i < a; i++) {
            total += months[i];
        }
        total += b;
        answer = days[total % 7];

        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
    }
}

평범한 날짜 계산 문제.

딱히 코멘트가 필요 없다.

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

문제 설명

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 1 이상 1,000 이하입니다.

입출력 예

nresult

풀이 .

class Solution {
    public int[] solution(int n) {
        int max = 0;
        for(int i = 1; i <= n; i++) {
            max += i;
        }
        int[] answer = new int[max];
        int[][] arr = new int[n][n];

        int row = 0, col = 0, input = 1;
        arr[row][col] = input;
        while(input < max) {
            // 상 -> 하 (row++)
            while(row + 1 < n && arr[row+1][col] == 0) {
                arr[++row][col] = ++input;
            }
            // 좌 -> 우 (col++)
            while(col + 1 < n && arr[row][col+1] == 0) {
                arr[row][++col] = ++input;
            }
            // 우하 -> 좌상 (row--, col--)
            while(row - 1 > 0 && col - 1 > 0 && arr[row-1][col-1] == 0) {
                arr[--row][--col] = ++input;
            }
        }

        int idx = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                answer[idx++] = arr[i][j];
            }
        }
        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
    }
}

이차원 배열로 삼각형을 표현할 수 있다.

(대각선을 그었을 때 아래쪽 삼각형에 해당하는 좌표만 사용)

문제의 경우에서 이동할 수 있는 방향은 총 세 가지.

1. 위쪽에서 아래쪽으로 수직 이동

2. 왼쪽에서 오른쪽으로 수평 이동

3. 오른쪽 아래에서 왼쪽 위로 대각 이동

각 경우에 대한 while()문을 만들어 준다.

처음에는 이전 좌표의 값에 +1을 해주려고 했었는데 이렇게 하려니 이동 방향을 꺾을 때마다 이전 좌표 값을 다르게 찾아야 하는 방식이 까다로웠다.

배열에 할당하는 최대 숫자 max를 먼저 구하고 input : 1 ~ max 를 할당하도록 하여 이 문제를 해결했다.

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

문제 설명

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

제한사항

• W, H : 1억 이하의 자연수

입출력 예

WHresult

입출력 예 설명

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

풀이 .

->

예제를 바탕으로 조건을 찾아보고자 했다.

예제의 경우 w : h = 8 : 12 이고, 이걸 최대공약수 4로 나누면 2 : 3이 된다.

즉, 전체 map에서 선분이 지나가는 2 x 3 크기의 덩어리가 gcd개 존재하게 된다.

하지만 이 6칸의 사각형이 모두 선분에 걸치는 것은 아니다. 살릴 수 있는 부분도 존재한다. 이걸 계산하는 게 관건인 듯 하다.

라고 여기까지 생각했는데.. 자세히 생각해보니 굳이 w : h가 1이 아닌 최대공약수를 갖도록 맞아떨어지는 수가 주어진다는 보장이 없다. (이걸 굳이 여러 블럭으로 나누려고 할 필요가 없었다)

결국 다시 원점이다.

나누어 떨어지지 않는 경우에 대한 조건을 떠올리기 위해 w : h = 8 : 5 로 직접 그려보았다.

끝 열이 겹치는 형태로 2 x 1, 3 x 1의 3, 2개씩 반복되었다.

여기에서 규칙을 찾을 수 없을까?

(틀린 접근법이었다)

여기에서 더 나아가지 못하고 답을 확인했다.

우선 딱 나누어 떨어지지 않는 경우(gcd = 1인 경우)는 그냥 w x h사이즈의 블록이 gcd개 만큼 반복된다고 보면 된다.

즉,  (w / gcd) * (h / gcd) 사이즈가 gcd번 반복되는 일반식을 세우면 되는 것이다.

위에서 관건이라고 언급했던 이 gcd개의 덩어리에서 선분을 지나는 칸을 구하는 것도 일반식을 세울 수 있었다.

이 w/gcd = w', h/gcd = h' 으로 두어 이 덩어리의 사이즈가 w' x h' 라고 두었을 때, 선분이 지나는 칸의 개수는 w' + h' - 1개가 된다.

일반식이기 때문에 gcd가 몇이든 항상 동일하게 적용된다.

어떻게 이런 식이 도출되는가?

->

(w' x h')블록 안에서 선분은 항상 행, 열 중 하나에 대해서만 이동한다. 행과 열을 동시에 이동하는 경우, 즉, 대각선 방향으로 한 번에 이동하는 경우는 없다는 것이다. 

(전체를 놓고 봤을 때 대각선 방향으로 이동하는 경우가 있긴 하지만 이건 다음 (w' x h')블록으로 이동하는 것이다. 즉, 위의 빨간 글씨의 문장은 항상 성립하게 된다.)

그럼 결국 선분은 (w' x h')블록 안에서 행을 h'번, 열을 w'번 이동하게 된다. 하지만 블록의 맨 왼쪽위 칸은 첫번째 행과 첫번째 행을 동시에 표현하기 때문에 이 중복에 대한 처리로 -1을 해줘야 한다.

이렇게 w' + h' - 1 이란 식을 도출할 수 있게 된다.

결국 전체 맵에서 손상되지 않은 사각형의 개수는

(w * h) - (w' + h' - 1) * gcd 이라는 식을 통해 구할 수 있게 된다. (단, w' = w / gcd, h' = h / gcd)

class Solution {
    public int gcd(int a, int b) {
        if(b == 0) return a;
        else return gcd(b, a % b);
    }

    public long solution(int w, int h) {
        long answer = 0;
        int gcd = gcd(w, h);
        answer = ((long)w * (long)h) - (((long)w / gcd) + ((long)h / gcd) - 1) * gcd;
        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
    }
}

풀이를 찾아보며 BigInteger 클래스를 사용해서 gcd를 좀 더 편하게 구할 수 있는 방법이 있단 걸 알았다.

사실 원래 방식도 별 거 없어서 그게 그거이긴 하다.

(속도는 원래 방식이 아주 조금 더 빠른 듯 하다)

    import java.math.BigInteger;
    
    public int gcd(int a, int b) {
        BigInteger bi1 = BigInteger.valueOf(a);
        BigInteger bi2 = BigInteger.valueOf(b);
        BigInteger gcd = bi1.gcd(bi2);
        return gcd.intValue();
    }

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

문제 설명

124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.

1. 124 나라에는 자연수만 존재합니다.
2. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.

예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.

10진법124 나라10진법124 나라

자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• n은 500,000,000이하의 자연수 입니다.

입출력 예

nresult

풀이 .

class Solution {
    public String solution(int n) {
        StringBuilder sb = new StringBuilder();
        while(n > 0) {
            int mod = n % 3;
            if(mod == 0) {
                mod = 4;
                n = n / 3 - 1;
            } else
                n /= 3;
            sb.insert(0, String.valueOf(mod));
        }
        return sb.toString();
    }
}

public class Main {
    Solution sol = new Solution();

}

문제를 보자마자 3진법을 사용하면 되겠다는 생각까지는 도달했다.

처음에는 단순히 3진법으로 나온 0, 1, 2를 각각 크기 순서대로 1, 2, 4로 치환하면 될 것이라고 생각했지만 잘못된 풀이였다.

n을 나눈 나머지가 1, 2일 때는 그걸 그대로 쓰면 되지만 0이 나올 떄는 몫을 -1 하고 나머지를 4로 바꿔줘야 한다.

(솔직히 왜 그래야 하는지 제대로 이해 못 했다.)