[JAVA] 백준 문자열 부수기 1

 

 

 

문자열 쪽이 많이 부족한 것 같아 부수기를 해보려고 한다.

브론즈부터 골드까지 각 5문제 이상씩 풀면서 익숙해져봐야겠다.

 

<<<브론즈 부수기>>

 

2743 단어 길이 재기 - 브론즈5

https://www.acmicpc.net/problem/2743

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();

System.out.println(input.length());

 

화가 날 정도로 쉬운 문제다.

 

 

2744 대소문자 바꾸기 - 브론즈5

https://www.acmicpc.net/problem/2744

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();

char[] arr = new char[input.length()];
for (int i=0; i<input.length(); i++) {
    int charString = input.charAt(i);
    if (charString >= 97) {
        arr[i] = (char)(charString - 32);
    } else {
        arr[i] = (char)(charString + 32);
    }
}

System.out.println(String.valueOf(arr));

 

소문자와 대문자 사이에 일정한 간격이 있다는 것을 이용한 풀이다.

하지만 toUpperCase라는 좋은 메서드가 있기때문에 이걸로 푸는 게 가독성이 더 좋을 것 같다.

toUpperCase를 이용한 풀이는 아래와 같다.

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();

StringBuilder sb = new StringBuilder();
for (int i=0; i<input.length(); i++) {
    char charString = input.charAt(i);

    if (charString >='a') {
        sb.append(Character.toUpperCase(charString));
    } else {
        sb.append(Character.toLowerCase(charString));
    }
}

System.out.println(sb);

 

 

 

9086 문자열 - 브론즈5

https://www.acmicpc.net/problem/9086

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tcCnt = Integer.parseInt(br.readLine());

StringBuilder sb = new StringBuilder();
for (int t=0; t<tcCnt; t++) {
    String input = br.readLine();

    sb.append(input.charAt(0)).append(input.charAt(input.length()-1)).append("\n");
}

System.out.print(sb);

 

지루해서 바로 실버로 넘어가야겠다

 

 

 

<<<실버 부수기>>

 

1181 단어 정렬 - 실버5

https://www.acmicpc.net/problem/1181

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int size = Integer.parseInt(br.readLine());
TreeSet<String> treeSet = new TreeSet<>((o1, o2) -> {
    if (o1.length() == o2.length()) {
        for (int i =0; i<o1.length(); i++) {
            char char1 = o1.charAt(i);
            char char2 = o2.charAt(i);
            if (char1 == char2) {
                continue;
            }

            return Character.compare(char1, char2);
        }

        return 0;
    }

    return Integer.compare(o1.length(), o2.length());
});

for (int i =0; i<size; i++) {
    treeSet.add(br.readLine());
}

StringBuilder sb = new StringBuilder();
while (!treeSet.isEmpty()) {
    sb.append(treeSet.pollFirst()).append("\n");
}

System.out.print(sb);

 

사전순으로 정렬하는 메서드가 있을 것 같은데 기억이 나지 않아서.. 소문자들이 순서대로 숫자에 저장된다는 아이디어를 이용하여 정렬하는 식으로 풀었다.

 

사전순으로 정렬하는 방법은 굉장히 간단했다. String 2개를 사전순으로 비교하는 방법은 다음과 같다.

o1.compareTo(o2)

 

몰랐지만 풀었으니 기분은 좋다..

 

 

 

 

1251 단어 나누기 - 실버5

https://www.acmicpc.net/problem/1251

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
String minString = "z".repeat(input.length());

for (int i = 1; i < input.length() - 1; i++) {
    for (int j = i+1; j < input.length(); j++) {
        StringBuilder sb = new StringBuilder();

        for (int a = i-1; a >=0; a--) {
            sb.append(input.charAt(a));
        }

        for (int b = j-1; b >= i; b--) {
            sb.append(input.charAt(b));
        }

        for (int c = input.length()-1; c >= j; c--) {
            sb.append(input.charAt(c));
        }

        String makedString = sb.toString();
        if (makedString.compareTo(minString) < 0) {
            minString = makedString;
        }
    }
}

System.out.println(minString);

 

인덱스를 계산해서 하나씩 바꾸면서 StringBuilder에 넣어줬다. 상당히 재밌는 문제여서 좋았다

 

 

1316 그룹 단어 체커 - 실버5

https://www.acmicpc.net/problem/1316

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cnt = Integer.parseInt(br.readLine());

int result = 0;
for (int i =0; i<cnt; i++) {
    String input = br.readLine();
    boolean[] visit = new boolean[26];

    char prev = ' ';
    boolean isGroupWord = true;
    for (int j = 0; j<input.length(); j++) {
        if (input.charAt(j) != prev) {
            int ch = input.charAt(j) - 'a';
            if (!visit[ch]) {
                visit[ch] = true;
                prev = input.charAt(j);
            } else {
                isGroupWord = false;
                break;
            }
        }
    }

    if (isGroupWord) {
        result ++;
    }
}

System.out.println(result);

 

재미있는 문제였다!

 

 

1427 소트인사이드 - 실버5

https://www.acmicpc.net/problem/1427

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String numberString = br.readLine();
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

for (int i=0; i<numberString.length(); i++) {
    pq.add(Character.getNumericValue(numberString.charAt(i)));
}

StringBuilder sb = new StringBuilder();
while (!pq.isEmpty()) {
    sb.append(pq.poll());
}

System.out.println(sb);

 

PriorityQueue를 잘 쓰면 된다. 너무 재미가 없어서 실버3으로 가야겠다.

 

 

 

 

1213 팰린드롬 만들기 - 실버3

 

https://www.acmicpc.net/problem/1213

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();

TreeMap<Character, Integer> map = new TreeMap<>();
for (int i =0; i<input.length(); i++) {
    map.put(input.charAt(i), map.getOrDefault(input.charAt(i), 0) + 1);
}

boolean isEven = (input.length() % 2 == 0);
char[] result = new char[input.length()];
int idx= 0;
int reverseIdx = result.length-1;
int oddCnt = 0;
boolean cantMakePalindrome = false;

for (Character key: map.keySet()) {
    Integer value = map.get(key);

    if (value % 2 != 0) {
        if ((isEven) || (!isEven && (oddCnt > 0))) {
            cantMakePalindrome = true;
            break;
        } else {
            //짝수 길이가 아니면서 oddCnt가 0임
            oddCnt ++;
            result[result.length/2] = key;
        }
    }

    int tmp = value / 2;
    for (int i = 0; i< tmp; i++) {
        result[idx++] = key;
        result[reverseIdx--] = key;
    }
}

if (cantMakePalindrome) {
    System.out.println("I'm Sorry Hansoo");
    return;
}

StringBuilder sb = new StringBuilder();
for (int i =0; i<result.length; i++) {
    sb.append(result[i]);
}

System.out.println(sb);

 

대충 만들면서 넣으주면 된다.

사전순 정렬이기 때문에 PriorityQueue를 넣어줬다

 

 

1515 수 이어 쓰기 - 실버3

https://www.acmicpc.net/problem/1515

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();

int minNumber = 0;
int idx = 0;
while (idx < input.length()) {
    minNumber++;
    String currentNum = String.valueOf(minNumber);

    for (char c: currentNum.toCharArray()) {
        if (input.charAt(idx) == c) {
            idx++;

            if (idx >= input.length()) {
                break;
            }
        }
    }
}

System.out.println(minNumber);

 

숫자를 하나씩 꺼내 앞숫자부터 비교하면서 주어진 숫자들을 삭제해나가는 느낌이다.

꽤 재밌는 문제였다!

 

 

 

2852 NBA 농구 - 실버3

 

https://www.acmicpc.net/problem/2852

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cnt = Integer.parseInt(br.readLine());

int[] score = new int[2];
int[] winTime = new int[2];

int currentWinTeam = -1;
int prevTime = 0;

for (int i =0; i<cnt; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int teamNumber = Integer.parseInt(st.nextToken())-1;
    String[] times = st.nextToken().split(":");

    score[teamNumber] ++;

    //이기는중
    int rivalTeam = score[(teamNumber + 1) % 2];
    if (score[teamNumber] > rivalTeam) {
        //무승부에서 바뀐거면
        if (currentWinTeam == -1) {
            currentWinTeam = teamNumber;
            prevTime = Integer.parseInt(times[0]) * 60 + Integer.parseInt(times[1]);
        }
    } else if (score[teamNumber] < rivalTeam) {
        //무승부에서 바뀐거면
        if (currentWinTeam == -1) {
            currentWinTeam = teamNumber;
            prevTime = Integer.parseInt(times[0]) * 60 + Integer.parseInt(times[1]);
        }
    } else {
        //이기고 있는 시간 갱신
        int currentMinute = Integer.parseInt(times[0]) * 60 + Integer.parseInt(times[1]);
        winTime[currentWinTeam] += (currentMinute - prevTime);

        //무승부 처리
        currentWinTeam = -1;
    }
}

if (currentWinTeam != -1) {
    int currentMinute = 48 * 60;
    winTime[currentWinTeam] += (currentMinute - prevTime);
}

StringBuilder sb = new StringBuilder();
sb.append(String.format("%02d", winTime[0] / 60)).append(":").append(String.format("%02d", winTime[0] % 60));
sb.append("\n");
sb.append(String.format("%02d", winTime[1] / 60)).append(":").append(String.format("%02d", winTime[1] % 60));

System.out.println(sb);

 

분 단위로 이기고 있는 시간만 잘 계산해주면 어렵지 않다.

실버 1로 넘어가도 될 것 같다.

 

 

 

1141 접두사 - 실버1

https://www.acmicpc.net/problem/1141

 

class Node {
    char ch;
    Map<Character, Node> map;

    public Node(char ch, Map<Character, Node> map) {
        this.ch = ch;
        this.map = map;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());
        Node root = new Node(' ', new HashMap<>());

        for (int i =0; i<cnt; i++) {
            String input = br.readLine();
            addString(root, input, 0);
        }

        int result = dfs(root);
        System.out.println(result);
    }

    private static int dfs(Node node) {
        if (node.map.isEmpty()) {
            return 1;
        }

        int sum = 0;
        for (char key: node.map.keySet()) {
            sum += dfs(node.map.get(key));
        }

        return sum;
    }

    private static void addString(Node node, String word, int idx) {
        if (idx >= word.length()) {
            return;
        }

        Node current = node.map.getOrDefault(word.charAt(idx), null);
        if (current == null) {
            current = new Node(word.charAt(idx), new HashMap<>());
            node.map.put(word.charAt(idx), current);
        }

        addString(current, word, idx+1);
    }
}

 

트리로 구성해서 리프노드의 개수를 세줬다.

트라이로 풀거나 다른 좋은 방법이 있을 것 같다는 생각이 든다. 계속 풀면서 찾아봐야겠다.