[JAVA] 백준 sorting - 실버모음

 

1181 단어 정렬(실버5)

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

1181번: 단어 정렬

 

• 저번에 풀었던 문제다! (2달전 쯤)
• 중복된 단어는 하나만 남기고 제거해야한다는 것에서 set냄새가 난다
• 정렬을 해야하는 set이라면 treeset을 사용하는 게 좋을 것 같다

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringBuffer sb = new StringBuffer();
TreeSet<String> treeSet = new TreeSet<>(new Comparator<String>() {
  @Override
  public int compare(String o1, String o2) {
    if (o1.length() == o2.length())
      return o1.compareTo(o2);
    else
      return o1.length() - o2.length();
  }
});

for (int n=0; n<N; n++) {
  String str = br.readLine();
  treeSet.add(str);
}

for (String s: treeSet) {
  sb.append(s); sb.append("\n");
}
System.out.print(sb);

• 문자의 길이가 같다면 compareTo로 사전순 정렬한다
• 문자의 길이가 다르다면 짧은 게 먼저 나오도록 한다(length의 오름차순)

 

 

1251 단어 나누기(실버5)

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

1251번: 단어 나누기

 

• subString으로 삼등분 땅땅해서 String의 compareTo 메서드를 쓰면 될 것 같다

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
String one = "";
String two = "";
String three = "";

String result = "";

for (int i =0; i<= s.length()-3; i++) {
  for (int j=i+1; j<= s.length()-2; j++) {
    one = s.substring(0, i+1);
    two = s.substring(i+1, j+1);
    three = s.substring(j+1);

    StringBuffer sb = new StringBuffer();
    for (int k = one.length()-1; k >= 0; k--)
      sb.append(one.charAt(k));

    for (int k = two.length()-1; k >= 0; k--)
      sb.append(two.charAt(k));

    for (int k = three.length()-1; k >= 0; k--)
      sb.append(three.charAt(k));

    //result.compareTo(sb.toString()); //result가 사전순으로 앞서면 -

    if (result.equals("") || result.compareTo(sb.toString()) > 0)
      result = sb.toString();
  }
}

System.out.print(result);

 

 

1427 소트인사이드(실버5)

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

1427번: 소트인사이드

 

• 그냥 진짜 내림차순 정렬하는 문제
• 값이 최대 10억이니까 int값에 충분히 저장될 수 있다

 

public class Main {
  public static void main(String args[]) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String str = br.readLine();
    List<Integer> list = new ArrayList<>();

    for (int i =0; i<str.length(); i++)
      list.add(Character.getNumericValue(str.charAt(i)));

    Collections.sort(list, Comparator.reverseOrder());
    StringBuffer sb = new StringBuffer();
    for (Integer i : list)
      sb.append(i);

    System.out.print(sb);
  }
}

• 리스트 다 저장하고 내림차순 정렬!

 

 

25631 마트료시카 합치기(실버5)

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

25631번: 마트료시카 합치기

 

• 처음에는 오름차순으로 정렬해서 옆에 넣을 수 있는 공간만 보면 될 줄 알았고, 구현도 그렇게 했다
• 하지만 옆옆에 내가 들어갈 공간이 있을수도 있고, 옆옆옆옆에 있을 수도 있음 (ex. 1 1 3 3 3 5 => 3개)
• 그래서 다음과 같은 풀이를 선택했다

 

1. 일단 마트료시카 오름차순 정렬
2. isMerged가 false인 맨 오른쪽 마트료시카를 든다
3. isMerged가 false인 나머지 왼쪽 마트료시카들을 쭉 훑는다
   1. 만약 들어갈 곳이 있으면 해당하는 인덱스의 isMerged를 true로 만든다 
   2. 모두 훑었으면 result를 하나 증가시킨다 (합체된 마트료시카 하나 완성)
4. 2~3 과정을 모두 isMerged가 true가 될 때까지 반복

 

풀이

public class Main {
  public static void main(String args[]) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    int[] arr = new int[N];

    for (int i =0; i<N; i++)
      arr[i] = Integer.parseInt(st.nextToken());

    Arrays.sort(arr);

    int result = 0;
    boolean[] isMerged = new boolean[N];

    while (true) {
      int rev = -1;
      for (int i=0; i<arr.length; i++) {
        if (!isMerged[i] && rev < arr[i]) {
          isMerged[i] = true;
          rev = arr[i];
        }
      }
      if (rev == -1)
        break;

      result++;
    }

    System.out.print(result);
  }
}

• 일단 오름차순으로 정렬한다
• 이전 마트료시카의 크기를 저장할 rev를 만든다
• 계속 훑으면서 isMerged가 false인 애를 찾아 rev에 저장한다
  • rev보다 값이 큰 경우, isMerged를 true로 설정해주고 rev에 값을 저장한다
• 만약 다 훑었는데 rev가 초기값이라면 모두 isMerged가 true라는 뜻이기 때문에 break해준다
• rev에 값이 있다면 중첩 마트료시카 하나가 만들어진거니까 result를 하나 증가시킨다 

 

 

1015 수열 정렬(실버4)

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

1015번: 수열 정렬

 

• 딱 문제를 처음 봤을 때는 뭐라는지 하나도 모르겠고 너무 어려웠다
• B의 값을 생각하면서 A의 인덱스 계산을 하려고 하니 한 번에 될 것 같지 않아 메모를 했다

 

//A:  2 1 3 1
//B:  1 1 2 3
//P:  2 0 3 1
//B[P[i]] = A[i]

//A[0] = 2 = B[2] // 2 = P[0]
//A[1] = 1 = B[0] // 0 = P[1]
//A[2] = 3 = B[3] // 3 = P[2]

• 천천히 적어보면 답이 보인다
• 풀이법
  1. A의 값을 하나씩 뽑는다 -> A[i]
  2. B를 쭉 돌면서 뽑은 A의 값과 값이 같은 인덱스를 찾는다 
  3. 해당 인덱스 값을 P[i]에 넣는다
• 같은 값이 있는 경우 사전순으로 앞선 애를 출력하라고 했으니, 가장 처음 발견한 B값을 바로 visit = true로 해주고 다음에 나오면 그 다음에 B값을 뽑는 식으로 구현했다

 

풀이

public class Main {
  public static void main(String args[]) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());
    StringTokenizer st = new StringTokenizer(br.readLine());
    int[] A = new int[N];

    for (int i =0; i<N; i++)
      A[i] = Integer.parseInt(st.nextToken());

    int[] B = A.clone();
    Arrays.sort(B);

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

    boolean[] visit = new boolean[N];

    for (int i =0; i<A.length; i++) {
      for (int j =0; j<B.length; j++) {
        if (A[i] == B[j] && !visit[j]) {
          visit[j] = true;
          P.add(String.valueOf(j));
          break;
        }
      }
    }

    System.out.print(String.join(" ", P));
  }
}

• A를 오름차순 정렬함
• visit배열을 만듦
• A에 값을 하나씩 뽑음
  • B를 훑으면서 A뽑은 값과 같은 값이면서 + visit가 false인 거 찾음
  • 같은 걸 찾으면 visit를 true로 만들고 P에 추가함

 

 

 

7795 먹일 것인가 먹힐 것인가(실버3)

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

7795번: 먹을 것인가 먹힐 것인가

 

• A와 B 배열을 오림차순 정렬해서 A가 먹을 수 있는 B 요소의 인덱스를 저장하면서 result에 더해주면 될 것 같다
• A를 오름차순 정렬했기 때문에 A[i+1]가 먹을 수 있는 먹이는 A[i]가 먹을 수 있는 먹이를 모두 포함한다 (크기가 크니까)
• 이를 canEat라는 index로 저장해 탐색 시간을 조금 줄이려고 했다

 

풀이

class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int tcCnt = Integer.parseInt(br.readLine());
    for (int tc = 0; tc < tcCnt; tc++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int ACnt = Integer.parseInt(st.nextToken());
      int BCnt = Integer.parseInt(st.nextToken());

      int[] A = new int[ACnt];
      int[] B = new int[BCnt];

      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < ACnt; j++)
        A[j] = Integer.parseInt(st.nextToken());

      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < BCnt; j++)
        B[j] = Integer.parseInt(st.nextToken());

      Arrays.sort(A);
      Arrays.sort(B);

      int result = 0;
      int canEat = 0;
      for (int i = 0; i < ACnt; i++) {
        for (int j = canEat; j < BCnt; j++) {
          if (A[i] <= B[j])
            break;

          canEat++;
        }

        result += canEat;
      }

      System.out.println(result);
    }
  }
}

• A배열과 B배열에 저장한다
• A와 B를 오름차순 정렬한다
• A에서 값을 하나씩 뺀다 -> A[i]
  • canEat 인덱스부터 B값을 훑어본다
  • 만약 B[j] 가 A[i] 보다 크거나 같으면 그 뒤론 모두 못먹는 애들이다 -> break
  • A[i]가 먹을 수 있는 먹이 수는 canEat 만큼이다. result에 더해준다

 

 

+) 이 문제는 이진탐색으로 풀 수도 있다고 한다. 궁금하신 분은 구글링 ㄱㄱ 

 

 

 

 

 

 

 

다음 공부할 내용: 문자열, 이진탐색

(공부할수록 공부해야할 게 늘어난다. 신기하다 ㅎㅎ)