www.acmicpc.net/problem/2504

 

2504번: 괄호의 값

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.  만일

www.acmicpc.net

작년에 특강들을때 풀었던 문제지만 기억이 가물가물했습니다..

 

먼저 괄호의 값이 결정되는 기준입니다.

1. () 의 값은 2이다.

2. [] 의 값은 3이다.

3. (X) 의 값은 2 * X이다.

4. [X] 의 값은 3 * X이다.

5. 괄호열 X와 괄호열 Y가 결합된 XY의 값은 X+Y이다.

 

입력이 ( ( ) ( ) ) 이런식으로 주어지면 2 * (2 + 2) = 8이라고 할 수 있는데

저는 2 * 2 + 2 * 2 = 8 의 방식으로 해결하였습니다.

 

변수는 답을 출력하는 ans와 중간 값을 나타내는 sum으로 2개를 사용하였습니다.

 

'(' / '['일 때 sum * 2 or sum * 3을 하고 push합니다.

')' / ']'일 때 연산을 수행하기 전에 먼저 괄호가 올바른 괄호열인지 확인해야합니다.

올바른 괄호열이 맞으면 바로 이전값이 여는 괄호일 경우에만 ans에 더해주고,

그 후에 sum / 2 or sum / 3을 하고 pop합니다.

올바른 괄호열이 아니면 0을 출력하고 return합니다.

 

모든 연산이 끝나고 스택이 괄호가 들어있으면 올바른 괄호열이 아니므로 0을 출력하고,

스택이 비어있으면 올바른 괄호열이므로 답을 출력합니다.

 

 

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
58
59
60
61
62
63
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Stack<Character> s = new Stack<>();
    static char ch[];
    static int ans, sum = 1;
 
    static void func() {
        for (int i = 0; i < ch.length; i++) {
            if (ch[i] == '(') {
                sum *= 2;
                s.push(ch[i]);
            } else if (ch[i] == '[') {
                sum *= 3;
                s.push(ch[i]);
            } else if (ch[i] == ')') {
                if (s.isEmpty() || s.peek() != '(') {
                    System.out.println(0);
                    return;
                }
 
                if (s.peek() == '(') {
                    if (ch[i - 1] == '(')
                        ans += sum;
                    sum /= 2;
                    s.pop();
                }
            } else {
                if (s.isEmpty() || s.peek() != '[') {
                    System.out.println(0);
                    return;
                }
 
                if (s.peek() == '[') {
                    if (ch[i - 1] == '[')
                        ans += sum;
                    sum /= 3;
                    s.pop();
                }
            }
        }
 
        if (!s.isEmpty())
            System.out.println(0);
        else
            System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        ch = st.nextToken().toCharArray();
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

 

'algorithm > data-structure' 카테고리의 다른 글

boj 1927 최소 힙  (0) 2021.01.31
boj 4889 안정적인 문자열  (0) 2021.01.26
boj 6198 옥상 정원 꾸미기  (0) 2021.01.26
boj 1874 수택 수열  (0) 2021.01.25
boj 17298 오큰수  (0) 2021.01.25

www.acmicpc.net/problem/6198

 

6198번: 옥상 정원 꾸미기

문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으

www.acmicpc.net

바라보는 방향이 오른쪽이고, 그 방향에 자신보다 크거나 같은 높이의 건물과 그 이후의 건물의 옥상은 볼 수 없습니다.

 

저는 순차탐색으로 스택에 높이와 인덱스를 넣어가며 비교하였습니다.

 

먼저 s.peek의 높이가 현재 높이보다 작거나 같으면 자신 이후의 건물을 볼 수 없으므로 pop을 해줍니다.

이때 pop을 해주면서 현재의 인덱스와 삭제할 건물의 인덱스 사이에 존재하는 번호의 갯수를 ans에 더해줍니다.

 

이 작업이 끝나고 스택에 값이 남아있으면 s.peek()부터 작은 순서대로 pop이 될 것입니다.

s.peek()이 가장 마지막에 있는 건물이기 때문에 고정값(pre)으로 하고 pop하는 건물의 인덱스와 pre의 차이만큼 더해줍니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Stack<int[]> s = new Stack<>();
    static int list[];
    static int N;
    static long ans;
 
    static void func() {
        for (int i = 0; i < N; i++) {
            while (!s.isEmpty() && s.peek()[0] <= list[i]) {
                ans += (i - (s.peek()[1] + 1));
                s.pop();
            }
 
            s.push(new int[] { list[i], i });
        }
 
        int pre = N - 1;
        while (!s.isEmpty()) {
            ans += (pre - s.peek()[1]);
            s.pop();
        }
        
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
cs

'algorithm > data-structure' 카테고리의 다른 글

boj 4889 안정적인 문자열  (0) 2021.01.26
boj 2504 괄호의 값  (0) 2021.01.26
boj 1874 수택 수열  (0) 2021.01.25
boj 17298 오큰수  (0) 2021.01.25
boj 4358 생태학  (0) 2021.01.25

www.acmicpc.net/problem/15652

 

15652번: N과 M (4)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

N과M 4번째 문제입니다.

같은 수를 여러번 골라도 되고, 수열은 비내림차순이어야 합니다.

비내림차순 이라는 말은 같거나 큰 숫자를 골라야합니다.

즉, 중복이 가능하다는 것입니다.

 

작은수를 고르면 안되기때문에 다음 수로 넘어갈 때는 현재 수인 i를 그대로 넘겨주면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int list[];
    static int N, M;
 
    static void dfs(int num, int cnt) {
        if (cnt == M) {
            for (int i = 0; i < M; i++) {
                sb.append(list[i] + " ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = num; i <= N; i++) {
            list[cnt] = i;
            dfs(i, cnt + 1);
            list[cnt] = 0;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[M];
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(1, 0);
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 15655 N과 M (6)  (0) 2021.01.27
boj 15654 N과 M (5)  (0) 2021.01.27
boj 15651 N과 M (3)  (0) 2021.01.26
boj 15650 N 과 M (2)  (0) 2021.01.26
boj 15649 N 과 M (1)  (0) 2021.01.26

www.acmicpc.net/problem/15651

 

15651번: N과 M (3)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

N과M 3번째 문제입니다.

 

이 문제는 같은 수를 중복해서 선택할 수 있기때문에 중복체크를 안하는 것이 맞습니다.

나머지는 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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int list[];
    static int N, M;
 
    static void dfs(int cnt) {
        if (cnt == M) {
            for (int x : list) {
                sb.append(x + " ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = 1; i <= N; i++) {
            list[cnt] = i;
            dfs(cnt + 1);
            list[cnt] = 0;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[M];
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(0);
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 15654 N과 M (5)  (0) 2021.01.27
boj 15652 N 과 M (4)  (0) 2021.01.26
boj 15650 N 과 M (2)  (0) 2021.01.26
boj 15649 N 과 M (1)  (0) 2021.01.26
boj 2580 스도쿠  (0) 2021.01.22

www.acmicpc.net/problem/15650

 

15650번: N과 M (2)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

N과 M 두번째 문제입니다.

 

첫번째 문제와 다른 점은 고른 수열이 오름차순이라는 점입니다.

순서를 보는 문제라고 생각하시면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static boolean visit[];
    static int list[];
    static int N, M;
 
    static void dfs(int num, int cnt) {
        if (cnt == M) {
            for (int x : list) {
                sb.append(x + " ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = num; i <= N; i++) {
            if (visit[i])
                continue;
 
            visit[i] = true;
            list[cnt] = i;
            dfs(i + 1, cnt + 1);
            list[cnt] = 0;
            visit[i] = false;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[M];
        visit = new boolean[N + 1];
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(1, 0);
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 15652 N 과 M (4)  (0) 2021.01.26
boj 15651 N과 M (3)  (0) 2021.01.26
boj 15649 N 과 M (1)  (0) 2021.01.26
boj 2580 스도쿠  (0) 2021.01.22
boj 1759 암호 만들기  (0) 2021.01.22

www.acmicpc.net/problem/15649

 

15649번: N과 M (1)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

기본적인 백트래킹으로 해결할 수 있는 문제입니다.

 

이 문제에서는 수의 순서를 따지기때문에 1,2,3,4와 1,2,4,3을 다른 수열이라고 보시면 됩니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static ArrayList<Integer> list = new ArrayList<>();
    static boolean[] visit = new boolean[9];
    static int N, M;
 
    static void dfs(int cnt) {
        if (cnt == M) {
            for (Integer x : list) {
                sb.append(x + " ");
            }
            sb.append("\n");
            return;
        }
 
        for (int i = 1; i <= N; i++) {
            if (visit[i])
                continue;
 
            visit[i] = true;
            list.add(i);
            dfs(cnt + 1);
            list.remove(list.size() - 1);
            visit[i] = false;
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(0);
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 15651 N과 M (3)  (0) 2021.01.26
boj 15650 N 과 M (2)  (0) 2021.01.26
boj 2580 스도쿠  (0) 2021.01.22
boj 1759 암호 만들기  (0) 2021.01.22
boj 1062 가르침  (0) 2021.01.22

 

www.acmicpc.net/problem/1874

 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net

스택에 1~N을 순서대로 push, pop 과정을 반복하면서 입력에 주어진 순서대로 pop을 할 수 있는지 출력하는 문제입니다.

 

아래의 예시를 이용하여 리뷰하겠습니다.

8
4
3
6
8
7
5
2
1

N = 8, list[] = {4, 3, 6, 8, 7, 5, 2, 1} 입니다.

 

push 1 -> s.peek = 1, list[idx] = 4 (s.peek != list[idx] 이므로 (+))

push 2 -> s.peek = 2, list[idx] = 4 (s.peek != list[idx] 이므로 (+))

push 3 -> s.peek = 3, list[idx] = 4 (s.peek != list[idx] 이므로 (+))

push 4 -> s.peek = 4, list[idx] = 4 (s.peek == list[idx] 이므로 (-)후에 idx++)

              s.peek = 3, list[idx] = 3 (s.peek == list[idx] 이므로 (-)후에 idx++)

              s.peek = 2, list[idx] = 6 (s.peek != list[idx] 이므로 다음 진행)

push 5 -> s.peek = 5, list[idx] = 6 (s.peek != list[idx] 이므로 (+))

push 6 -> s.peek = 6, list[idx] = 6 (s.peek == list[idx] 이므로 (-)후에 idx++)

              s.peek = 5, list[idx] = 8 (s.peek != list[idx] 이므로 다음 진행)

push 7 -> s.peek = 7, list[idx] = 8 (s.peek != list[idx] 이므로 (+))

push 8 -> s.peek = 8, list[idx] = 8 (s.peek == list[idx] 이므로 (-)후에 idx++)

              s.peek = 7, list[idx] = 7 (s.peek == list[idx] 이므로 (-)후에 idx++)

              s.peek = 5, list[idx] = 5 (s.peek == list[idx] 이므로 (-)후에 idx++)

              s.peek = 2, list[idx] = 2 (s.peek == list[idx] 이므로 (-)후에 idx++)

              s.peek = 1, list[idx] = 1 (s.peek == list[idx] 이므로 (-)후에 idx++)

 

여기서 8까지 push 완료하였고, 스택 안의 모든 숫자가 pop되었으므로 순서대로 출력해주시면 됩니다.

만약에 모든 push가 이루어졌는데 pop이 더이상 진행되지 못할 경우에는 NO를 출력해주셔야합니다.

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static Stack<Integer> s = new Stack<>();
    static int list[];
    static int N;
 
    static void func() {
        int idx = 0;
        for (int i = 1; i <= N; i++) {
            s.add(i);
            sb.append("+\n");
            while (!s.isEmpty() && idx < N && s.peek() == list[idx]) {
                s.pop();
                sb.append("-\n");
                idx++;
            }
        }
        
        while(!s.isEmpty() && idx < N && s.peek() == list[idx]) {
            s.pop();
            sb.append("-\n");
            idx++;
        }
        if(!s.isEmpty()) {
            sb = new StringBuffer();
            sb.append("NO\n");
        }
        
        System.out.println(sb.toString());
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 2504 괄호의 값  (0) 2021.01.26
boj 6198 옥상 정원 꾸미기  (0) 2021.01.26
boj 17298 오큰수  (0) 2021.01.25
boj 4358 생태학  (0) 2021.01.25
boj 5639 이진 검색 트리  (0) 2021.01.24

www.acmicpc.net/problem/17298

 

17298번: 오큰수

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

www.acmicpc.net

스택으로 구현할 수 있고, 시간초과에 주위해야하는 문제입니다.

자바에서는 출력만으로도 시간초과가 나올 수 있기때문에 반복적인 System.out.println 보다는

StringBuffer, StringBuilder, BufferedWriter 중에서 사용해야합니다.

 

우선 오큰수는 자신의 오른쪽에 있는 숫자들 중에서 자신보다 큰 수 중에 가장 왼쪽에 있는 수를 말합니다.

 

저는 이 문제를 해결하기 위해 수열의 역순으로 탐색을 하였습니다.

list[i]를 스택에 넣기 전에 자신보다 작은 값들을 전부 pop해준 후에 남아있는 스택의 top에 있는 값이 오큰수 입니다.

 

먼저 스택이 비어있다면 자신이 가장 큰 수이므로 -1입니다.

비어있지 않다면 스택의 top이 오큰수입니다.

 

이 값들을 StringBuffer에 다 append를 해준 후에 마지막에 sb.toString()을 출력해주시면 되겠습니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static Stack<Integer> s = new Stack<>();
    static int list[], ans[];
    static int N;
 
    static void print() {
        for (int i = 0; i < N; i++) {
            sb.append(ans[i] + " ");
        }
 
        System.out.println(sb.toString() + "\n");
    }
 
    static void func() {
        for (int i = N - 1; i >= 0; i--) {
            while (!s.isEmpty() && s.peek() <= list[i])
                s.pop();
 
            if (s.isEmpty())
                ans[i] = -1;
            else
                ans[i] = s.peek();
 
            s.add(list[i]);
        }
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new int[N];
        ans = new int[N];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        print();
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 6198 옥상 정원 꾸미기  (0) 2021.01.26
boj 1874 수택 수열  (0) 2021.01.25
boj 4358 생태학  (0) 2021.01.25
boj 5639 이진 검색 트리  (0) 2021.01.24
boj 1991 트리 순회  (0) 2021.01.22

www.acmicpc.net/problem/4358

 

4358번: 생태학

프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어

www.acmicpc.net

나무의 각 종의 이름이 입력으로 들어오면 사전순으로 각 종의 비율을 출력하는 문제입니다.

사전순으로 출력하기 위해 Map 중에서 TreeMap을 사용하였습니다.

 

이름이 주어질 때마다 새로운 이름이면 생성하여 맵에넣고, 기존에 있던 이름이면 +1.0한 값을 맵에 넣어줍니다.

 

맵의 데이터들을 출력하기 위해 Entry를 사용하였고, e.getKey()(이름)과 e.getValue()/N *100 (비율)을 출력하였습니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Map.Entry;
import java.util.TreeMap;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static String st;
    static TreeMap<String, Double> m = new TreeMap<>();
    static double N;
 
    static void func() {
        StringBuffer sb = new StringBuffer();
        for (Entry<String, Double> e : m.entrySet()) {
            sb.append(e.getKey() + " " + String.format("%.4f", e.getValue() * 100.0 / N) + "\n");
        }
 
        System.out.println(sb.toString());
    }
 
    static void input() throws Exception {
        while (true) {
            st = br.readLine();
            if (st == null || st.length() == 0)
                break;
 
            if (m.containsKey(st)) {
                double a = m.get(st);
 
                m.put(st, a + 1.0);
            } else {
                m.put(st, 1.0);
            }
 
            N += 1.0;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 1874 수택 수열  (0) 2021.01.25
boj 17298 오큰수  (0) 2021.01.25
boj 5639 이진 검색 트리  (0) 2021.01.24
boj 1991 트리 순회  (0) 2021.01.22
boj 11003 최솟값 찾기  (0) 2021.01.22

www.acmicpc.net/problem/5639

 

5639번: 이진 검색 트리

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다

www.acmicpc.net

자바로 트리를 처음 구현해보았습니다..

 

입력이 전위순회이므로 들어오는 대로 트리에 넣어줍니다.

이진 검색 트리는 x가 들어오면 트리의 루트노드의 값부터 비교를 합니다.

노드의 값보다 작으면 왼쪽 서브트리이고,

노드의 값보다 크면 오른쪽 서브트리로 이동하면 되고

 

이동하려는 서브트리가 null이면 그곳에 newnode를 삽입하면 됩니다.

출력은 후위순회로 출력입니다.

 

 

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuffer sb = new StringBuffer();
 
    static class tree {
        int x;
        tree llink;
        tree rlink;
 
        tree() {
        }
 
        tree(int x, tree llink, tree rlink) {
            this.x = x;
            this.llink = llink;
            this.rlink = rlink;
        }
    }
 
    static tree node = new tree();
 
    static void addnode(int x) {
        tree newnode = new tree(x, null, null);
 
        if (node.x == 0) {
            node.x = x;
            return;
        }
 
        tree p = node;
 
        while (p != null) {
            if (p.x > x) {
                if (p.llink == null) {
                    p.llink = newnode;
                    break;
                } else
                    p = p.llink;
            } else {
                if (p.rlink == null) {
                    p.rlink = newnode;
                    break;
                } else
                    p = p.rlink;
            }
        }
    }
 
    static void postorder(tree t) {
        if (t.llink != null)
            postorder(t.llink);
        if (t.rlink != null)
            postorder(t.rlink);
        sb.append(t.x + "\n");
    }
 
    static void input() throws Exception {
        String st;
        while (true) {
            st = br.readLine();
            if (st == null || st.length() == 0)
                break;
 
            int x = Integer.parseInt(st);
            addnode(x);
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        postorder(node);
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 17298 오큰수  (0) 2021.01.25
boj 4358 생태학  (0) 2021.01.25
boj 1991 트리 순회  (0) 2021.01.22
boj 11003 최솟값 찾기  (0) 2021.01.22
boj 2517 달리기  (0) 2021.01.22

www.acmicpc.net/problem/2042

 

2042번: 구간 합 구하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄

www.acmicpc.net

세그먼트 트리의 기본적인 문제입니다.

 

처음에 list가 주어지고 그 다음에 연산이 주어집니다.

a가 1이면 b번째 수를 c로 변경, a가 2이면 [b~c] 구간 값의 합을 출력합니다.

 

a가 1일경우에 c를 long으로 받아야하기 때문에 자료형변환의 실수가 있어서 NumberFormat 오류가 많이 발생했습니다..ㅠ

 

 

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static long list[], tree[];
    static int N, M, K;
 
    static long init(int node, int s, int e) {
        if (s == e)
            return tree[node] = list[s];
 
        int m = (s + e) / 2;
        return tree[node] = init(node * 2, s, m) + init(node * 2 + 1, m + 1, e);
    }
 
    static void update(int node, int s, int e, int idx, long diff) {
        if (idx < s || idx > e)
            return;
 
        tree[node] += diff;
 
        int m = (s + e) / 2;
        if (s != e) {
            update(node * 2, s, m, idx, diff);
            update(node * 2 + 1, m + 1, e, idx, diff);
        }
    }
 
    static long query(int node, int s, int e, int l, int r) {
        if (l <= s && e <= r)
            return tree[node];
        if (s > r || l > e)
            return 0;
 
        int m = (s + e) / 2;
 
        return query(node * 2, s, m, l, r) + query(node * 2 + 1, m + 1, e, l, r);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        list = new long[N + 1];
        tree = new long[N * 4 + 1];
 
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = Integer.parseInt(st.nextToken());
        }
 
        init(1, 1, N);
 
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < M + K; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            long c = Long.parseLong(st.nextToken());
 
            if (a == 1) {
                update(1, 1, N, b, c - list[b]);
                list[b] = c;
            } else {
                sb.append(query(1, 1, N, b, (int) c) + "\n");
            }
        }
 
        System.out.println(sb.toString());
    }
 
    public static void main(String[] args) throws Exception {
        input();
    }
}
 cs

'algorithm > SegmentTree' 카테고리의 다른 글

boj 14438 수열과 쿼리 17  (0) 2021.02.21
boj 13537 수열과 쿼리 1  (0) 2021.02.21
boj 6549 히스토그램에서 가장 큰 직사각형  (0) 2021.02.19
boj 2104 부분배열 고르기  (0) 2021.02.19
boj 2243 사탕상자  (0) 2021.02.04

www.acmicpc.net/problem/20419

 

20419번: 화살표 미로 (Easy)

첫번째 줄에는 미로의 행 R, 열 C, 준서가 가진 주문서 세트의 개수 K가 주어진다. 두번째 줄부터 R줄에 걸쳐 화살표 미로의 지도가 입력된다. 각 줄마다 "UDLR"로만 이루어진 길이 C의 문자열이 입

www.acmicpc.net

문제를 잘못 이해하는 바람에 4번이나 WA를 받고 깨달았습니다...

 

이 문제는 (1, 1)에서 (R, C)로 이동하면 탈출하는 문제입니다.

저는 (R, C)에서 오른쪽으로 가느니 밑으로 가느니 이런 삽질을 하였습니다 ㅠㅠ

 

아무튼..

 

문제는 bfs로 해결하였습니다.

K가 0아니면 1이었기 때문에 queue에 {x좌표, y좌표, 주문서 사용}를 저장하였고,

 

해당 칸에 명시되어 있는 방향으로 이동한 좌표, 주문서를 사용하며 이동한 좌표 모두 queue에 담으며 탐색하였습니다.

 

 

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
package BOJ.bfs;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Boj20419 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][];
    static int direct[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
    static boolean visit[][][];
    static int N, M, K;
 
    static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { 0, 0, 0 });
        visit[0][0][0] = true;
        while (!q.isEmpty()) {
            int x = q.peek()[0];
            int y = q.peek()[1];
            int k = q.peek()[2];
            q.remove();
 
            if (x == N - 1 && y == M - 1) {
                System.out.println("Yes");
                return;
            }
 
            int d = list[x][y];
            int nx = x + direct[d][0];
            int ny = y + direct[d][1];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                if (!visit[nx][ny][k]) {
                    q.add(new int[] { nx, ny, k });
                    visit[nx][ny][k] = true;
                }
            }
 
            if (K > 0) {
                if ((1 & k) == 0) { // Left
                    int nk = k | 1;
                    int nd = d - 1;
                    if (nd == -1)
                        nd = 3;
 
                    nx = x + direct[nd][0];
                    ny = y + direct[nd][1];
                    if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                        if (!visit[nx][ny][nk]) {
                            q.add(new int[] { nx, ny, nk });
                            visit[nx][ny][nk] = true;
                        }
                    }
                }
 
                if ((2 & k) == 0) { // Right
                    int nk = k | 2;
                    int nd = d + 1;
                    if (nd == 4)
                        nd = 0;
 
                    nx = x + direct[nd][0];
                    ny = y + direct[nd][1];
                    if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                        if (!visit[nx][ny][nk]) {
                            q.add(new int[] { nx, ny, nk });
                            visit[nx][ny][nk] = true;
                        }
                    }
                }
            }
 
        }
 
        System.out.println("No");
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        list = new int[N][M];
        visit = new boolean[N][M][4];
        K = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            for (int j = 0; j < M; j++) {
                char ch = str.charAt(j);
                if (ch == 'U')
                    list[i][j] = 0;
                else if (ch == 'R')
                    list[i][j] = 1;
                else if (ch == 'D')
                    list[i][j] = 2;
                else
                    list[i][j] = 3;
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        bfs();
    }
}
cs

'algorithm > bfs' 카테고리의 다른 글

boj 1012 유기농 배추  (0) 2021.02.03
boj 16956 늑대와 양  (0) 2021.02.03
boj 2638 치즈  (0) 2021.01.22
boj 17142 연구소 3  (0) 2021.01.22
boj 2636 치즈  (0) 2021.01.22

+ Recent posts

티스토리툴바