5
0 4
1 2
1 -1
2 2
3 3

1 -1
1 2
2 2
3 3
0 4

간단한 문제이다. 

Arrays.sort()와 Comparator를 이용하면 금방 풀 수 있다.

이차원 배열 arr[N][2]이 있다. (N은 주어진 좌표 개수, 2는 x,y 좌표를 의미)

배열 arr을 Arrays.sort()를 이용하여 정렬할 때, 우리만의 정렬 기준(Comparator)을 선언해 준다.

우선 arr[N][2]를 열어보면 

아래와 같이 배열 안에 작은 배열이 있는 식으로 볼 수 있다.

arr = { {1, 2} ,

          {2, -1},

          {-1, 2},

          .... }

Comparator에 우리가 선언할 compare은 arr 안의 작은 배열의 값을 비교하여 정렬하는 것이다.

        // 핵심
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b){
                if(a[1] == b[1]){ // arr[i][1] == arr[i+1][1] 두 점의 Y 좌표를 비교
                    return a[0]-b[0];  //같으면 X의 값을 비교하여 정렬
                } else { 
                    return a[1]-b[1];  //다르면 Y의 값을 비교하여 정렬
                }
            }
        });

전체 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.Arrays;

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

        int[][]arr = new int[n][2];
		
        // 좌표를 배열에 담기
        for(int i=0;i<n;i++){
            String[] a = br.readLine().split(" ");
            arr[i][0] = Integer.parseInt(a[0]);
            arr[i][1] = Integer.parseInt(a[1]);
        }
		
        // 핵심
        Arrays.sort(arr, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b){
                if(a[1] == b[1]){
                    return a[0]-b[0];
                } else {
                    return a[1]-b[1];
                }
            }
        });

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

문제 : 

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:

Input: digits = ""
Output: []
Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints (제한조건) :
0 <= digits.length <= 4
digits [i] is a digit in the range ['2', '9'].

2-9까지 숫자의 조합이 주어졌을 때, 해당 숫자가 나타낼 수 있는 알파벳의 모든 조합을 구하는 문제이다.

처음부터 자료구조를 HashMap을 사용하기로 생각을 했으나, 어떻게 해야 주어진 문자열 digits.lentgh에 맞춰 반복문을 쓸까 고민을 했다.

그러다가 문득 모든 가능한 경우의 수를 탐색하면서 조건을 만족하는 해를 찾는  백트랙킹(backtracking) 알고리즘이 생각이 났다.

구현 방법이 내가 기억하는 게 맞다면 이런 식으로 구현이 되는데

for(선택지)
 상태 변경
 재귀호출(변경된 상태)
 상태 복귀

긴가민가하여 조금 헤맸다.

우선 내 풀이는 이렇다.

주어진 메인메서드의 리턴값이 List <String>이니 

결과를 리턴해줄 리스트 result를 선언해 준다.

그리고 digitis이 공백일 경우 result를 바로 리턴해 준다.

List<String> result = new ArrayList<>();

if(digits == null || digits.length()==0){
    return result;
}

이후 각 숫자들이 나타낼 수 있는 알파벳 조합을 저장하기 위해 Map <Character, String>을 생성해 주었다.

Map의 Key타입을 Character로 지정해 준 이유는 digits문자열을 문자 배열(char)로 전환하여 비교할 예정이기 때문이다. 

        Map<Character, String> map = new HashMap<>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");

마지막으로 백트랙킹을 만들어 주겠다.

매개변수로는

1. 문자열 digits,

2. 몇 번째 조합인지 체크하는 인덱스 index,

3. 조합을 저장할 StringBuilder,

4. 최종 조합을 저장할 리스트 result,

5. 그리고 각 숫자의 알파벳을 가지고 있는 map이다.

주어진 문자열 digits이 "23"일 경우 나올 수 있는 알파벳 조합의  digits의 길이와 동일한 2이다.

예)

'2' = "abc"

'3' = "def"

2와 3의 모든 조합 :ad, ae, af, bd, be, bf, cd, ce, cf

백트래킹을 재귀적으로 호출하여 탐색할 때, 최대 탐색할 수 있는 깊이를 지정하지 않으면 StackOverFlow가 발생한다.

몇 번째 조합인지 체크(깊이 체크)하는 index가 digits의 길이와 같을 경우 return 하도록 해줬다.

그리고 return 할 때, Stringbuilder는 모든 조합을 탐색한 상태이기 때문에 result에 더 해주도록 한다.

digits가 "23"일 때 아래의 코드는 다음과 같이 작동한다.

    public void backTrack(String digits, int index, StringBuilder comb, 
                          List<String> result, Map<Character, String> map){

        if(index == digits.length()){ // 인덱스의 값이 digits의 길이와 같으면
            result.add(comb.toString()); // 끝까지 탐색한 것이므로 result에 더해주고
            return; // return한다.
        }

        String letters = map.get(digits.charAt(index)); // map에 저장된 각 숫자의 알파벳을 저장
		
        // letters에 있는 문자를 하나씩 꺼내온다.
        for(char letter : letters.toCharArray()){
            comb.append(letter); // 꺼내온 문자를 StringBuilder comb에 저장하고
            backTrack(digits, index+1, comb, result, map); // 재귀적으로 조합 탐색
            comb.deleteCharAt(comb.length()-1); // 재귀호출이 끝나면 stringBuilder를 비워준다.
        }
    }

1. backTrack  첫 호출

String letters = map.get(digits.charAt(index));

-> letters = map.get(digits.charAt(0));  

map에서 '2'의 값 "abc"를  가져와  letters에 저장한다.

for(char letter : letters.toCharArray()) { // 문자열 letters를 문자배열 {'a', 'b', 'c'}로 전환하여 하나씩 꺼내온다.

comb.append(letter); // 우선 a를 StringBuilder comb에 입력하고

backTrack(digits, index+1, comb, result, map);  // 재귀 호출 

-> backTrack("23", 0+1, comb, result, map);  // backTrack에 a 다음에 올 문자 조합을 찾는다.

2. backTrack 두 번째 호출

if(index == digits.length()) // index의 크기가 digits의 길이와 동일하지 않으니 넘어간다.

String letters = map.get(digits.charAt(index));

-> letters = map.get(digits.charAt(1));  

map에서 '3'의 값 "def"를  가져와  letters에 저장한다.

for(char letter : letters.toCharArray()) { // 문자열 letters를 문자배열 {'d', 'e', 'f'}로 전환하여 하나씩 꺼내온다.

comb.append(letter); // comb에 들어있던 a와  d를 더하여 ad를 만든다.

backTrack(digits, index+1, comb, result, map);  // 재귀 호출 

-> backTrack("23", 1+1, comb, result, map);  // backTrack에 ad 다음에 올 문자 조합을 찾는다.

3. backTrack 세 번째 호출

if(index == digits.length()) //  2==2로 index의 크기가 digits의 길이와 동일하니 

result.add(comb.toString()); // 끝까지 탐색한 것이므로 result에 comb에 저장된 문자열 ab를 넣어주고
 return;                                    // return 한다.

4. backTrack 두 번째 호출로 복귀

위와 같이 반복하여 a의 모든 결과를 탐색하여 첫 번째 backTrack으로 돌아오면 

comb에 들어가 있던 a를 comb.deleteCharAt(comb.length()-1)를 통해 최종적으로 제거해 주고 

b와 c의 조합도 탐색하고 종료한다.

전체 코드는 다음과 같다. 

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();

        if(digits == null || digits.length()==0){
            return result;
        }

        Map<Character, String> map = new HashMap<>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");

        backTrack(digits, 0, new StringBuilder(), result, map);

        return result;
    }

    public void backTrack(String digits, int index, StringBuilder comb, List<String> result, Map<Character, String> map){

        if(index == digits.length()){
            result.add(comb.toString());
            return;
        }

        String letters = map.get(digits.charAt(index));

        for(char letter : letters.toCharArray()){
            comb.append(letter);
            backTrack(digits, index+1, comb, result, map);
            comb.deleteCharAt(comb.length()-1);
        }
    }
}

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:

Input: s = "cbbd"
Output: "bb"
 

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

문제 : 

문자열 s 가 주어졌을때, 문자열 안에서 가장 긴 팰린드롬을 substring하여 리턴하는 문제이다.

이 문제를 해결하기 위해 브루트포스를 이용하여 푸는것도 가능하지만 이번에는 동적 프로그래밍(DP)를 이용해 보기로 헀다.

풀이 :

1. 우선 문자열 s의 길이가 0일 경우 팰린드롬이

아니고 1이면 자동적으로 팰린드롬이 완성이 된다. 

예) s = "a"; 

문자열이 한글자일 경우 좌에서 보나 우에서 보나 일치하기에 팰린드롬이다.  

    int n = s.length(); // s의 길이 저장
    if(n<=1){ // 0 혹은 1이면 s 반환
        return s;
    }

2. 가장 긴 팰린드롬을 s에서 추출(substring)해야 하기에 

최대 길이를 저장할 maxLen와 

substring을 위한 인덱스 start, end를 선언했다.

이미 문자열 길이가 1이하인 경우는 제외시켰기에 최대 길이는 1부터 시작하므로 maxLen=1로 초기화 하였다.

     int maxLen = 1; // 최대 길이 저장
     int start =0;   // s.substring(start,  시작 인덱스
     int end = 0;    // end);               끝 인덱스

이제 마지막으로 동적 프로그래밍에 사용할 배열을 선언한다.

boolean[][] dp = new boolean[n][n];

3. 배열을 boolean으로 선언한 이유는 문자열 s에서 발생할 수 있는 모든 경우의 수 중에서 팰린드롬인 경우를 표기하기 위함이다.

배열이 n * n (문자열 길이 * 문자열 길이)인 이유는 다음과 같다.

만약 주어진 문자열이 "babad"일 때 2차원 배열 dp에서 표기할 수 있는 문자열 s의 조합이다.

  j →   0   1   2   3   4
     ---------------------
i=0 |   b   a   b   a   d
i=1 |       a   b   a   d
i=2 |           b   a   d
i=3 |               a   d
i=4 |                   d

4. 이제 문자열 s의 모든 조합을 확인하기 위하여 for문을 사용해 문자열을 탐색하겠다.

     for(int i=0; i<n;i++){ // 첫번째 for 문
     	dp[i][i] = true; // 인덱스의 위치가 같은 곳을 true로
        for(int j=0;j<i;j++){ // 두번재 for 문
        }
     }

i==j 일때 팰린드롬이 형성됨으로 dp 배열에서 dp[i][i] 을 true로 만들어준다.

예) 

i =0, j =0    // 비교하는 두 인덱스의 요소의 위치가 같을 때

s[0] == s[0]   // badad의 0번 인덱스는 b==b 이다.

dp[0][0]       // 고로 i==j 는 i==i와 같고 dp[i][i]는 팰린드롬이므로 전부 true

  j →   0   1   2   3   4
     ---------------------
i=0 |   b  
i=1 |       a  
i=2 |           b   
i=3 |               a   
i=4 |                   d


  j →   0   1   2   3   4
     ---------------------
i=0 |   T  
i=1 |       T  
i=2 |           T   
i=3 |               T   
i=4 |                   T

밑준비는 끝났으니 이제 팰린드롬인지 판단하는 조건을 쓰겠다.

조건은 다음과 같다 :

 if(s.charAt(i)==s.charAt(j) && (i-j<=2 || dp[j+1][i-1])){

• s[j] == s[i]: 양 끝 문자가 같고
• i - j <= 2: 길이가 3이하인 경우는 바로 확인 가능  (i = 2; j= 0 일때 배열에선 0,1,2 니까 길이가 3이다. 예 bab)
• 그 외는 내부 문자열 dp[j+1][i-1]이 팰린드롬인지 확인

1. s.charAt(j) == s.charAt(i)

→ 먼저 양 끝 문자가 같아야 팰린드롬일 가능성이 생긴다.
예: "a**bab**a"에서 양쪽 a가 같아야 팰린드롬일 가능성이 있다..

2. dp[j + 1][i - 1] == true

→ 가운데 문자열 s[j+1..i-1]이 이미 팰린드롬이어야 전체도 팰린드롬이다.

예를 들어:

 j가 0, i= 4

• 전체 문자열: s[0..4] = "ababa"
• 양끝 같음: s[0] == s[4] == 'a'
• 중간 부분: s[1..3] = "bab" → 이게 팰린드롬이어야 "ababa"도 팰린드롬

조금 이해가 안간다면 이렇게 설명할 수 있다. 

i = 1

• j = 0 → s[0]="b", s[1]="a" → 다름 → dp[0][1]=false

i = 2

• j = 0 → s[0]="b", s[2]="b", 길이=3 → 가운데 "a"는 팰린드롬 (dp[1][1]=true) → dp[0][2] = true
• j = 1 → s[1]="a", s[2]="b" → 다름 → dp[1][2] = false

➡ "bab" 팰린드롬 발견!

i = 3

• j = 0 → s[0]="b", s[3]="a" → 다름
• j = 1 → s[1]="a", s[3]="a", 길이=3 → 가운데 "b"는 팰린드롬 (dp[2][2]=true) → dp[1][3]=true
• j = 2 → s[2]="b", s[3]="a" → 다름

➡ "aba" 팰린드롬 발견 (같은 길이)

i = 4

• j = 0~3 → 모두 양 끝 문자 다름 → dp[j][4] = false 전부

팰린드롬일 가능성이 있는 인덱스들을 찾았다면 이어서 그것을 dp에 체크한다.

그리고 두 인덱스 사이의 길이가 maxLen보다 클 경우 maxLen를 갱신하고

start와 end 좌표도 갱신한다.

dp[j][i] = true;
if(i-j+1>maxLen){
    maxLen = i-j+1;
    start = j;
    end = i;
}

완성된 for문은 다음과 같다.

     for(int i=0; i<n;i++){
        dp[i][i] = true;
        for(int j=0;j<i;j++){
            if(s.charAt(i)==s.charAt(j) && (i-j<=2 || dp[j+1][i-1])){
                dp[j][i] = true;
                if(i-j+1>maxLen){
                    maxLen = i-j+1;
                    start = j;
                    end = i;
                }
            }
        }
     }

모든 순회를 끝나면 DP는 이렇게 생긴다.

  j →   0   1   2   3   4
     ---------------------
i=0 |   T   F   T   F   F  = bab
i=1 |       T   F   T   F  = aba
i=2 |           T   F   F
i=3 |               T   F
i=4 |                   F



  j →   0   1   2   3   4
     ---------------------
i=0 |   b   a   b   a   d 
i=1 |       a   b   a   d
i=2 |           b   a   d
i=3 |               a   d
i=4 |                   d

이제 마지막으로 구한 두  인덱스를 사용하여 문자열 s 안의 가장 긴 팰린드롬을 리턴하면 끝이다.

class Solution {
    public String longestPalindrome(String s) {
     int n = s.length();
    if(n<=1){
        return s;
    }
     int maxLen = 1;
     int start =0;
     int end = 0;

     boolean[][] dp = new boolean[n][n];

     for(int i=0; i<n;i++){
        dp[i][i] = true;
        for(int j=0;j<i;j++){
            if(s.charAt(i)==s.charAt(j) && (i-j<=2 || dp[j+1][i-1])){
                dp[j][i] = true;
                if(i-j+1>maxLen){
                    maxLen = i-j+1;
                    start = j;
                    end = i;
                }
            }
        }
     } 

     return s.substring(start,end+1); 
    }
}

5
5
4
3
2
1

1
2
3
4
5

딱히 어려울 건 없는 문제이다. 

처음에는 TreeMap 연습할 겸 대충 풀려다가 안되어서 다른 방법을 선택하게 되었다.

TreeMap이 아무리 최악이더라도 삽입/출력 시 O(log n)의 시간 복잡도를 가져 최종 결과를 출력할 때만 빠르게 한다면 되지 않을까 싶었는데.

BufferedWriter를 썼을 경우 NullPointerException이 나와  안되고 StringBuilder를 쓰면 틀렸다고만 나왔다.

아무튼 그래서 방향을 틀어서 Collections의 sort를 이용하기로 했다. 

 - Collections.sort는 O(n) ~ O(nlogn) 시간 복잡도를 가지고 있다.

 - Arrays.sort는 최악의 경우 O(n^2) 까지 시간 복잡도가 올라가기 때문에 사용하지 않았다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;


public class BOJ2751_SortNumbers2 {
    public static void main(String[] args) throws Exception{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        // 리스트 선언
        List<Integer> list = new ArrayList<>();
		// 리스트에 정수 입력
        for(int i=1;i<=n;i++){
            list.add(Integer.parseInt(br.readLine()));
        }
		// 정렬
        Collections.sort(list);
        
        // StringBuilder로 출력
        StringBuilder sb = new StringBuilder();
        for(int val : list){
            sb.append(val).append("\n");
        }
        System.out.print(sb);

    }
}

문제 :

문자열 s가 '(', ')', '{', '}', '[', ']' 문자만 포함하고 있을 때, 이 문자열이 유효한지 판단하세요.

문자열이 유효하려면 다음 조건을 모두 만족해야 합니다:

• 열린 괄호는 동일한 종류의 닫는 괄호로 닫혀야 합니다.
• 열린 괄호는 올바른 순서로 닫혀야 합니다.
• 모든 닫는 괄호는 대응되는 동일한 종류의 열린 괄호를 가져야 합니다.

예시:

예시 1:

입력: s = "()"
출력: true

예시 2:

입력: s = "()[]{}"
출력: true

예시 3:

입력: s = "(]"
출력: false

예시 4:

입력: s = "([])"
출력: true

제약 사항:

• 1 ≤ s.length ≤ 10⁴
• s는 오직 괄호 문자 '()[]{}' 로만 구성됩니다.

구현 :

이 문제의 힌트를 보았을 때,

1. 문자 스택을 쓰고

2. (, {, [ 등 열린 괄호를 만나면 스택에 넣고

3. ), }, ] 닫힌 괄호를 만나면 스택에서 매칭되는 열린괄호가 있으면 pop하라고 했다.

class Solution {
    public boolean isValid(String s) {
		// 스택 준비
        Stack<Character> stack = new Stack<>();
        // 매칭되는 괄호를 찾기 위해 HashMap 준비
        Map<Character, Character> mapping = new HashMap<>();
        mapping.put(')', '(');
        mapping.put('}', '{');
        mapping.put(']', '[');
		
        // String s를 문자 배열로 전환하여 하나씩 
        for (char c : s.toCharArray()) {
        	// 열린 괄호가 들어오면 stack에 푸시
            if (mapping.containsValue(c)) {
                stack.push(c);
            // 닫힌 괄호가 들어오면 실행
            } else if (mapping.containsKey(c)) {
            	// 스택이 비어 있거나 가장 마지막에 들어온 값을 pop해서 비교
                if (stack.isEmpty() || mapping.get(c) != stack.pop()) {
                	// 매칭되는 괄호가 아니면 false 리턴
                    return false;
                }
            }
        }

        return stack.isEmpty();  

    }
}

문제 :

N(1<= N <= 100,000,000,000)가 주어졌을때,

1,2,3,4,...N까지 binary값을 구해서

그 binary값이 팰린드롬인 수의 핪을 구하라.

테스트케이스 :

입력 : 1

출력 : 1

1은

바이너리 값이 1이므로 팰린드롬

입력 : 3

출력 : 4

3은

1 의 바이너리 값이 1 이므로 팰린드롬 O

2 의 바이너리 값은 10 이므로 팰린드롬 X
3 의 바이너리 값은 11 이므로 팰린드롬 O

1과 3의 합은 4

입력 : 5

출력 : 25

1 = 1                                        O

2 = 10                                      X                             

3 = 11                                      O

4 = 100                                     X

5 = 101                                     O

6 = 110                                       X

7 = 111                                       O

8 = 1000                                     X

9 = 1001                                     O

풀이 :

import java.util.Random;

public class LongBinary {
    public static void main(String[] args) {
        long start = System.nanoTime();
        Random random = new Random();
        // 1~100,000,000,000
        long n = random.longs(1,100000000000).findFirst().getAsLong();
        System.out.println(n);
        long sum = 0;
        
        for(long i=1; i<=n; i++){
        // 1부터 N까지 순차적으로 
            System.out.println("1. check this number : " +i);
            if(checkPalindrome(i)){
            //팰린드롬이면 더하기
                sum += i;
            } else {
                continue;
            }
        }
        long end = System.nanoTime();
        System.out.println("실행시간 : " + (end-start)/1000000 + "ms");
        System.out.println(sum);
    }

    private static boolean checkPalindrome(long i) {
    // 전달 받은 i의 값을 binary 문자열로 변환
        String binary = Long.toBinaryString(i);
        System.out.println("2. this is binary : "+binary);
        
        int left =0, right = binary.length()-1;
        // 좌측과 우측의 값을 비교해서 다르면 false
        // 같으면 true;
        while(left<right){
            if(binary.charAt(left) != binary.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        System.out.println("("+i+") is palindrome!!!");
        return true;
    }
}