더 이상 물러설 곳이 없다

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를 사용해 쉽게 해결할 수 있었다.

상속은 객체지향 프로그래밍에서 굉장히 중요하다.

하지만 관계형 데이터베이스에는 상속 개념이 존재하지 않는다

RDB에는 상속 개념과 매우 유사한 슈퍼-서브 타입이라는 관계 개념이 존재하는데, JPA가 패러다임의 불일치 해소라는 그 목적성에 맞게 객체지향의 상속을 RDB의 슈퍼-서브 타입으로 잘 매핑해준다.

RDB에서 슈퍼-서브 타입을 표현하는 방식은 세 가지가 있는데 JPA는 이 방법을 모두 지원한다.

1. 조인 전략 (가장 많이 사용됨)

가장 바람직한(?) 모델로 평가받는 조인을 이용한 방식이다.

조인 전략이 구조적으로도 객체지향의 상속을 가장 잘 나타내지 않나 싶다.

부모 클래스의 테이블이 공통속성을 가지고 자식 테이블들은 각자의 고유한 컬럼들을 따로 갖는다.

부모의 PK를 자식의 PK이자 FK로 사용했는데, JAVA에서 자식 객체를 검색할 경우 이를 통해 조인 쿼리를 날려서 찾아낸다. 

테이블이 정규화 되어있기 때문에 효율적인 구조라 할 수 있으며 쓸 데 없이 낭비되는 저장공간이 없다는 장점이 있다.

단점으로는 조회할 때 조인 사용량이 높아 성능이 저하될 수 있다는 부분, 새로운 데이터 저장 시 부모, 자식 테이블에 따로따로 insert문을 날려야 한다는 점이 있다.

@Entity
@Inheritance(strategy = InheritanceType.JOINED)  // 상속 매핑 전략 선택
@DiscriminatorColumn  // 자식 객체를 구분하기 위한 Dtype
public abstract class Item {
    // 부모 테이블은 공통된 속성에 대한 컬럼만을 갖는다
    @Id @GeneratedValue
    private Long id;

    private String name;
    private int price;
}

2. 단일 테이블 전략 (디폴트)

테이블 하나에다 모든 자식의 정보를 때려넣는 방식이다.

상속 매핑 전략을 따로 설정하지 않으면 이 방식이 기본으로 적용된다.

(다른 자식의 속성 컬럼에 대해선 NULL을 갖는다)

Dtype 컬럼의 존재가 필수적이다. 조인 전략에서는 굳이 Dtype이 없어도 조인을 통해 알아낼 수는 있지만 단일 테이블 전략에서는 Dtype이 없으면 객체를 구분할 수가 없다.

이러한 이유로 @DiscriminatorColumn을 넣지 않아도 자동적으로 Dtype 컬럼이 추가된다.

하나의 테이블에 모든 정보가 다 담겨있기 떄문에 조인 없이 바로 select가 가능하여 조회 성능이 빠르다는 장점이 있다.

단점으로는 다른 자식들에 대한 고유 속성 컬럼은 NULL값으로 가지고 있어야하므로 자식 엔티티의 컬럼들은 전부 다 NULL이 허용되며, 테이블이 너무 커져버릴 수 있다는 점이 있다.

@Entity
@Inheritance(strategy = InheritanceType.SINGLE_TABLE)  // 전략 선택 안 하면 디폴트로 싱글 테이블 적용
@DiscriminatorColumn  // 자식 객체를 구분하기 위한 Dtype (싱글 테이블에선 명시하지 않아도 자동 생성됨)
public abstract class Item {

    @Id @GeneratedValue
    private Long id;

    private String name;
    private int price;
}

3. 테이블 퍼 클래스 전략 (사용하지 말 것!)

부모 클래스에 대한 테이블은 존재하지 않는다.

각 자식 클래스 별로 자신만의 테이블을 갖는데, 이때 부모가 갖고 있어야 할 고유한 속성들을 모든 자식 클래스가 자신의 테이블에 갖고 있는 방식이다.

서브 타입(자식)에 대한 구분이 명확하다는 것과 싱글 테이블 전략과는 다르게 NOT NULL 조건을 사용할 수 있다는 장점이 있다.

단점으로는 하나의 부모에 자식이 여럿일 경우 조회 성능이 굉장히 느려지게 된다는 점이 있다.

각각의 자식 테이블 중에 찾고자 하는 객체가 어느 곳에 있는지 알 수 없기 때문에 모든 테이블을 검사해야 한다.

이를 위해서 UNION 을 사용해 모든 테이블을 합치고 그것을 조회한다.

@Entity
@Inheritance(strategy = InheritanceType.TABLE_PER_CLASS)  // 웬만하면 사용을 자제해야 하는 전략
@DiscriminatorColumn  // 자식 객체를 구분하기 위한 Dtype
public abstract class Item {

    @Id @GeneratedValue
    private Long id;

    private String name;
    private int price;
}

위 세 가지 방법 모두 부모 클래스는 abstract로 생성해야 한다.

그렇지 않으면 JPA가 부모 클래스의 개별 테이블까지 함께 만들어버린다.

(Item 클래스는 공통 속성을 한 번에 관리하기 위함일 뿐, Item에 대한 개별 테이블은 필요 없다)

문제 설명

카카오 프렌즈 컬러링북

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

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

위의 그림은 총 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 와 똑같은 문제.

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

다대다 관계의 경우 그대로 사용하지 못하고 반드시 정규화를 통해 중간 테이블을 만들어줘야 한다.

이러한 관계가 있을 때 반드시 중간 중간 테이블을 두어 일대다+다대일 형태로 변형해줘야 한다.

JPA에서는 @ManyToMany를 통해 연관관계를 매핑할 경우 하이버네이트가 위와 같은 중간 테이블을 알아서 만들어서 처리해준다.

@Entity
public class Member {

    @Id @GeneratedValue
    @Column(name = "MEMBER_ID")
    private Long id;

    @Column(name = "USERNAME")
    private String username;

    @ManyToMany
    @JoinTable(name = "새로 만들어줄 중간 테이블 이름")
    private List<Product> products = new ArrayList<>();
}
.
.
.
@Entity
public class Product {

    @Id @GeneratedValue
    private Long id;

    private String name;

    @ManyToMany(mappedBy = "products")
    private List<Member> members = new ArrayList<>();
}

위와 같이 @ManyToMany로 양방향 매핑 되어있을 때 (굳이 양방향이어야 할 필요는 없음. 단방향이어도 괜찮다) Member의 @JoinTable(name = "새로운 테이블 명")을 통해 중간 테이블을 따로 만들어준다.

하지만 이러한 방식은 실무에서 절대로 사용하면 안 된다.

중간테이블을 만들고 PK, FK 쌍을 알아서 매핑해주는 것 까지는 문제가 없는데, 실무 레벨에서는 이러한 테이블 매핑에 필요한 필수적인 정보들 외에도 중간 테이블이 가져야하는 여러 가지 컬럼들이 있을 수 있다.

(예를들어 멤버 - 오더 - 상품 이렇게 되어있을 경우 오더가 발생한 시간이라든가 하는 정보들)

하이버네이트에 의해 생성된 중간 테이블은 관계 설정에 필수적으로 필요한 정보들만 담겨있을 뿐 이러한 비즈니스 로직상 필요한 정보들은 담기지 않는다.

따라서, 실무 단계에서는 @ManyToMany는 절대 사용하지 말아야 한다.

다대다 관계를 사용하고 싶은 경우라면 중간 테이블에 대한 클래스를 직접 만들어서 @ManyToOne과 @OneToMany의 조합을 만들어 사용해야 한다.

중간 테이블을 직접 만들어서 관계를 매핑하면 아래와 같은 형태가 된다.

@Entity
public class Member {

    @Id @GeneratedValue
    @Column(name = "MEMBER_ID")
    private Long id;

    @Column(name = "USERNAME")
    private String username;

    @OneToMany(mappedBy = "member")
    private List<MemberProduct> memberProducts = new ArrayList<>();
}
.
.
.
@Entity
public class Product {

    @Id @GeneratedValue
    private Long id;

    private String name;

    @OneToMany(mappedBy = "product")
    private List<MemberProduct> memberProducts = new ArrayList<>();
}
.
.
.
@Entity
public class MemberProduct {

    @Id @GeneratedValue
    private Long id;

    @ManyToOne
    @JoinColumn(name = "MEMBER_ID")
    private Member member;

    @ManyToOne
    @JoinColumn(name = "PRODUCT_ID")
    private Product product;
}

Member(ONE) - (MANY)MemberProduct(MANY) - (ONE)Product

MemberProduct는 Order 정도의 역할이 되겠다.

중간 테이블을 하나의 엔티티 개념으로 사용하면 (MemberProduct -> Order) 이러한 형태를 가질 수 있게 된다.

(ORDER_ID는 Generated Value로 주어진 비즈니스적 의미를 갖지 않는 값)