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;
}

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

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 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 boolean isMinimality(int set, List<Integer> list) {
    boolean isMinimality = true;

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

    return isMinimality;
}

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));

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;
}

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;
    }
}

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"}));

@Test
void getPassAndFailWordList_성공()  throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
    //given
    String[] answerIds = new String[] {"6_1", "4_1", "5_1", "9_3"};
    WordService w = new WordServiceImpl(repository, userService);

    Method method = w.getClass().getDeclaredMethod("getPassAndFailWordList", String[].class);
    method.setAccessible(true);

    List<Integer> passWordList = Arrays.asList(6,4,5);
    List<Integer> failWordList = Arrays.asList(9);

    Object[] obj = new Object[] {answerIds};

    //when
    Map<String, List<Integer>> map = (Map<String, List<Integer>>) method.invoke(w, obj);

    //than
    assertThat(map).extracting("pass", String.class)
            .contains(passWordList);
    assertThat(map).extracting("fail", String.class)
            .contains(failWordList);
}

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;
}

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}}));

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;
}

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}}));

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;
}

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

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;
}

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("))))((((((()())()))("));

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;
    }
}

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}));

public int solution(String arrangement) {
    char[] ch = arrangement.toCharArray();

    int answer = 0;
    char pre = 0;
    Stack<Character> stack = new Stack<Character>();
    for (char c : ch) {
        if (c == '(') {
            stack.push(c);
        } else {
            stack.pop();
            if (pre == c) {
                answer += 1;
            } else {
                answer += stack.size();
            }
        }

        pre  = c;
    }

    return answer;
}

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

public int solution(int[] numbers, int target) {
    int answer = dfs(numbers, target, 0, 0);
    return answer;
}

private int dfs(int[] numbers, int target, int depth, int sum) {
    if (depth == numbers.length) {
        return sum == target ? 1 : 0;
    }

    int left = dfs(numbers, target, depth + 1, sum + numbers[depth]);
    int right = dfs(numbers, target, depth + 1, sum - numbers[depth]);

    return left + right;
}

if (depth == numbers.length) {
    return sum == target ? 1 : 0;
}

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