아찌방 하우스

https://school.programmers.co.kr/learn/courses/30/lessons/49994

풀이 - 나의 생각

1 -> 2 로 넘어갈 경우

방문 길이는 체크 되지만

2-> 1 방향으로 가는 경우는

체크 되지 않아야 한다.

기존에 하던 것처럼 2차원 배열로 방문처리 할 경우

위의 경우는 가능하지만

3 ->2나, 4->2, 5->2 같은 경우

방문 길이가 늘어나야 하지만

2가 이미 방문처리 되어 늘어나지 않는다.

그걸 어떻게 코딩할까 고민을 하다가

방문처리를 3차원으로 하면 되겠다고 생각했다.

[방향][맵][맵] 이런 식으로해서

들어온 방향 + 반대 방향을 방문 처리 해주면

그 외에 방향에서 들어오는 건 방문 길이가 추가 되게 할 수 있다!!

코드

import java.util.*;

class Solution {
    public int solution(String dirs) {
        int answer = 0;
        boolean[][][] visited = new boolean[4][11][11];
        int x = 5, y = 5;
        
        for(int i = 0; i < dirs.length(); i++){
            switch(dirs.charAt(i)){
                case 'U':
                        if(x-1 < 0) continue;
                        x--;
                        if(!visited[0][x][y]){
                            answer++;
                            visited[0][x][y] = true;
                            visited[1][x+1][y] = true;
                        }
                        break;
                case 'D':
                        if(x+1 >= 11) continue;
                        x++;
                        if(!visited[1][x][y]){
                            answer++;
                            visited[1][x][y] = true;
                            visited[0][x-1][y] = true;
                        }
                        break;
                case 'L':
                        if(y-1 < 0) continue;
                        y--;
                        if(!visited[2][x][y]){
                            answer++;
                            visited[2][x][y] = true;
                            visited[3][x][y+1] = true;
                        }
                        break;
                case 'R':
                        if(y+1 >= 11) continue;
                        y++;
                        if(!visited[3][x][y]){
                            answer++;
                            visited[3][x][y] = true;
                            visited[2][x][y-1] = true;
                        }
                        break;
            }
        }
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/92335

풀이 - 나의 생각

1. 주어진 int n을 K진수로 바꾸기

2. 조건에 맞춰 숫자 자르기

3. 그 숫자가 소수인지 확인하기

1은

Integer.toString(int n, int k)

-> n을 k진수로 변환하여 String 형으로 반환한다.

2는

String.split("0+")

-> 0 또는 연속된 0을 기준으로 문자열을 분환해줌

3은

에라토스테네스의 체를 활용했는데

원래는 n까지 소수의 개수를 찾는 방식이지만

이번에는 n이 소수인지 아닌지 판별하는 방식으로 사용했다.

코드

import java.util.*;

class Solution {
    public int solution(int n, int k) {
        String converted = Integer.toString(n, k);
        String[] nums = converted.split("0+"); // 0 또는 연속된 00을 기준으로 분할
        
        int answer = 0;
        
        for(String s : nums){
            if(isPrimeNumber(s)){
                answer++;
            }
        }
        
        
        return answer;
    }
    
    public static boolean isPrimeNumber(String s){ //에라토스테네스의 체 활용
        long num = Long.parseLong(s);
        if(num <= 1){
            return false;
        }
        
        for(int i = 2; i <= Math.sqrt(num); i++){
            if(num % i == 0){
                return false;
            }
        }
        
        return true;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/131701

풀이 - 나의 생각

이 문제를 풀기 위한 포인트!!!!

1. 중복 제거

2. 한 바퀴 돌리기

1. 중복 제거

Set 쓰면 해결!!

2. 한 바퀴 돌리기

이중 for문 쓰면서 해결했는데

결국에는 주어진 배열을 넘어가면

처음으로 넘어가는 게 중요

처음에는

index = i+j >= arr.length ? (i+j)-arr.length : i+j

이런 식으로 했는데

index = (i+j)%arr.length

이렇게 하면 더 간단하게 해결 할 수 있었다.

테스트 결과 속도도 더 빨랐다. ( 조건 검사를 할 필요가 없으니까)

이외.....

처음에는 더해지는 값들을 저장하기 위해

반복문 안에서

int형 변수 하나를 선언해서

값을 더해가면서 Set에 저장했는데

그것 보다는

반복문 밖에서 int형 배열을 선언해서

값을 더해가면서 저장하는게

속도가 더 빨랐다.

아무래도 반복문이 돌아갈때마다

변수를 선언 및 초기화 시키는데

메모리가 할당되는 시간이 발생하기 때문으로 파악된다.

코드

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        Set<Integer> nums = new HashSet<>();
        int len = elements.length; // .length() 가 계속 사용되기 때문에 차라리 변수를 하나 선언
        int[] sums = new int[len]; // 연속으로 더할 값을 저장하기 위한 배열
        
        for(int i = 0; i < len; i++){
            for(int j = 0; j < len; j++){
                sums[j] += elements[(i+j)%len]; // 주어진 배열의 범위를 넘어가지 않으면서 돌게
                nums.add(sums[j]);
            }
        }
        return nums.size(); // Set은 중복 제거가 알아서 되기 때문에, 저장된 Set의 길이가 나올 수 있는 모든 합의 경우의 수다
    }
}

SKT 코테

- 난이도 : 생각보다 엄청 어렵지는 않았다.

- 본인이 잘 본건 아니다. 4문 중 2문만 풀었고, 1문제는 풀다가 시간이 끝나버렸다.

- 보통 2개는 푸는 거 같고 3개는 좀 있고, 4개 풀었다는 사람은 못봤다.

- 전형적인 코테 난이도 인 것 같다.

- 1, 2 문제는 쉽고, 3, 4 가 좀 어렵고

데브매칭(PCCP) - JAVA Lv2 580 

- 보통 Lv3 부터 우대로 쳐주는 기업들이 있다는데 20점 차이로 못 받아서 좀 아쉽다.

- SKT 코테랑 비슷한 난이도인 거 같다.

ps. 이걸로 취업할 생각은 안 했는데 그래도 탈락 문자 오는 거 조금 신경 쓰인다....

- 둘 다 프로그래머스를 통해 테스트 진행했다.

- IDE 없으니까 조금 불편하긴 했는데 하다보니 익숙해지는 것 같다.

- 결국 관건은 1, 2 문을 50분 ~ 1시간 이내에 풀고, 3, 4 번 중 하나를 1시간 이내에 풀어내야 하는 것 같다.

- 그러면 백준 기준 골드 상위 문제를 1시간 이내에 풀어야 한다는 건데, 이건 당장 해결할 수 있는 문제는 아니고 계속 알고리즘을 풀어갈 수 밖에 없는 거 같다.

ps. 백준 골드 1 찍었다.

잘난건 아니지만 기분은 좋다 ㅎㅎ

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

문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.

크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)

출력

돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.

코드

BFS 풀이 방식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class JUN12886 {
    static int sum;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        sum = A + B + C;
        visited = new boolean[sum+1][sum+1];

        if(sum % 3 != 0){
            System.out.println("0");
            return;
        }

        Queue<int[]> q = new ArrayDeque<>();

        q.offer(new int[]{A,B,C});
        visited[A][B] = true;

        boolean flag = false;
        while (!q.isEmpty()){
            int[] now = q.poll();
            int a = now[0];
            int b = now[1];
            int c = now[2];

            if(a == b && b == c) {
                flag = true;
                break;
            }

            for (int i = 0; i < 2; i++) {
                for (int j = i+1; j < 3; j++) {
                    if(now[i] == now[j]) continue;
                    int t1 = now[i] > now[j]? now[i] - now[j] : now[i] + now[i];
                    int t2 = now[i] > now[j]? now[j] + now[j] : now[j] - now[i];
                    if(!visited[t1][t2]){
                        visited[t1][t2] = true;
                        q.offer(new int[]{t1, t2 ,sum - (t1 + t2)});
                    }
                }
            }
        }

        System.out.println(flag?"1":"0");
    }
}

DFS 풀이 방식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int sum;
    static int[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        sum = A + B + C;
        visited = new int[sum+1][sum+1];

        if(sum % 3 != 0){
            System.out.println("0");
        }else {
            dfs(A,B);
            System.out.println(visited[sum/3][sum/3]);
        }
    }

    public static void dfs(int a, int b){
        if(visited[a][b] == 1) return;

        visited[a][b] = 1;

        int[] now = {a, b, sum - (a+b)};
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if(now[i] < now[j]) {
                    int[] temp = {a, b, sum - (a + b)};
                    temp[i] += now[i];
                    temp[j] -= now[i];
                    dfs(temp[0], temp[1]);
                }
            }
        }
    }
}

풀이

 A + B + C = sum 

이 세가지 돌 그룹의 합은

돌을 이동 시켜도 변하지 않는다.

또한

C = sum - ( A + B)

와 같이 

한 돌 그룹의 값은

sum 값에서 나머지 두 그룹의 합을 뺀 값과 같다

 두 그룹을 비교하다 보면

결국 반복된다.

-> 중복 처리 필요

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

코드

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

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String args[]) throws IOException
	{
		/* 11653 소인수분해
		 * 정수 입력받아서 소인수 분해
		   */
		
		int n = sc.nextInt();
		
		for(int i = 2; i <= n;) //소인수는 1보다 큽니다, 그래서 2부터 시작
		{
			if(n%i == 0) // 나머지가 0이면 출력
			{
				n/=i;
				System.out.println(i);
			}
			else
			{
				i++;
			}
		}
			
	}
}ll

풀이

https://fall-in-dream.tistory.com/22

위의 문제랑 비슷한데

이 문제는 그냥 출략하면 되서 더 단순하다.

문제

정수 배열 array와 정수 n이 매개변수로 주어질 때, array에 들어있는 정수 중 n과 가장 가까운 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

제한사항

• 1 ≤ array의 길이 ≤ 100
• 1 ≤ array의 원소 ≤ 100
• 1 ≤ n ≤ 100
• 가장 가까운 수가 여러 개일 경우 더 작은 수를 return 합니다.

입출력 예

입출력 예

입출력 예 설명

입출력 예 #1

• 3, 10, 28 중 20과 가장 가까운 수는 28입니다.

입출력 예 #2

• 10, 11, 12 중 13과 가장 가까운 수는 12입니다.

코드

class Solution {
    public int solution(int[] array, int n) {
        
        int answer = 1000;
        int sub = 100; //n과의 거리가 현재 가장 가까운 값
        int temp = 0;
        
        for(int i = 0; i < array.length; i++)
        {
            temp = array[i] - n; //n과의 거리
            if(temp < 0) //음수이면 양수로 바꾸기 위해
            {
                temp*=-1; // Math.abs(arr[i] - i); 로 대체 가능합니다.
            }
            
        	if(temp < sub) // 현재 n과의 거리가 기존의 거리보다 가까우면
        	{
        		sub = temp;
        		answer = array[i]; // n과 가까운 값 저장
        	}
            else if(temp == sub && answer > array[i]) // n과의 거리가 동일할 경우 더 작은 값을 저장
            {
                sub = temp;
                answer = array[i];
            }
        }
        return answer;
    }
}

풀이

정렬 쓰기 싫었고, Math 쓰기 싫어서 이렇게 했습니다.

풀이 방법은 주석을 보시면 아시겠지만

주어진 정수(n)과 가장 가까운 수를 찾아야합니다.

그렇기때문에

배열(array)에 저장된 값을 주어진 정수(n)과 뺀 값이

sub(현재 가장 가까운 거리)보다 작으면

그 값을 sub으로 저장 및 비교하면서 

가장 가까이 있는 수를 찾아줍니다.

이때 주의점 2가지

1. n보다 배열에 작으면(arr[i]  <  n)

뺄때 음수가 나오니까 양수로 바꿔줍시다.

(-2 보다 1이 더 가깝지만, -2 < 1 이기 때문에)

2. 가장 가까운 수가 여러개 일때, 더 작은 수를 출력해야 합니다.

해결 방안

1. 음수라면 -1을 곱해서 양수로 만들어줍니다.

	temp = array[i] - n; //n과의 거리
	if(temp < 0) //음수이면 양수로 바꾸기 위해
	{
		temp*=-1; // Math.abs(arr[i] - i); 로 대체 가능합니다.
	}

2. sub이 동일할때 더 작은 수를 저장합니다.

            if(temp == sub && answer > array[i]) // n과의 거리가 동일할 경우 더 작은 값을 저장
            {
                sub = temp;
                answer = array[i];
            }

문제

문제 설명

제한사항

제한사항

• 2 ≤ n ≤ 10,000

입출력 예

입출력 예

입출력 예 설명

입출력 예 #1

• 12를 소인수분해하면 2 * 2 * 3 입니다. 따라서 [2, 3]을 return합니다.

입출력 예 #2

• 17은 소수입니다. 따라서 [17]을 return 해야 합니다.

입출력 예 #3

• 420을 소인수분해하면 2 * 2 * 3 * 5 * 7 입니다. 따라서 [2, 3, 5, 7]을 return합니다.

코드

import java.util.*;

class Solution {
    public int[] solution(int n) {
        int[] answer;
        HashMap<Integer, Integer> map = new HashMap<>();
        int index = 0;
        
        for(int i = 2; i <= n;) //소인수는 1보다 크기에 2부터 시작
        {
        	if(n%i==0) // 나눠지면 인수라는 것
        	{
        		map.put(i, i); //해시맵에 저장
        		n/=i; // n을 소인수로 나누기
        	}
        	else // 나눠지지 않으면 i++;
        	{
        		i++;
        	}
        	
        }
        
        answer = new int[map.size()]; //해시맵 크기만큼
        for(Integer i : map.keySet()) //배열에 값 넣기
        {
        	answer[index] = map.get(i);
        	index++;
        }
        Arrays.sort(answer); //해시맵은 정렬된 상태가 아니기 때문에 정렬
        return answer;
    }
}

풀이

소인수를 구하기 위해서는

소인수분해를 해야하고

소인수분해는

이런 과정을 통해 이루어집니다!

자! 여기서 우리는 중복된 수를 제거해야합니다.

배열을 쓰면서도 할 수 있겠지만

저는 자동으로 중복제거를 해주는 HashMap이 좋겠다 싶어서

HashMap을 이용해 봤습니다 ㅎㅎ

12(n) 가 소수(i)로 나눴을 때 나머지가 0 이면

그 소수가 소인수가 되니까 map 에 put 하고

나머지가 0이 아니라면 다음 소수로 넘어갑니다.

그리고 그렇게 HashMap에 저장된 값을 배열에 저장하는 이유는

HashMap은 정렬된 것처럼 보이지만 사실은 정렬되어 있지 않기 때문입니다!!

그래서 배열에 값을 넣어준 후 정렬시켜 준 것이죠 ㅎㅎ