더 이상 물러설 곳이 없다

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) 와 거의 동일한 문제이다.

www.acmicpc.net/problem/1149

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

예제 입력 1

3

26 40 83

49 60 57

13 89 99

예제 출력 1

96

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        int[][] rgb = new int[n][3];
        int[][] dp = new int[n][3];  // dp[n][R or G or B] = n에 해당 색깔 놓을 수 있는 최소값
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 3; j++) {
                rgb[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp[0][0] = rgb[0][0];
        dp[0][1] = rgb[0][1];
        dp[0][2] = rgb[0][2];
        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + rgb[i][0];
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + rgb[i][1];
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + rgb[i][2];
        }

        int ans = Math.min(dp[n-1][0], Math.min(dp[n-1][1], dp[n-1][2]));
        System.out.println(ans);
    }
}

대놓고 DP문제인데.. 보자마자 DP를 떠올렸어야 하는 문제인데 그러지 못했다.

처음에는 모든 조합을 구해서 조건을 만족하는지 검사해볼까 했지만 무조건 시간 초과가 나는 방법이다.

3^N개의 조합이 나오게 되는데 N이 최대 1000이기 때문에 최대 3^1000가지의 조합

거기다 조건 검사 한 번에 O(N) 시간.. 이건 무조건 시간 초과다.

결국 어떤 알고리즘이 사용되는지 확인했고 어려운 문제는 아니라서 DP를 확인하자마자 바로 풀어낼 수 있었다.

조건이 3개나 존재하지만 결국 다 같은 말이다. (일부러 헷갈리게 하려고 같은 말을 다른 식으로 여러 번 써놓은 건가?)

그냥 나와 인접하는 양 옆의 집과 다른 색을 가져야 한다는 얘기다.

집을 하나 놓을 때마다 이전 집과 다른 색들 중에서 고르면 되는 것이다.

DP에 저장하는 값은 "dp[n][color] = n번째 집에 color 색을 놓았을 때 가능한 최소값" 이다.

DP 배열을 1차원으로 할까도 생각해봤지만 그럼 다른 색을 놓아야 하는 조건을 검사하는 게 번거로워진다. 그냥 2차원을 사용하자.

www.acmicpc.net/problem/1662

문제

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오.

입력

첫째 줄에 압축된 문자열 S가 들어온다. S의 길이는 최대 50이다. 문자열은 (, ), 0-9사이의 숫자로만 들어온다.

출력

첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 int범위다.

예제 입력 1

33(562(71(9)))

예제 출력 1

19

풀이 1. (틀린 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        Stack<Character> stk = new Stack<>();
        for(int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == ')') break;
            stk.push(str.charAt(i));
        }

        int length = 0;
        while(!stk.isEmpty()) {
            if(stk.peek() == '(') {
                stk.pop();  // 괄호 제거
                length = length * (stk.pop() - '0');  // 압축 해제
            }else {
                length += 1;
                stk.pop();
            }
        }
        System.out.println(length);
    }
}

예제의 경우에서만 생각하고 코드를 짜서 틀렸다.

이 코드는 하나의 괄호 안에 여러 괄호가 포함되는 경우를 처리하지 못한다.

풀이 2. (정답 코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split("");
        Stack<String> stk = new Stack<>();  // 문자열의 길이도 스택에 함께 넣는다. 길이는 한자리를 넘어갈 수 있으므로 반드시 String 사용

        for(int i = 0; i < arr.length; i++) {
            if(!arr[i].equals(")")) {
                stk.push(arr[i]);  // ")" 등장할때마다 로직 수행. ")"전까지는 전부 스택에 담는다
            }else {
                int cnt = 0;
                while(!stk.peek().equals("(")) {  // 괄호를 풀기 위해 "(" 나올 때까지 pop 한다
                    String output = stk.pop();
                    if(output.equals("*")) {
                        int len = Integer.parseInt(stk.pop());
                        cnt += len;
                    }else {
                        cnt += 1;
                    }
                }
                stk.pop();  // "(" 제거
                int len = Integer.parseInt(stk.pop());
                cnt *= len;  // 압축 해제
                stk.push(String.valueOf(cnt));
                stk.push("*");  // "*" 밑에 있는 숫자는 문자열이 아니라 숫자의 길이를 나타냄
            }
        }

        int ans = 0;
        while(!stk.isEmpty()) {
            if(stk.peek().equals("*")) {
                stk.pop();
                ans += Integer.parseInt(stk.pop());
            }else {
                stk.pop();
                ans += 1;
            }
        }
        System.out.println(ans);
    }
}

같은 레벨에 있는 여러 괄호를 정상적으로 처리하려면?

(처음에 생각한 로직)

1. 일단 ")"이 등장할 때마다 처리 로직을 수행해야 하는 부분은 명확하다고 봤다. ")"이 나오기 전까지 스택에 담고 ")"이 나오면 오직 수행

2. 그 후 "("이 나오기 전까지 문자들을 빼면서 개수(길이)를 센다.

3. "("이 나오면 제거하고 그 다음에 나오는 숫자를 빼서 지금까지 센 길이에 곱한다. (= 압축 해제)

4. 압축이 해제된 길이 만큼의 아무 문자나 스택에 넣는다.(중요한 건 길이이기 때문에 어떤 문자를 넣든 중요하지 않다)

4번 단계에서 압축 해제한 문자를 다시 넣는 것이 조금은 낭비라고 느껴졌다.

하지만, 최초 입력 문자열의 길이는 최대 50인데, 가장 압축을 많이 하는 경우인 "9( )" 사이에 47개의 숫자를 넣는 경우를 생각하면 47 * 9 = 463 으로 그다지 크지 않다.

N 제한이 작아서 무리가 없는 수준이지만 그래도 이를 줄일 수 있는 더 좋은 방법이 있었다.

스택에 기존 문자열과 압축 해제한 문자열의 길이를 함께 저장하는 것이다.

들어가는 숫자가 문자열이 아니라 문자열의 길이임을 표시하기 위해 "*"를 함께 넣어서 구분한다.

자료구조 문제에서 기초적인 구현력을 요구하는 경우가 많은 것 같다.

나중에 자료구조만 따로 모아서 풀어봐야겠다.

www.acmicpc.net/problem/14719

문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

예제 입력 1

4 4

3 0 1 4

예제 출력 1

5

예제 입력 2

4 8

3 1 2 3 4 1 1 2

예제 출력 2

5

예제 입력 3

3 5

0 0 0 2 0

예제 출력 3

0

힌트

힌트 1:

힌트 2:

힌트 3:

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

class Block {
    int w, h;
    Block(int w, int h) {
        this.w = w;
        this.h = h;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        Block[] arr = new Block[W];
        int sumOfBlock = 0;

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < W; i++) {
            int h = Integer.parseInt(st.nextToken());
            arr[i] = new Block(i, h);
            sumOfBlock += h;
        }

        // 배열의 시작부터 오름차순 블록만 받아서 저장
        Stack<Block> leftStk = new Stack<>();
        Stack<Block> rightStk = new Stack<>();
        int maxHeight = 0;
        for(int i = 0; i < arr.length; i++) {
            if(arr[i].h > maxHeight) {
                maxHeight = arr[i].h;
                leftStk.push(arr[i]);
            }
        }

        // 배열의 끝부터 오름차순 블록만 받아서 저장
        maxHeight = 0;
        for(int i = arr.length - 1; i >= 0; i--) {
            if(arr[i].h > maxHeight) {
                maxHeight = arr[i].h;
                rightStk.push(arr[i]);
            }
        }

        // 모든 면적 계산
        int ans = (rightStk.peek().w - leftStk.peek().w + 1) * maxHeight;
        int beforeW = leftStk.pop().w;
        while(!leftStk.isEmpty()) {
            int w = leftStk.peek().w;
            int h = leftStk.peek().h;
            ans += (beforeW - w) * h;
            beforeW = w;
            leftStk.pop();
        }
        beforeW = rightStk.pop().w;
        while(!rightStk.isEmpty()) {
            int w = rightStk.peek().w;
            int h = rightStk.peek().h;
            ans += (w - beforeW) * h;
            beforeW = w;
            rightStk.pop();
        }

        // 전체 면적에서 블록 면적 제거
        ans -= sumOfBlock;
        System.out.println(ans);
    }
}

codeung.tistory.com/253 와 똑같은 문제.

스택을 이용하여 해결했지만 굳이 스택일 필요는 없다. 어레이리스트나 최대힙도 가능.

www.acmicpc.net/problem/2304

문제

N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.

1. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
2. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
3. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
4. 지붕의 가장자리는 땅에 닿아야 한다.
5. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.

그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.

그림1 . 기둥과 지붕(굵은 선)의 예

창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.

기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.

입력

첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.

출력

첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.

예제 입력 1

7

2 4

11 4

15 8

4 6

5 3

8 10

13 6

예제 출력 1

98

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;
import java.util.StringTokenizer;

class Pillar implements Comparable<Pillar>{
    int left;
    int height;
    Pillar(int left, int height) {
        this.left = left;
        this.height = height;
    }
    @Override
    public int compareTo(Pillar o) {
        return this.left < o.left ? -1 : 1;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        Stack<Pillar> leftStk = new Stack<>();
        Stack<Pillar> rightStk = new Stack<>();
        ArrayList<Pillar> pillars = new ArrayList<>();

        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int L = Integer.parseInt(st.nextToken());
            int H = Integer.parseInt(st.nextToken());
            pillars.add(new Pillar(L, H));
        }
        Collections.sort(pillars);  // 입력 순서 보장되지 않는다. 정렬 필요

        // 가운데의 가장 높은 기둥을 기준으로 left, right 스택 채운다. 단, 높이가 증가하는 기둥만 채운다
        int maxHeight = 0;
        int len = pillars.size();
        for(int i = 0; i < len; i++) {
            if(maxHeight < pillars.get(i).height) {
                maxHeight = pillars.get(i).height;
                leftStk.push(pillars.get(i));
            }
        }
        maxHeight = 0;
        for(int i = len - 1; i >= 0; i--) {
            if(maxHeight < pillars.get(i).height) {
                maxHeight = pillars.get(i).height;
                rightStk.push(pillars.get(i));
            }
        }

        int ans = (rightStk.peek().left - leftStk.peek().left + 1) * rightStk.peek().height;
        int beforeLeft = leftStk.pop().left;
        while(!leftStk.isEmpty()) {
            int left = leftStk.peek().left;
            int height = leftStk.peek().height;
            ans += (beforeLeft - left) * height;
            beforeLeft = left;
            leftStk.pop();
        }

        int beforeRight = rightStk.pop().left + 1;
        while(!rightStk.isEmpty()) {
            int right = rightStk.peek().left + 1;
            int height = rightStk.peek().height;
            ans += (right - beforeRight) * height;
            beforeRight = right;
            rightStk.pop();
        }

        System.out.println(ans);
    }
}

처음 봤을 때는 문제의 그림을 보고 이차원 배열을 탐색하는 그래프 문제라고 생각했다.

DFS, BFS 문제를 너무 많이 풀다 보니까 일단 무작정 그런 쪽으로 생각하게 되는 거 같다.

정말 대놓고 보이는 게 아닌 이상은 항상 어떤 어떤 알고리즘을 적용시키는 게 좋을지를 먼저 생각해보자.

스택으로 분류 되어있지만 딱히 스택일 필요는 없는 문제. 그냥 어레이리스트를 사용해도 된다.

창고다각형은 가장 높은 기둥을 가운데에 두고 그 양 옆으로 높이가 점점 내려가는 모양을 띄게 된다.

가장 높은 기둥을 중앙일 때,

왼쪽 부분에서는 높이가 점점 올라가는 기둥들만,

오른쪽 부분에서는 높이가 점점 내려가는 기둥들만 따로 모은다.

그 후 넓이를 계산해주면 된다.

주의할 점은, 가운데에 오는 가장 높은 기둥이 여러 개일 경우를 대비하여 이것도 따로 계산해줘야 한다는 것이다.

알고나면 굉장히 간단한 해법인데 생각해내기가 쉽지 않았다.

www.acmicpc.net/problem/11403

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

예제 입력 1

3

0 1 0

0 0 1

1 0 0

예제 출력 1

1 1 1

1 1 1

1 1 1

예제 입력 2

7

0 0 0 1 0 0 0

0 0 0 0 0 0 1

0 0 0 0 0 0 0

0 0 0 0 1 1 0

1 0 0 0 0 0 0

0 0 0 0 0 0 1

0 0 1 0 0 0 0

예제 출력 2

1 0 1 1 1 1 1

0 0 1 0 0 0 1

0 0 0 0 0 0 0

1 0 1 1 1 1 1

1 0 1 1 1 1 1

0 0 1 0 0 0 1

0 0 1 0 0 0 0

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;

    static int[][] map = null;
    static int[][] ans = null;
    static int n;

    public static void dfs(int start, int now) {
        for(int next = 0; next < n; next++) {
            if(map[now][next] == 1 && ans[start][next] == 0) {  // ans로 방문 여부 체크
                ans[start][next] = 1;
                dfs(start, next);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        map = new int[n][n];
        ans = new int[n][n];
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(map[i][j] == 1 && ans[i][j] == 0) {
                    ans[i][j] = 1;
                    dfs(i, j);
                }
            }
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                System.out.print(ans[i][j] + " ");
            }
            System.out.println();
        }
    }
}

단방향 그래프의 탐색 문제.

항상 좌표로 표시되는 맵에서 양방향 그래프 탐색으로만 풀다가 단방향을 풀려니 좀 헷갈렸다.

이 문제는 탐색 점을 row, col으로 표시를 하는 것은 부적절하며 시작점을 계속 가지고 있어야 한다.

탐색을 할 때 1로 채우는 것은 now->next가 아니라 start->next 이다.