[☁️ 구름톤 챌린지] 2주차 학습일지 - 1

문제 6. 문자열 나누기

이번 문제는 각 단계마다 해당 자료형을 어떻게 사용하면 좋을지 생각하면 좋을 것 같다.

import java.io.*;
import java.util.*;
import java.lang.*;

class Main {
	static int N;
	static String S;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		S = br.readLine();
		int result = 0;
		
        // 나올 수 있는 조합 리스트
		List<String[]> wordList = new ArrayList<>();
        // 중복 제거를 위해 set 자료형 사용
		Set<String> set = new HashSet<>();
		
		// 문자열을 부분문자열로 나눈다.
		for(int i = 1; i < N; i++) {
			for(int j = i+1; j < N; j++) {
				String first = S.substring(0,i);
				String second = S.substring(i, j);
				String third = S.substring(j);
                // 조합 리스트를 만든다.
				wordList.add(new String[]{first, second, third});
				set.add(first);
				set.add(second);
				set.add(third);
			}
		}

		// 부분문자열을 중복 제거하고 사전 순서로 배열을 정렬된 상태로 만든다.
		List<String> tempScoreList = new ArrayList<>(set);
		Collections.sort(tempScoreList);
		
		// HashMap에 정렬된 상태의 배열과 인덱스를 저장한다.
		Map<String, Integer> wordScore = new HashMap<>();
		for(int i = 0; i < tempScoreList.size(); i++) {
			wordScore.put(tempScoreList.get(i), i+1);
		}

		int maxScore = -1;
		// 조합을 하나씩 꺼낸다.
		for(String[] words : wordList) {
			int tempScore = 0;
			// 꺼낸 조합에서 index를 가지고 tempScore를 구한다. 
			for(String word : words) {
				tempScore += wordScore.get(word);
			}
			maxScore = Math.max(maxScore, tempScore);
		}
		System.out.println(maxScore);	
	}
}

이번 문제에서 사용한 Set 자료형에 대해 알아보자.

Set 자료형의 특징은 다음과 같다.

- 객체(데이터)를 중복해서 저장할 수 없다.

- 저장된 객체(데이터)를 인덱스로 관리하지 않아, 저장 순서가 보장되지 않는다.

- 대표적인 클래스는 HashSet, TreeSet, LinkedHashSet이 있다.

- 데이터를 검색하려면 iterator() 메서드로 iterator(반복자)를 생성하고 데이터를 가져와야 한다.

Iterator<String> it = set.iterator();

while (it.hasNext()) { 			   // hasNext() : 데이터가 있으면 true 없으면 false
	System.out.println(it.next()); // next() : 다음 데이터 리턴
}

 

HashSet

- 데이터를 중복 저장할 수 없고 순서를 보장하지 않는다.

 

TreeSet

- 중복된 데이터를 저장할 수 없고, 입력한 순서대로 값을 저장지 않는다.

- 오름차순으로 데이터를 정렬한다.

 

LinkedHashSet 

- 중복된 데이터를 저장할 수 없다.

- 입력된 순서대로 데이터를 관리한다.

 

문제 7. 구름 찾기 깃발

이 문제는 완전 탐색 문제이다.

- 8방향으로 돌면서, 도달할 수 있는지 확인하고 갈 수 있으면 방문한다.

- 해당 지점이 1이면 count를 1 더한다.

- result 배열을 업데이트하고, result 배열에 k의 개수를 확인한다.

import java.io.*;
import java.util.*;

class Main {
	static int N, K;
	static int[][] M, result;
	static int[] dy = {0,-1,-1,-1,0,1,1,1};
	static int[] dx = {1,1,0,-1,-1,-1,0,1};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine()); 
		N =	Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		M = new int[N][N];
		result = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++){
				M[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				int count = 0;
				if(M[i][j] == 1) {
					continue;
				}
				for(int k = 0; k < 8; k++){
					int n_y = i + dy[k];
					int n_x = j + dx[k];
					if(n_y >= N || n_y < 0 || n_x >= N || n_x < 0) {
						continue;
					}
					if(M[n_y][n_x] == 1) {
						count += 1;
					}
				}
				result[i][j] = count;
			}
		}
		
		int k_count = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(result[i][j] == K) {
					k_count += 1;
				}
			}
		}
		
		System.out.println(k_count);
	}
}