<stdio.han>

구름톤 챌린지 연합

[느낀점]

쉬운문제인줄알았는데 생각보다 어려워서 풀이를 참고했다. 지금까지 풀었던 문제인 큐에 담아 탐색하는 문제이다. 이번 주 구름톤 챌린지는 그래프 문제인데 그래프 문제는 자신이없어서 큰일이다. 풀이를 최소한으로 참고하면서 풀어 볼 예정이다.

[결과 코드]

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		boolean[][] bridges = new boolean[N+1][N+1];
		boolean[] visited = new boolean[N+1];//default == false
		for(int i=0;i<M;i++){
			st = new StringTokenizer(br.readLine(), " ");
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			bridges[s][e] = true;
		}
		int count = 0;
		for(int i=1;i<=N;i++){
			if(visited[i]==false){
			Queue<Integer> q = new LinkedList<>();
			q.add(i);
			
			while(!q.isEmpty()){
				int currentNode = q.poll();
				visited[currentNode] = true;
				
				for(int nextNode=1;nextNode<=N;nextNode++){
					if(bridges[currentNode][nextNode] == true && 
						 bridges[nextNode][currentNode] == true && 
						 visited[nextNode] == false){
						q.add(nextNode);
					}
				}
			}
			count++;
		}
		}
		System.out.println(count);
	}
}

구름톤 챌린지 과일 구매

[느낀점]

오랜만에 풀이 없이 풀고 24시간이 지나기 전에 풀었다. 4방탐색, 8방탐색 문제가 아니라서 쉬운것도 있었고 지금까지 구름톤 챌린지를 하며 실력이 늘어 풀만한것도 있었다. 처음엔 저번에 배운 큐를 사용할까 했지만 정렬문제로인해 방향을 바꿨다. 아직 map을 value 기준으로 정렬, key 기준으로 정렬은 어려워 구글링을 했다.

[결과 코드]

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int[] count = new int[N];
		long answer = 0; // 범위가 int 의 범위를 초과하는 경우도 있어서 long 으로 선언
		Map<Integer, Integer> map = new HashMap<>();
		
		//과일의 개수는 배열에 담고, 과일 1조각당 포만감은 맵에 담는다. 맵의 키는 과일 개수의 인덱스와 같다.
		for(int i=0;i<N;i++){
			st = new StringTokenizer(br.readLine(), " ");
			int p = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			if(p==1) {
				map.put(i, c);
				count[i] = p;
			} else {
				map.put(i, c/p);
				count[i] = p;
			}
		}
		//1조각당 포만감이 높은 순으로 내림차순한다
		List<Integer> keys = new ArrayList<>(map.keySet());
		Collections.sort(keys, (o1, o2) -> (map.get(o2).compareTo(map.get(o1))));
		//keys는 내림차순으로 정렬되어있기때문에 foreach문으로 keys 를 순회
		for(Integer key : keys){
			//K가 0이 될경우 break
			if(K==0){
				break;
			}
			//포만감이 높은 순으로 과일의 개수에서 하나씩 빼면서 answer에 더한다. K가 0이 될경우 break
			for(int i=0;i<count[key];i++) {
				answer+=map.get(key);
				K--;
				if(K==0){
					break;
				}
			}
		}
		System.out.println(answer);
	}
}

구름톤 챌린지 작은 노드

[느낀점]

최근 문제들이 다 큐를 이용한 탐색문제여서 그런지 이번 문제는 나름 할만했다. 간단하게 아이디어를 얻기 위해 풀이를 보았다. 이번에는 풀이를 최대한 덜 활용해 보기위해 먼저 풀이를 공부한 후 그걸 다시 그림판으로 생각을 정리 후 그 내용을 토대로 풀이를 보지 않고 작성해보았다. 물론 제출 시 오류가 나서 몇번 보긴 했지만 반복적으로 공부를 하다보니 큐를 이용한 탐색은 나름 풀수있게 된것같다.

[결과 코드]

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken()); //노드 개수
		int M = Integer.parseInt(st.nextToken()); //간선 개수
		int K = Integer.parseInt(st.nextToken()); //시작 노드 번호
		Map<Integer, List<Integer>> map = new HashMap<>(); //map을 활용해 key에 노드, value에 간선을 list로 넣는다
		boolean[] visited = new boolean[N+1]; //0부터 시작이 아닌 1부터 시작하기 때문에 N+1 개 배열 생성, 기본값 false
		
		for(int i=0;i<M;i++){
			st = new StringTokenizer(br.readLine(), " ");
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			if(!map.containsKey(s)){ //해당 노드로 시작하는 map이 없을경우 새로 생성 
				map.put(s,new ArrayList<>());
			}
			if(!map.containsKey(e)){
				map.put(e,new ArrayList<>());
			}
			map.get(s).add(e); //해당 노드에 간선list에 추가
			map.get(e).add(s);
		}
		
		Queue<Integer> q = new LinkedList<>(); //탐색을 위한 큐 생성
		q.add(K); //큐에 탐색할 노드 추가
		int answer = 0; //방문한 노드 개수
		int currentNode = K; //현재 노드
		while(!q.isEmpty()){
			currentNode = q.poll(); 
			answer++;
			visited[currentNode] = true; //방문한 노드는 true 로 변경
			List<Integer> tmpNodes = map.get(currentNode); //현재 노드의 list를 tmpNodes 로 생성
			if(tmpNodes != null && !tmpNodes.isEmpty()){ //list 가 존재하거나 혹은 존재하고 list가 들어있을때
				Collections.sort(tmpNodes); //정렬을 한다, 정렬을 하지 않을 경우 작은 노드 순서가 아닌 무작위로 조회가 되어 오답이 나온다
				for(int nextNode : tmpNodes){ //foreach 문으로 리스트 순회
					if(visited[nextNode]==false) { //방문하지 않는 노드일 경우
						q.add(nextNode); //while(!q.isEmpty()) 이기 때문에 q.add를 하여 다시 탐색할 노드를 집어 넣는다
						break; //break 문으로 빠져나와 다시 while 문을 수행한다.
					}
				}
			}
		}
		System.out.println(answer + " " + currentNode);
	}
}

구름톤 챌린지 발전기 (2)

[느낀점]

저번의 문제에서 약간 심화된 버전의 문제이다. 저번 문제를 풀이를 보며 풀어서 그런지 어느정도는 혼자서 풀 수 있었다. 하지만 요새 구름톤 트레이닝하며 강의가 매일 많고 과제도 많아져서 구름톤 챌린지 문제를 볼 시간이 부족해서 점점 문제가 밀리고 있다. 놀시간을 줄이며 최대한 둘다 가져가보려고 하고있다.

[결과 코드]

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int[][] M = new int[N][N];
		boolean[][] visited = new boolean[N][N];
		int[] score = new int[31]; //유형의 범위는 1~30이기 때문
		// dx/dy기법
		int[] dx = {0, 0, 1, -1};
		int[] dy = {1, -1, 0, 0};
		
		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++) {
				//건물의 유형이 0이 아니고 방문하지 않은 장소
				if(M[i][j] != 0 && visited[i][j] == false) {
					Queue<int[]> q = new LinkedList<>();
					q.add(new int[]{i, j});
					visited[i][j] = true;
					
					//단지의 크기 최소 1, 건물의 유형(1~30)
					int size = 1;
					int target = M[i][j];
					
					while(!q.isEmpty()){
						int[] current = q.poll();
						for(int k=0;k<4;k++) {
							//상,화,우,좌 탐색
							int nextX = current[0] + dx[k];
							int nextY = current[1] + dy[k];
							
							//맵 범위 안에있을경우
							if(nextX >= 0 && nextX < N && nextY >= 0 && nextY < N){
								//방문한 곳이 아니고 해당 위치가 큐에 들어간 유형과 같은 유형일 경우
								if(visited[nextX][nextY] == false && M[nextX][nextY] == target){
									visited[nextX][nextY] = true;
									q.add(new int[]{nextX, nextY});
									//단지의 크기 증가
									size++;
								}
							}
						}
					}
					//특정 유형으로 탐색 종료 후 크기가 K 보다 클 경우 해당 건물 유형점수 증가
					if(size >= K){
						score[target]++;
					}
				}
			}
		}
		//모든 탐색 종류 후 건물의 유형중 점수가 가장 높은것을 출력
		int maxScore = 0;
		//건물 점수가 같다면 건물유형이 큰것을 선택하기 때문에 뒤에서부터 탐색
		for(int i=30;i>=0;i--){
			if(score[i]>score[maxScore]){
				maxScore = i;
			}
		}
		System.out.println(maxScore);
	}
}

구름톤 챌린지 발전기

[느낀점]

4방탐색을 기반으로 한 심화문제이다. 물론 나는 풀이 없이는 도저히 못풀겠다. 앞으로의 문제들은 전부 다 풀이를 보고 풀 예정이다. 풀이를 보며 코드 한줄한줄 뜯어보며 풀다보면 실력이 향상하는 느낌이 든다. 문제를 다 풀고보면 나름 간단하게 느껴진다.

[결과 코드]

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int[][] M = new int[N][N];
		boolean[][] visited = new boolean[N][N];
		int count = 0;
		// dx/dy기법
		int[] dy = {1, -1, 0, 0};
		int[] dx = {0, 0, 1, -1};
		
		
		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());
			}
		}
		// dx/dy 기법을 사용한 탐색 및 큐를 사용한 탐색 후보 관리
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				//[i][j] 가 1이고 visited가 false인 자리 탐색
				if(M[i][j] == 1 && visited[i][j] == false) {
					//첫 번째 탐색 후보 생성
					//visited 변수 갱신
					Queue<int[]> q = new LinkedList<>();
					q.add(new int[]{i, j});
					visited[i][j] = true;
					
					while(!q.isEmpty()) {
						//poll = 큐 첫번째 값을 반환하고 제거
						int[] current = q.poll();
						
						//상,하,우,좌 탐색
						for(int k=0;k<4;k++) {
							int nextX = current[0] + dx[k];
							int nextY = current[1] + dy[k];
							//탐색하는 4방 좌표가 범위를 벗어나는지 아닌지
							if(nextX >= 0 && nextX < N && nextY >= 0 && nextY < N) {
								//새롭게 4방 탐색한 좌표가 조건에 해당하는지
								if(M[nextX][nextY] == 1 && visited[nextX][nextY] == false) {
									//새롭게 탐색한 좌표들도 조건에 해당한다면 탐색후보에 추가한다.
									q.add(new int[]{nextX, nextY});
									visited[nextX][nextY] = true;
								}
							}
						}
					}
					//탐색이 끝나면 count++;
					count++;
				}
			}
		}
		System.out.println(count);
	}
}

구름톤 챌린지 통증 (2)

[시행 착오]

아래 코드는 처음에 제출한 오답코드이다. 처음엔 간단한 문제겠구나 하고 풀었다가 테스트 케이스에서 오답을 만나고 내가 뭘 잘못했을까 고민해봤다. 무조건 N을 큰 수부터 빼는게 중요한것이 아니고 결국은 N==0이 되는것이 가장 중요하다는것을 깨달았다. 머리로는 대충 알겠지만 도저히 스스로 풀 수가 없었다. 슬슬 모든 문제들이 풀이를 보지 않고는 풀수가 없는 단계까지 왔다. 나의 한계를 만난것이다. 그래서 풀이를 보며 코드 한 라인, 한 라인 나아가며 뜯어본 결과 이해는 됬으나 스스로 그 풀이를 작성할 수가 없어서 참고해가며 풀었다. 배낀수준이지만 이렇게라도 하면 실력이 늘것이라고 생각한다. 

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		Integer N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine(), " ");
		Integer A = Integer.parseInt(st.nextToken());
		Integer B = Integer.parseInt(st.nextToken());
		int count = 0;
		boolean flag = true;
		while(flag) {
			if(N-B>=0) {
				N-=B;
				count++;
				flag = true;
				continue;
			} else {
				flag = false;
			}
			if(N-A>=0) {
				N-=A;
				count++;
				flag = true;
			} else {
				flag = false;
			}
		}
		if(N>0){
			count=-1;
		}
		System.out.println(N);
		System.out.println(count);
	}
}

[정답 코드]

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		Integer N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine(), " ");
		Integer A = Integer.parseInt(st.nextToken());
		Integer B = Integer.parseInt(st.nextToken());
		
		int[] dp = new int[N+1];
		
		//풀이에서는 MAX_VALUE로 초기화 했다. MAX_VALUE 가 아니라 N보다 큰값이면 다 가능하지 않을까 생각한다.
		for(int i=0;i<=N;i++) {
			dp[i] = Integer.MAX_VALUE;
		}
		dp[0] = 0;
		
		for(int i=0;i<=N;i++) {
			if(i-A>=0 && dp[i-A] != Integer.MAX_VALUE) {
				dp[i] = Math.min(dp[i], dp[i-A] + 1);
			}
			//N-A 를 했을때보다 횟수가 더 적을경우 N-B로 한것을 선택한다.
			if(i-B>=0 && dp[i-B] != Integer.MAX_VALUE) {
				dp[i] = Math.min(dp[i], dp[i-B] + 1);
			}
		}
		
		//for문 끝까지 돌렸을때 dp[N] 값이 여전히 MAX_VALUE라면 -1을 출력한다.
		System.out.println(dp[N] != Integer.MAX_VALUE ? dp[N] : -1);
	}
}

구름톤 챌린지 GameJam

[느낀점]

결국 이 문제도 풀이를 보며 풀었다. 풀이를 보지 않고는 나는 도저히 풀 수 없는 레벨이였다. 처음에 이 문제를 풀었을 때는 코드가 현재 정답코드의 2배이상이였다. static 매서드로 함수를 만들어서 풀 생각을 못해서 각 goorm 과 player의 게임 을 2번 진행해서 2배가 되버린것이다. 풀이를 참고해가며 문제를 다 작성하고 제출을 했는데 컴파일 오류가 계속나는 것이다. 그래서 chatgpt에 물어보고 구글링을 1시간넘게 계속했다. chatgpt도 문제가 없다고 말해서 이유를 못찾다가 알고보니 매서드를 만들어서 쓰려면 static 으로 만들어야했는데 나는 public static void main 안에 다 담아버려서 그랬던거였다. 아래는 정답 코드이다.

[정답코드]

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());

        //goorm과 player의 시작 위치 생성
        st = new StringTokenizer(br.readLine(), " ");
        int[] goormPos = {Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1};
        //bolean 배열은 기본적으로 false로 초기화된다
        boolean[][] goormVisited = new boolean[N][N];
        st = new StringTokenizer(br.readLine(), " ");
        int[] playerPos = {Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1};
        boolean[][] playerVisited = new boolean[N][N];


        //보드판 생성
        String[][] board = new String[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                board[i][j] = st.nextToken();
            }
        }
        int goormScore = move(goormPos, goormVisited, 1, board, N);
        int playerScore = move(playerPos, playerVisited, 1, board, N);

        if (goormScore > playerScore) {
            System.out.println("goorm " + goormScore);
        } else if (goormScore < playerScore) {
            System.out.println("player " + playerScore);
        }
        
    }

        //dx/dy 기법을 사용해 행렬에서 방향을 관리, 문제가 문자열형태로 주기때문에 map을 사용

    static HashMap<String, int[]> directions = new HashMap<String, int[]>() {
        {
            put("U", new int[]{-1, 0});
            put("D", new int[]{1, 0});
            put("L", new int[]{0, -1});
            put("R", new int[]{0, 1});
        }
    };


        //좌표에서 이동을 하다 보드판을 넘어갔을 경우 반대편으로 넘어가는 함수
        static int setPos(int a,int N) {
            if (a == -1) return N - 1;
            if(a == N) return 0;
            return a;
        }

        //게임을 진행하다 종료됬을때의 점수를 return 해주는 함수
        static int move(int[] pos, boolean[][] visited, int score, String[][] board, int N) {

            //말의 위치
            int x = pos[0];
            int y = pos[1];
            //방문한 위치는 true로 전환
            visited[x][y] = true;
            //score는 초기에 1점

            boolean flag = true;
            //flag가 false가 되면 while문 종료
            while(flag) {
                String command = board[x][y];
                //command의 첫번째 문자
                int distance = Integer.parseInt(command.substring(0, command.length() - 1));
                //command의 두번째 문자
                String direction = command.substring(command.length() - 1);
                //distance만큼 direction 방향으로 이동
                for(int i=0;i<distance;i++) {
                    //이 부분이 약간 이해가 헷갈린다
                    x+=directions.get(direction)[0];
                    y+=directions.get(direction)[1];
                    x = setPos(x, N);
                    y = setPos(y, N);

                    if(!visited[x][y]){
                        visited[x][y] = true;
                        score++;
                    } else {
                        flag = false;
                        break;
                    }
                }
            }
            return score;
        }

}

구름톤 챌린지 폭탄 구현하기(2)

[느낀점]

7일차에 풀었던 8방탐색문제보다 쉬운버전인 4방탐색문제다. 8방탐색을 한번 풀어서 그런걸까 더 쉽게 느껴졌다. 하지만 여전히 코드는 depth가 깊어 스마트하지 못한 코드같다. 완전탐색문제를 dx/dy 테크닉으로 풀어야 될것같은데 여전히 어려워서 if문 도배로 해버렸다.

[결과 코드]

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		String[][] map = new String[N][N];
		int[][] score = new int[N][N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0;j<N;j++) {
				map[i][j] = st.nextToken();
				score[i][j] = 0;
			}
		}
		
		int max = 0;
		for(int i=0;i<K;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int y = Integer.parseInt(st.nextToken()) - 1;
			int x = Integer.parseInt(st.nextToken()) - 1;
			if(y-1>=0){
				if(map[y-1][x].equals("@")){
					score[y-1][x]+=2;
				} else if (map[y-1][x].equals("0")){
					score[y-1][x]++;
				}
			}
			if(y+1<N){
				if(map[y+1][x].equals("@")){
					score[y+1][x]+=2;
				} else if (map[y+1][x].equals("0")){
					score[y+1][x]++;
				}
			}
			if(x-1>=0){
				if(map[y][x-1].equals("@")){
					score[y][x-1]+=2;
				} else if (map[y][x-1].equals("0")){
					score[y][x-1]++;
				}
			}
			if(x+1<N){
				if(map[y][x+1].equals("@")){
					score[y][x+1]+=2;
				} else if (map[y][x+1].equals("0")){
					score[y][x+1]++;
				}
			}
			if(map[y][x].equals("@")){
				score[y][x]+=2;
			} else if (map[y][x].equals("0")) {
				score[y][x]++;
			}
		}
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(score[i][j]>=max) {
					max=score[i][j];
				}
			}
		}
		System.out.println(max);
		
	}
}