구름톤 챌린지 2주 차 학습 일기 (Day6 ~ 8)

🧩 문제 6. 문자열 나누기

> 배운 점

문자열을 분리하는 모든 경우의 수를 조합으로 탐색하는 방법 (완전탐색)

- 문자열 길이가 최대 100으로 크기가 작으니까 완전 탐색으로 해결 가능

( 보통 조합은 재귀 함수로 구함)

 

 

> 느낀 점

[문제 해결 단계]를 먼저 손으로 꼭 써보고 코드로 작성하자.

1. 가능한 부분 문자열을 찾고, 정렬해 점수판 만듦
2. 완전탐색으로 문자열을 자를 수 있는 모든 경우의 수 찾음
3. 점수판을 이용해 모든 경우의 수 中 최대 점수를 찾음

(코드 참고 : https://goorm.notion.site/Java-8df05c32e4574e0f87c6c0a846a387af)

import java.io.*;
import java.util.*;
 
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
        String str = br.readLine();
 
        // 1) 모든 부분 문자열, 배열에 저장
        List<String[]> wordList = new ArrayList<>();    // 📍 단어 집합 저장 리스트
        Set<String> score = new HashSet<>();            // 점수 목록 (중복 제거)
 
        // 위치 2개 정하는 모든 조합 구하기
        for(int i = 1 ; i < N ; i++) {
            for(int j = i + 1 ; j < N ; j++) {
 
                // 가능한 부분 문자열 구하기
                String first  = str.substring(0, i);
                String second = str.substring(i, j);
                String third  = str.substring(j);
 
                wordList.add(new String[] {first, second, third});    // 📍 나눠진 단어, 하나의 집합으로 리스트에 저장
 
                // 발생하는 부분 문자열, 점수 계산 
                score.add(first);
                score.add(second);
                score.add(third);
            }
        }
 
 
        // 2) 점수판 만들기
 
        // 🔔 score 변수 값 사전 순으로 정렬
        List<String> tmpScoreList = new ArrayList<>(score);
        Collections.sort(tmpScoreList);
 
        // 🔔 객체에 Key로 전환
        Map<String, Integer> wordScore = new HashMap<>();
        for(int i = 0 ; i < tmpScoreList.size() ; i++) {
            wordScore.put(tmpScoreList.get(i), i + 1);
        }
 
        // 3) 최고 점수 구하기
        int max = -1;
        for (String[] words : wordList) {
            int tmpScore = 0;
 
            for (String word : words) {
                tmpScore += wordScore.get(word);
            }
 
            max = Math.max(max, tmpScore);
        }
 
        System.out.println(max);
    }
}
 

 

로직을 직접 써보고, 구현해야 겠다.

머릿속에서만 생각하고 하려니 잘 안 풀림,,,ㅠ

 

 

> 헷갈렸던 점

: 한 문자열을 3개로 나누는 모든 조합을 구하는 코드를 작성하는 것이 쉽지 않았다.

⇨ 모든 부분 문자열 구하기

    -> 단어 3개로 나눠야하므로 1 ~ N -1 사이의 인덱스 2개를 정해 나눔

 

 

⇨ 재귀 함수 사용하는 버전도 고민해봤었는데 아래와 같다.

import java.util.ArrayList;
import java.util.List;
 
public class StringDivisions {
    public static void main(String[] args) {
 
        String input = "abcdefgh";
 
        List<String> divisions = divideStringIntoCombinations(input);
        
        for (String division : divisions) {
            System.out.println(division);
        }
    }
    
    // 문자열을 3개로 나누는 모든 조합을 생성하는 함수
    private static List<String> divideStringIntoCombinations(String input) {
 
        List<String> divisions = new ArrayList<>();
        makeDivisions(input, "", 1, divisions);
 
        return divisions;
    }
    
    // 재귀 함수 사용해 모든 조합 생성
    private static void makeDivisions(String input, String current, int partsRemain, List<String> divisions) {
 
        if (partsRemain == 0) {
            divisions.add(current);
            return;
        }
        
        for (int i = 1 ; i <= input.length() ; i++) {
 
            String part = input.substring(0, i);
            String rest = input.substring(i);
 
            makeDivisions(rest, current + part + " ", partsRemain - 1, divisions);
        }
    }
}

 

 

그럼 이렇게 결과가 나온다 함.

 

 

🧩 문제 7. 구름 찾기 깃발

> 배운 점

- 완전탐색
- 행렬에서의 이동 개념 (8방향)
   (상하좌우 + 왼쪽 위 대각선 / 오른쪽 위 대각선 / 왼쪽 아래 대각선 / 오른쪽 아래 대각선)

 

> 느낀 점

: 8방향 bfs 문제는 손에 꼽을 정도로 풀어봐서 맞을까...? 싶었는데 한 번에 맞아서 기분이 좋았다..ㅎㅎ

 

> 헷갈렸던 점

: 정답 배열을 채우기 위한 bfs를 수행할 때,

 

1) 입력받을 때 값이 0인 칸을 큐에 추가하고, bfs를 1번만 수행할 것인지,

2) 값이 0인 모든 칸에 대해 bfs를 매번 수행할 것인지

 

고민했었다.

 

결국 1) 값이 0인 칸을 큐에 추가하고 bfs를 1번만 수행하는 식으로 진행해 해결했다.

import java.io.*;
import java.util.*;
 
class Main {
    static int N, K;
    static int[][] board, answer;
    
    static int[] dx = {0,0,-1,1,-1,-1,1,1};
    static int[] dy = {1,-1,0,0,-1,1,-1,1};
    
    static Queue<int[]> queue = new LinkedList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());    // 게임판 크기
        K = Integer.parseInt(st.nextToken());    // 찾고 싶은 깃발 값
        
        // 1. 입력 받기
        board = new int[N][N];
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                
                if(board[i][j] == 0) {
                    queue.add(new int[] {i, j});
                }
            }
        }
        
        
        // 2. 배열 채우기 - bfs 한 번만 수행
        answer = new int[N][N];
        bfs();
        
        
        // 3. 값이 K인 깃발 개수 출력하기
        int cnt = 0;
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < N ; j++) {
                if(answer[i][j] == K) {
                    cnt++;
                }
            }
        }
        
        System.out.println(cnt);
    }
    
    // BFS - 정답 배열 채우는 메소드
    private static void bfs() {
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            
            for(int d = 0 ; d < 8 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(nx < 0 || ny < 0 || nx >= N || ny >= N || board[nx][ny] == 0)    continue;
                if(board[nx][ny] == 1) {
                    answer[now[0]][now[1]]++; // 2차원 정답 배열 값 갱신
                }
            }
        }
    }
}

 

 

🧩 문제 8. 통증

> 배운 점

: 그리디

 

> 느낀 점

: 거스름돈 문제와 비슷하다.

 

통증 수치 N과 같은 값을 갖는 변수 tmp를 지정한다.

 

tmp가 14로 나눴을 때 몫이 0보다 크다면, 14만큼 나눈 값을 아이템 수 cnt에 더하고 tmp를 14로 나눈 값의 나머지로 바꾼다.

그 이후에 7도, 1도 그렇게 진행한다.

 

최종적으로 나온 cnt를 정답으로 하면 된다.

 

> 헷갈렸던 점

: 없다.

 

 

---

6일차 문제가 좀 생각할 게 있어서 겁먹었는데

오히려 7,8일차가 갈수록 문제가 쉬워져서 더 빠르게 풀 수 있었다.