'Computer/Algorithm_Java' 카테고리의 글 목록 (4 Page)

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

☕Language: Java

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

class Solution {
    public String solution(int a, int b) {
        String answer = "";
        String[] strArr = {"THU", "FRI", "SAT", "SUN", "MON", "TUE", "WED"};
        
        int monthDay = calcMonthToDay(a) + b;
        answer = strArr[monthDay%7];
 
        return answer;
    }
    
    public static int calcMonthToDay(int month){
        int day = 0;
        while(--month>0){
            switch (month) {
                case 2:
                    day += 29;
                    break;
                case 4:
                case 6:
                case 9:
                case 11:
                    day += 30;
                    break;
                default:
                    day += 31;
            }
        }
        return day;
    }
}
 
 

🤔 해설

1. calcMonthToDay(int month)

- switch문을 활용한 일자 계산

- while(--month>0)

- 해당 월은 계산하지 않으므로 전위 연산자 사용

2. String[] strArr

- 1월 1일 기준 금요일에 맞춰 strArr 선언

3. strArr[monthDay%7]

- 요일 구하기

😮 이 외의 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
  public String solution(int a, int b) {
      String answer = "";
 
      int[] lastDayOfTheMonth = {31,29,31,30,31,30,31,31,30,31,30,31};
      String[] DayOfTheWeek ={"FRI","SAT","SUN","MON","TUE","WED","THU"};
      int totalDay = 0;
      for(int i = 0 ; i< a-1; i++){
          totalDay += lastDayOfTheMonth[i];
      }
      totalDay += b-1;
      answer = DayOfTheWeek[totalDay %7];
 
      return answer;
  }
}
 
 

* 배열 활용

1
2
3
4
5
6
7
8

import java.time.*;
 
class Solution {
  public String solution(int a, int b) {
      return LocalDate.of(2016, a, b).getDayOfWeek().toString().substring(0,3);
  }
}
 
 

* time 함수 사용

🔗 소스 코드
GitHub

📚 참고 자료

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

저작자표시 (새창열림)

'Computer > Algorithm_Java' 카테고리의 다른 글

[Algorithm_Java] 광물 캐기 (Success) (0)	2023.10.14
[Algorithm_Java] 연속된 부분 수열의 합 (Success) (0)	2023.10.13
[Algorithm_Java] 문자열 내 p와 y의 개수 (Success) (1)	2023.10.11
[Algorithm_Java] 24480번 알고리즘 수업 - 깊이 우선 탐색 2 (Success) (0)	2023.10.08
[Algorithm_Java] 15652번 N과 M (4) (Success) (1)	2023.10.05

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

☕Language: Java

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

class Solution {
    boolean solution(String s) {
        
        // 1. s에 'p'의 개수와 'y'의 개수를 비교해 같으면 True, 다르면 False를 return
        // 2. 'p', 'y' 모두 하나도 없는 경우는 항상 True를 리턴'
        // 3. 개수를 비교할 때 대문자와 소문자는 구별하지 않음
        
        boolean answer = true;
        int cnt = 0;
        
        s = s.toLowerCase();
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            if(c=='p'){
                cnt++;
            }
            if(c=='y'){
                cnt--;
            }
        }
        
        if(cnt!=0){
            answer = false;
        }
 
        return answer;
    }
}
 
 

🤔 해설

1. toLowerCase()

- 대소문자 -> 소문자로 통일

2. for문 + if문

- p일 때는 cnt +1, y일 때는 cnt -1로 stack과 유사하게 구현

- cnt가 0일 때만 true 반환

😮 이 외의 풀이

1
2
3
4
5
6
7
8

class Solution {
    boolean solution(String s) {
        s = s.toUpperCase();
 
        return s.chars().filter( e -> 'P'== e).count() == s.chars().filter( e -> 'Y'== e).count();
    }
}
 
 

* 람다식 사용

1
2
3
4
5
6
7

class Solution {
    boolean solution(String s) {
 
        return s.replaceAll("[^yY]", "").length() - s.replaceAll("[^pP]", "").length() == 0 ? true : false;
    }
}
 
 

* 정규식 사용

- s.replaceAll("[^yY]", "")

- y 또는 Y가 아닌 문자 제거(공란으로 replace)

🚨 문자열을 두 번 수정하고 두 번 길이를 계산하므로 효율적이지 않을 수 있음

🔗 소스 코드
GitHub

📚 참고 자료

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

저작자표시 (새창열림)

'Computer > Algorithm_Java' 카테고리의 다른 글

[Algorithm_Java] 연속된 부분 수열의 합 (Success) (0)	2023.10.13
[Algorithm_Java] 2016년 (Success) (0)	2023.10.12
[Algorithm_Java] 24480번 알고리즘 수업 - 깊이 우선 탐색 2 (Success) (0)	2023.10.08
[Algorithm_Java] 15652번 N과 M (4) (Success) (1)	2023.10.05
[Algorithm_Java] 24479번 알고리즘 수업 - 깊이 우선 탐색 1 (Success) (0)	2023.10.02

24480번: 알고리즘 수업 - 깊이 우선 탐색 2

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양

www.acmicpc.net

☕ Language: Java

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

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
 
    static int[] visited;
 
    static List<ArrayList<Integer>> graph = new ArrayList<>(); // 정점들의 정보를 기록할 그래프
 
    static int count = 1;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());
 
        visited = new int[N + 1];
 
        // graph의 index를 정점의 개수만큼 만들어줌
        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<>());
        }
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int fromN = Integer.parseInt(st.nextToken());
            int toN = Integer.parseInt(st.nextToken());
 
            // 무방향이기 때문에 양쪽으로 정보를 추가
            graph.get(fromN).add(toN);
            graph.get(toN).add(fromN);
        }
 
        // 내림차순 정렬
        Comparator<Integer> descComparator = Collections.reverseOrder();
 
        for (int i = 1; i < graph.size(); i++) {
            Collections.sort(graph.get(i), descComparator);
        }
 
        // 깊이 우선 탐색 재귀 시작
        dfs(R);
 
        StringBuilder sb = new StringBuilder();
 
        // 각 인덱스별로 방문 순서가 기록된 배열을 순회하며, 값을 StringBuilder에 저장
        for (int i = 1; i < visited.length; i++) {
            sb.append(visited[i]).append("\n");
        }
 
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
    }
 
    // 깊이 우선 탐색 메서드
    private static void dfs(int R) {
        visited[R] = count; // 현재 방문하고있는 정점에 순서 저장
 
        // 현재 위치한 정점이 갈 수 있는 정점 리스트를 순회
        for (int i = 0; i < graph.get(R).size(); i++) {
            int newN = graph.get(R).get(i);
 
            // 다음 갈 정점을 방문했었는지 체크(0일 경우 방문 X)
            if (visited[newN] == 0) {
                count++;
                dfs(newN);
            }
        }
    }
 
}
 
 

24479번 알고리즘 수업 - 깊이 우선 탐색 1과 동일하나, 내림차순 정렬

🔗 소스 코드
GitHub

📚 참고 자료

[Algorithm_Java] 24479번 알고리즘 수업 - 깊이 우선 탐색 1 (Success)

24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점

hj0216.tistory.com

저작자표시 (새창열림)

'Computer > Algorithm_Java' 카테고리의 다른 글

[Algorithm_Java] 2016년 (Success) (0)	2023.10.12
[Algorithm_Java] 문자열 내 p와 y의 개수 (Success) (1)	2023.10.11
[Algorithm_Java] 15652번 N과 M (4) (Success) (1)	2023.10.05
[Algorithm_Java] 24479번 알고리즘 수업 - 깊이 우선 탐색 1 (Success) (0)	2023.10.02
[Algorithm_Java] 10872번 팩토리얼 (Success) (0)	2023.10.01

15652번: N과 M (4)

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

www.acmicpc.net

☕Language: Java

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.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int[] arr;
    public static StringBuilder sb = new StringBuilder();
 
    public static int N, M;
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        arr = new int[M];
        dfs(1, 0);
 
        br.close();
 
        bw.write(sb.toString());
 
        bw.flush();
        bw.close();
 
    }
 
    public static void dfs(int idx, int depth) {
        if (depth == M) {
            for (int val : arr) {
                sb.append(val).append(' ');
            }
            sb.append('\n');
            return;
        }
 
        for (int i = idx; i <= N; i++) {
            arr[depth] = i;
            dfs(i ,depth + 1);
 
        }
    }
}
 
 

🤔 해설

1. arr = new int[M];

- 출력을 위한 arr 배열 생성

2. dfs(1, 0);

- dfs(방문 시작점, 배열 내 위치)

3. for (int i = idx; i <= N; i++) {

- i를 idx부터 시작함으로써 다음 depth에서 시작점보다 작은 값을 방문하지 않도록 함

4. arr[depth] = i;

- 배열 내 현재 위치에 값 입력

5. dfs(i, depth + 1);

- 깊은 노드로 이동

🔗 소스 코드
GitHub

저작자표시 (새창열림)

'Computer > Algorithm_Java' 카테고리의 다른 글

[Algorithm_Java] 문자열 내 p와 y의 개수 (Success) (1)	2023.10.11
[Algorithm_Java] 24480번 알고리즘 수업 - 깊이 우선 탐색 2 (Success) (0)	2023.10.08
[Algorithm_Java] 24479번 알고리즘 수업 - 깊이 우선 탐색 1 (Success) (0)	2023.10.02
[Algorithm_Java] 10872번 팩토리얼 (Success) (0)	2023.10.01
[BaekJoon] 11866번 요세푸스 문제 0 문제 풀이 (Success) (0)	2023.09.30

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양

www.acmicpc.net

☕ Language: Java

😮 찾아본 풀이

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

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
    
    // 정점들의 방문 순서를 저장
    static int[] visited;
    
    // 정점들의 정보를 기록할 그래프
    static List<ArrayList<Integer>> graph = new ArrayList<>();
 
    // 방문 순서
    static int count = 1;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());
        
        // 1부터 시작하도록 배열의 크기 N+1 지정
        visited = new int[N+1];
        
        // graph의 크기를 정점의 개수만큼 생성
        for(int i =0; i < N+1; i++) {
            graph.add(new ArrayList<>());
        }
        
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int fromN = Integer.parseInt(st.nextToken());
            int toN = Integer.parseInt(st.nextToken());
 
            // 무방향이기 때문에 양쪽으로 정보를 추가
            graph.get(fromN).add(toN);
            graph.get(toN).add(fromN);
        }
        
        // 오름차순 정렬
        for(int i = 1; i < graph.size(); i++) {
            Collections.sort(graph.get(i));
        }
        
        // 깊이 우선 탐색 재귀 시작
        dfs(R);
        
        StringBuilder sb = new StringBuilder();
        
        // 방문 순서가 기록된 배열을 순회하며, 값을 StringBuilder에 저장
        for(int i = 1; i < visited.length; i++) {
            sb.append(visited[i]).append("\n");
        }
        
        bw.write(sb.toString());
        
        bw.flush();
        bw.close();
    }
    
    // 깊이 우선 탐색 메서드
    private static void dfs(int R) {
        visited[R] = count;
        // 현재 방문하고있는 정점에 순서 저장
 
        // 현재 위치한 정점이 갈 수 있는 정점 리스트를 순회
        for(int i = 0; i < graph.get(R).size(); i++) {
            int newN = graph.get(R).get(i);
                
            // 다음 갈 정점을 방문했었는지 체크(0일 경우 방문 X)
            if(visited[newN] == 0){
                count++;
                dfs(newN);
            }
        }
    }
 
}
 
 

🤓 예시

시작 정점이 1로 주어져 있으므로, 1부터 방문 탐색 시작

dfs(1)

visited[1] = 1 (방문 순서를 집계하는 count 변수도 1부터 시작)

newN = 외부 ArrayList의 방문 탐색 정점(1)에서 연결된 다른 정점

만일 1과 3이 연결되어 있다면

3은 아직 방문하지 않았으므로 visited[3]==0

방문순서 count 증가

dfs(3)

visited[3] = 2

newN = 외부 ArrayList의 방문 탐색 정점(3)에서 연결된 다른 정점

만일 3과 2가 연결되어 있다면

2는 아직 방문하지 않았으므로 visited[2]==0

방문순서 count 증가

dfs(2)

visited[2] = 3

newN = 외부 ArrayList의 방문 탐색 정점(2)에서 연결된 다른 정점

만일 2와 3이 연결되어 있다면

3은 방문하였으므로 visited[3]!=0

2와 연결된 다른 정점 탐색

... 반복

🔗 소스 코드
GitHub

📚 참고 자료

[백준] 깊이 우선 탐색_24479,24480_자바

안녕하세요😎 백엔드 개발자 제임스입니다 :) 오늘은 [깊이 우선 탐색] 이라는 문제를 포스팅하려고 합니다. 그래프와 관련된 문제를 해결할 때, 두 가지의 해결법이 있습니다. 첫 번째는 깊이

kang-james.tistory.com

저작자표시 (새창열림)

'Computer > Algorithm_Java' 카테고리의 다른 글

[Algorithm_Java] 24480번 알고리즘 수업 - 깊이 우선 탐색 2 (Success) (0)	2023.10.08
[Algorithm_Java] 15652번 N과 M (4) (Success) (1)	2023.10.05
[Algorithm_Java] 10872번 팩토리얼 (Success) (0)	2023.10.01
[BaekJoon] 11866번 요세푸스 문제 0 문제 풀이 (Success) (0)	2023.09.30
[BaekJoon] 1934번 최소공배수 문제 풀이 (Success) (0)	2023.09.29

이모저모 개발 블로그