개발자 아지트

https://school.programmers.co.kr/learn/courses/30/lessons/68644?language=java

문제설명

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요.

문제 해결 방법

주어진 배열에서 각각 다른인덱스의 요소를 뽑아서 합을 구한후 해쉬셋에 추가

해쉬셋을 사용하여 중복제거함

코드 구현

import java.util.HashSet;

class Solution {
    
    public static HashSet<Integer> set1 = new HashSet<Integer>();
    public int[] solution(int[] numbers) {
        int[] answer = {};
        
        for(int i = 0; i < numbers.length; i++){
            for(int j = 0; j< numbers.length; j++){
                if(i == j){
                    continue;
                }
                
                int sum = numbers[i] + numbers[j];
                set1.add(sum);
                
            }
        }
        
       return set1.stream().sorted().mapToInt(Integer::intValue).toArray();
        
        //해쉬셋을 stream으로 변환후, 오름차순으로 정렬한다. 
        // 그 후 set1의 Integer객체들을 int형으로 변환해주고, 배열로 변환한다. 
    }
}

시간/공간 복잡도

O(N^2)

최적화 및 개선

따로 하지않음

어려웠던 점

문법에 익숙하지 않은점

https://www.acmicpc.net/problem/2667

문제설명

지도에서  현재 자신이 있는 곳(집)에서 집이 상하좌우 중 어느 한 곳이라도 연속이 되면 단지로 판단하고, 단지의 개수, 단지에 속한 집의 개수를 세아려서 오름차순으로 정렬하여 한줄에 하나씩 출력한다. 

문제 해결 방법

BFS로 문제를 풀었다. 

코드 구현

import java.io.InputStreamReader;
import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
	public static int N;
	public static int cnt = 0;
	public static int totalCnt = 0;
	public static int[][] graph;
	public static int[] dx = {1, -1, 0, 0};
	public static int[] dy = {0, 0, 1, -1};
	public static String A="";
	public static int[] sortt;

	public static ArrayList<Integer> list = new ArrayList<>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());
		
		graph = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			Arrays.fill(graph[i], 0);
		}
		
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			for(int j = 0; j < N; j++) {
				graph[i][j] = Character.getNumericValue(str.charAt(j));
			}
		}
		for(int i = 0; i<N; i++) {
			for(int j = 0; j<N; j++) {
				BFS(i, j);
				cnt=0;
			}
		}
		
		System.out.println(totalCnt);
		
		Collections.sort(list);
			
		for(Object a : list) {
			System.out.println(a);
		}
		
	}
	
	public static void BFS(int start1, int start2) {
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(start1, start2));
		cnt = 0;
		
		while(!q.isEmpty()) {
			Point p = q.poll();
			
			if(graph[p.x][p.y]==1) {
				graph[p.x][p.y] = 9;
				cnt+=1;
			}
			
			for(int i = 0; i < 4; i++) {
				int x = p.x + dx[i];
				int y = p.y + dy[i];
				
				
				if(x < 0 || y < 0 || x >= N || y >= N) {
					continue;
				}
				
				if(graph[p.x][p.y]==0) {
					if(graph[x][y]==1) {
					}
				}
				
				
				if(graph[x][y]==1 && graph[p.x][p.y]!=0) {
					q.add(new Point(x, y));
					graph[x][y] = 9;
					cnt += 1;
				}
			}
			
		}
		
		if (cnt!=0) {
			totalCnt+=1;=
			list.add(cnt);
		}
	}
}

시간/공간 복잡도

O(N^2)

최적화 및 개선

따로 하지않음

어려웠던 점

처음에 ArrayList 사용할 생각을 못했다.
문자열에 각 단지의 개수를 추가한 후, 출력할 때 문자 하나하나 CharAt()으로 잘라서 출력했더니,
단지의 수가 9가 넘는 것들(두자리 수)의 값을 출력해야할 상황에는 다 런타임 에러가 났다. 

ArrayList가 답이다,, 이것을 이용하면 Collections를 이용해서  sort도 굉장히 편하게 할 수 있다.. 

버티지 말자~ 모르면 찾아보자 

https://www.acmicpc.net/problem/2606

문제설명

컴퓨터는 네트워크를 통해 연결되어있다. (이것을 읽으면 딱 그래프가 연상된다)

1번 컴퓨터가 웜바이러스가 걸렸고, 이 컴퓨터와 네트워크를 통해 연결되었다면, 모두 바이러스에 걸리게된다. 

이때, 1번 컴퓨터를 통해 웜바이러스에 걸린 컴퓨터의 대수는?

문제 해결 방법

BFS를 이용하였고, 큐를 통해 구현하였다. 

코드 구현

import java.io.BufferedWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
	public static int N, M;
	public static int cnt = 0;
	public static boolean[] visited;
	public static int[][] graph;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		visited = new boolean[N];
		graph = new int[N][N];
		
		Arrays.fill(visited, false);
		for(int i = 0; i < N; i++) {
			Arrays.fill(graph[i], 0);
		}
		
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph[a - 1][b - 1] = 1;
			graph[b - 1][a - 1] = 1;
		}
		bfs(0);
		System.out.println(cnt);
		
	}
	
	public static void bfs(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(start);
		
		while(!q.isEmpty()) {
			int nodeIndex = q.poll();
			
			
			if(!visited[nodeIndex]) {
				visited[nodeIndex]= true;
			}
			
			for(int i = 0; i < N; i++) {
				if(graph[nodeIndex][i] == 1 && !visited[i]) {
					visited[i] = true;
					cnt+=1;
					q.offer(i);
				}
			}
		}
	}
}

시간/공간 복잡도

O(N^2)

최적화 및 개선

따로 하지않음

어려웠던 점

아직 살짝 문법적으로 헷깔리는점이 어려울뿐 ㅎㅎ

https://www.acmicpc.net/problem/2178

문제설명

목적지를 향해 미로를 탐색하여 이동할 때 지나야 하는 최소 칸수를 구한다. 

문제 해결 방법

BFS로 풀었다. 

코드 구현

import java.io.BufferedReader;
import java.awt.Point;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	public static int N, M;
	public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {0, -1, 0, 1};
	public static int[][] graph;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		//1,1에서 출발 
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		graph = new int[N][M];
		
		for(int i = 0; i<N; i++) {
			Arrays.fill(graph[i], 0);
		}
		
		//N, M 위치로 이동
		
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			for(int j = 0; j < M; j++) {
				graph[i][j] = Character.getNumericValue(str.charAt(j));
			}
		}
		
		bfs();
		System.out.println(graph[N-1][M-1]);
		// BFS 

	}
	
	public static void bfs() {
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(0,0));
		while(!q.isEmpty()) {
			Point p = q.poll();
			
			for(int i = 0; i < 4; i++) {
				int x = p.x + dx[i];
				int y = p.y + dy[i];
				if(x<0 || y<0 || x>=N || y>=M) {
					continue;
				}
				if(graph[x][y] == 1) {
					q.add(new Point(x, y));
					graph[x][y]=graph[p.x][p.y]+1;
				}

			}
		}	
	}
}

시간/공간 복잡도

O(N^2)

최적화 및 개선

하지않음 

어려웠던 점

좌표를 어떻게 저장해야할까 고민을 많이 하다가 

구글링해서 Point를 사용하여 문제를 해결했다. 

https://www.acmicpc.net/problem/1260

문제설명

단순 DFS, BFS 구현 문제이다!

문제 해결 방법

DFS는 스택으로, BFS는 큐로 문제를 풀었다. !

코드 구현

package Mar0304;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class P_1260 {
	public static int N, M, V;
	public static boolean[] visited;
	public static int[][] graph;
	
	public static void main(String[] args) throws Exception {
		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());
		V = Integer.parseInt(st.nextToken());
		
		visited = new boolean[N];
		graph = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			visited[i]=false;
			Arrays.fill(graph[i], 0);
		}
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph[a-1][b-1] = 1;
			graph[b-1][a-1] = 1;
		}
		
		DFS(V-1);
		
		Arrays.fill(visited, false);
		System.out.println("");
		BFS(V-1);
		
		
	}
	
	// DFS
	public static void DFS(int start) {
		//visited[start] = true;
		Stack<Integer> stack = new Stack<>();
		stack.push(start);
		
		
		while(!stack.isEmpty()) {
			int current = stack.pop();
			
			if(!visited[current]) {
				System.out.print((current + 1) + " ");
				visited[current] = true;
				
			}
			
			for(int i = N - 1; i >= 0; i--) {
				if(!visited[i]) {
					if(graph[current][i] == 1) {
						stack.push(i);
					}
				}
			}

		}
		
	}
	
	// BFS
	public static void BFS(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		//visited[start] = true;
		q.offer(start);
		
		while(!q.isEmpty()) {
			int nodeIndex = q.poll();
			
			if(!visited[nodeIndex]) {
				System.out.print((nodeIndex + 1) + " ");
				visited[nodeIndex] = true;
			}
			
			for(int i = 0; i < N; i++) {
				if(graph[nodeIndex][i]==1 && !visited[i]) {
					q.offer(i);
				}
			}
			
		}
		
		
	}
}

시간/공간 복잡도

O(N^2)

최적화 및 개선

하지않음

어려웠던 점

문법이 손에 안익어서 어려웠다.