728x90

문제풀이

 

두가지 접근방법

1. DFS 를 이용한 전체 탐색

 - 처음에 시도했던 방법이다.  메모리 초과가 나와서 역시나했나다..

   그 이유는 최대 10^5 개의 숫자를 DFS로 탐색하려면 엄청난 메모리가 사용될거라 생각했다.

   이 방법이 틀린줄 알면서 풀어본 이유는 대부분의 코딩테스트는 정수론 문제는 거의 출제하지 않는것 같기 때문이다.

   

2. 정수론을 이용한 정렬

 - 문제에서 주어지는 30 이란 숫자에서 생각해낸 방법이다.

   다른분들의 풀이를 보면서 참고하였다.

 

1) 우선 3의 배수의 특징은 각 자리수의 합이 3의 배수라는 점이 있다.

 

2) 우리는 30의 배수를 찾아야 하므로 입력받은 숫자를 정렬했을때 처음에 0이 오면 된다.

 

3) 두 가지 조건을 이용하여  30의 배수인지 아닌지 찾았다.

 

 

소스코드1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.io.*;
import java.util.*;
 
public class Main {
    static int n,k;
    static List<Integer> list = new ArrayList<>();
    static int ans = -1;
    static boolean[] selected;
    public static void main(String[] args) throws Exception, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        String num = br.readLine();
        selected = new boolean[num.length()];
        dfs(0, num, "");
        
        System.out.println(ans);
    }
    static void dfs(int depth, String num, String source)
    {
        if(depth == num.length())
        {
            int k = Integer.parseInt(source);
            if(k >= 30 && k%30 == 0)
            {
                ans = Math.max(ans, k);
            }
            return;
        }
        for(int i=0;i<num.length();i++)
        {
            if(selected[i]) continue;
            selected[i] = true;
            dfs(depth+1, num, source + num.charAt(i));
            selected[i] = false;
        }
    }
}
 
 cs

 

소스코드2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws Exception, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        
        String nums = br.readLine();
        int[] num = new int[nums.length()];
        
        int sum = 0;
        for(int i=0;i<num.length;i++)
        {
            num[i] = nums.charAt(i) - '0';
            sum += num[i];
        }
        
        Arrays.sort(num);
        
        if(sum % 3 == 0 && num[0] == 0)
        {
            for(int i=0;i<num.length;i++)
            {
                System.out.print(num[num.length-i-1]);
            }
        }
        else
            System.out.println(-1);
    }
}
 
 cs

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

 

10610번: 30

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한

www.acmicpc.net

 

LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[Greedy] BOJ 1339번, 단어 수학(JAVA)  (0) 2021.11.08
[Tree] BOJ 10610번, 트리의 지름(JAVA)  (0) 2021.11.04
[Sort] BOJ 1181번, 단어 정렬(JAVA)  (2) 2021.10.31
[Topology Sort] BOJ 2252번, 줄 세우기(JAVA)  (0) 2021.10.29
[Kruskal MST] BOJ 1197번, 최소 스패닝 트리(JAVA)  (0) 2021.10.29
728x90

문제풀이

 

이번 문제는 정렬 알고리즘 문제입니다.

입력으로 들어오는 문자열을 주어진 조건에 맞게 정렬하는 방법에 대해 알아보고자 합니다.

코딩테스트에서 정렬만을 단독으로 물어보는 문제는 거의 출제되지 않고 주로 정렬을 사용해서 어떤 다른것을 해라~

이런식으로 주어지기 때문에 단순 정렬이 아닌 길이순, 사전순, 이나 사용자 클래스를 만들어서 정렬 과같은 방법을 모두 알 익혀두어야 합니다. 

 

문제를 풀때 정렬을 직접 구현해서 사용해도 되지만 Collection.sort(), Arrays.sort()를 사용하는것이 시간상 더 효율적이라고 생각합니다.

 

1. sort 함수 호출할때 정렬 방법 선택하기

 

2. 사용자 정의 클래스를 만들어서 toCompare 함수 override 하기 

 

다음의 두 가지를 이용해서 문제를 풀어보겠습니다.

소스코드를 참고해 주세요.

 

소스코드

방법1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.io.*;
import java.util.*;
 
public class Main {
    static int n;
    static Map<String, Integer> map = new HashMap<>();
    public static void main(String[] args) throws Exception, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++)
        {
            map.put(br.readLine(), 1);
        }
        
        String[] arr = new String[map.size()];
        int idx = 0;
        for(String key : map.keySet())
        {
            arr[idx++] = key;
        }
        
        Arrays.sort(arr, new Comparator<String>(){
            public int compare(String a, String b)
            {
                if(a.length() < b.length()) return -1;
                else if(a.length() > b.length()) return 1;
                else {
                    return a.compareTo(b);
                }
            }
        });
        for(int i=0;i<arr.length;i++)
        {
            sb.append(arr[i]).append('\n');
        }
        
        System.out.println(sb);
    }
}
 cs

방법2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.io.*;
import java.util.*;
 
public class Main {
    static int n;
    static Map<String, Integer> map = new HashMap<>();
    public static void main(String[] args) throws Exception, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++)
        {
            map.put(br.readLine(), 1);
        }
        
        String[] arr = new String[map.size()];
        int idx = 0;
        for(String key : map.keySet())
        {
            arr[idx++] = key;
        }
        
        List<MyString> list = new ArrayList<>();
        for(int i=0;i<arr.length;i++)
        {
            list.add(new MyString(arr[i]));
        }
        
        Collections.sort(list);
        for(int i=0;i<list.size();i++)
        {
            sb.append(list.get(i).str).append('\n');
        }
        
        System.out.println(sb);
    }
}
 
class MyString implements Comparable<MyString>{
    String str;
    
    public MyString(String s)
    {
        str = s;
    }
    
    @Override
    public int compareTo(MyString mString)
    {
        if(str.length() < mString.str.length()) return -1;
        else if(str.length() > mString.str.length()) return 1;
        else{
            return str.compareTo(mString.str);
        }
    }
}
 cs

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

 

1181번: 단어 정렬

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

www.acmicpc.net

 

LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[Tree] BOJ 10610번, 트리의 지름(JAVA)  (0) 2021.11.04
[Sort] BOJ 10610번, 30(JAVA)  (0) 2021.11.01
[Topology Sort] BOJ 2252번, 줄 세우기(JAVA)  (0) 2021.10.29
[Kruskal MST] BOJ 1197번, 최소 스패닝 트리(JAVA)  (0) 2021.10.29
[BFS] BOJ 2583번, 영역 구하기(JAVA)  (0) 2021.10.28
728x90

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

  • numbers의 길이는 1 이상 100,000 이하입니다.
  • numbers의 원소는 0 이상 1,000 이하입니다.
  • 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력

numbers return
[6, 10, 2] "6210"
[3, 30, 34, 5, 9] "9534330"

문제 풀이

문자열을 정렬하는 문제이다.

sort() 함수를 이용해 비교함수를 따로 구현하였다.

문자열은 정렬은 기본적으로 아스키코드 값이 작을 수록, 길이가 짧을 수록 이라는 특징을 가지고 있다

이 문제에서는 두개의 string을 앞뒤로 붙였을때 큰 값이 먼저 와야하기 때문에

bool compare(string a, string b)

{

    return a+b > b+a;

}

다음과 같은 방법을 이용하였다.

 

소스 코드

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
bool compare(string a, string b)
{
    return a+b > b+a;
}
string solution(vector<int> numbers)
{
    string ans = "";
    vector<string> nums;
    for(int i=0;i<numbers.size();i++)
    {
        nums.push_back(to_string(numbers[i]));
    }
    sort(nums.begin(), nums.end(), compare);

    if(nums[0] == "0")
        return "0";
    for(int i=0;i<nums.size();i++)
    {
        ans += nums[i];
    }
   
    return ans;
}
LIST
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[Level2 프로그래머스] 조이스틱, c++  (0) 2021.10.01
[Level2 프로그래머스] 소수 찾기, c++  (0) 2021.10.01
[Level2 프로그래머스] 프린터, c++  (0) 2021.10.01
[Level2 프로그래머스] 전화번호 목록, c++  (0) 2021.10.01
[Level2 프로그래머스] 튜플, c++  (0) 2021.10.01

+ Recent posts

티스토리툴바