Programmers #17

이강용·2023년 5월 21일
0

Programmers

목록 보기
16/58

분수의 덧셈

📑 문1) 첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

제한사항

  • 0 <numer1, denom1, numer2, denom2 < 1,000

입출력 예

numer1denom1numer2denom2result
1234[5,4]
9213[29,6]

입출력 예 설명

  • 1 / 2 + 3 / 4 = 5 / 4입니다. 따라서 [5, 4]를 return 합니다.

  • 9 / 2 + 1 / 3 = 29 / 6입니다. 따라서 [29, 6]을 return 합니다.

나의 풀이

class Solution {
     public static int[] solution(int numer1, int denom1, int numer2, int denom2) {
        int commonDenominator = denom1 * denom2;
        int sumNumerator = (numer1 * denom2) + (numer2 * denom1);
        int gcd = findGCD(sumNumerator, commonDenominator);

        return new int[] {sumNumerator / gcd, commonDenominator / gcd};
    }

    public static int findGCD(int a, int b) {
        if (b == 0) {
            return a;
        }
        return findGCD(b, a % b);
    }
}

나의 생각

기약분수를 구하라 와 같은 문제의 조건이 주어지면 최대공약수를 이용해서 문제에 접근하면된다. 이번 문제 역시, 분자 sumNumerator , 분모 commonDenominator 를 구한 뒤, 분자, 분모에 최대공약수를 나눠주면 해결되는 문제였다.

안전지대

📑 문2) 다음 그림과 같이 지뢰가 있는 지역과 지뢰에 인접한 위, 아래, 좌, 우 대각선 칸을 모두 위험지역으로 분류합니다.

지뢰는 2차원 배열 board에 1로 표시되어 있고 board에는 지뢰가 매설 된 지역 1과, 지뢰가 없는 지역 0만 존재합니다.
지뢰가 매설된 지역의 지도 board가 매개변수로 주어질 때, 안전한 지역의 칸 수를 return하도록 solution 함수를 완성해주세요.

제한사항

  • board는 n * n 배열입니다.
  • 1 ≤ n ≤ 100
  • 지뢰는 1로 표시되어 있습니다.
  • oard에는 지뢰가 있는 지역 1과 지뢰가 없는 지역 0만 존재합니다.

입출력 예

boardresult
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 0, 0]]16
[[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 1, 1, 0], [0, 0, 0, 0, 0]]13
[[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]]0

입출력 예 설명

  • (3, 2)에 지뢰가 있으므로 지뢰가 있는 지역과 지뢰와 인접한 위, 아래, 좌, 우, 대각선 총 8칸은 위험지역입니다. 따라서 16을 return합니다.

  • (3, 2), (3, 3)에 지뢰가 있으므로 지뢰가 있는 지역과 지뢰와 인접한 위, 아래, 좌, 우, 대각선은 위험지역입니다. 따라서 위험지역을 제외한 칸 수 13을 return합니다.

  • 모든 지역에 지뢰가 있으므로 안전지역은 없습니다. 따라서 0을 return합니다.

나의 풀이

class Solution {
    public int solution(int[][] board) {
       int answer = 0;

        int[] dx = {-1, 0, 1, 0, -1, 1, -1, 1};
        int[] dy = {0, 1, 0, -1, -1, -1, 1, 1};

        int length = board.length;

        boolean[][] checkBoard = new boolean[length][length];

        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                boolean flag = true;

                for (int k = 0; k < 8; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (board[i][j] == 1) {
                        checkBoard[i][j] = true;
                    }

                    if (nx >= 0 && nx < length && ny >= 0 && ny < length && board[nx][ny] == 1) {
                        checkBoard[i][j] = true;
                    }
                }
            }
        }

        for (int i = 0; i < checkBoard.length; i++) {
            for (int j = 0; j < checkBoard.length; j++) {
                if (!checkBoard[i][j]) {
                    answer++;
                }
            }
        }


        return answer;
    }
}

나의 풀이

핵심은 dx,dy로 2차원 Grid에서 주변 8개의 셀 ( 북, 동, 남, 서, 북동, 북서, 남동, 남서 )을 탐색하는 방향 벡터이다.

checkBoard는 board와 같은 크기의 boolean 타입 2차원 배열로, 초기에는 모든 값이 false 로 설정된다. 특정 조건 ( 지뢰, 지뢰 인근 셀)에 대해 true 값을 설정한다.

첫 번째 중천된 for 반복문은 board의 모든 셀을 순회한다. 각 셀에 대해, board[i][j]값이 1이면 checkBoard[i][j]를 true로 설정, 그리고 그 셀 주변 8개의 셀을 살펴보고, 주변 셀의 값이 1이면 checkBoard[i][j]를 true로 설정

두 번째 중첩된 for 반복문은 checkBoard의 모든 셀을 순회, 만약 checkBoard[i][j] 값이 false라면,answer의 값을 1 증가 시킴

겹치는 선분의 길이

📑 문3) 선분 3개가 평행하게 놓여 있습니다. 세 선분의 시작과 끝 좌표가 [[start, end], [start, end], [start, end]] 형태로 들어있는 2차원 배열 lines가 매개변수로 주어질 때, 두 개 이상의 선분이 겹치는 부분의 길이를 return 하도록 solution 함수를 완성해보세요.
lines가 [[0, 2], [-3, -1], [-2, 1]]일 때 그림으로 나타내면 다음과 같습니다.

선분이 두 개 이상 겹친 곳은 [-2, -1], [0, 1]로 길이 2만큼 겹쳐있습니다.

제한사항

  • lines의 길이 = 3
  • lines의 원소의 길이 = 2
  • 모든 선분은 길이가 1 이상입니다.
  • lines의 원소는 [a, b] 형태이며, a, b는 각각 선분의 양 끝점 입니다.
    -100 ≤ a < b ≤ 100

입출력 예

linesresult
[[0, 1], [2, 5], [3, 9]]2
[[-1, 1], [1, 3], [3, 9]]0
[[0, 5], [3, 9], [1, 10]]8

입출력 예 설명

입출력 예 #1

  • 두 번째, 세 번째 선분 [2, 5], [3, 9]가 [3, 5] 구간에 겹쳐있으므로 2를 return 합니다.

입출력 예 #2

  • 겹친 선분이 없으므로 0을 return 합니다.

입출력 예 #3

  • 첫 번째와 두 번째 선분이 [3, 5] 구간에서 겹칩니다.
  • 첫 번째와 세 번째 선분 [1, 5] 구간에서 겹칩니다.
  • 두 번째와 세 번째 선분 [3, 9] 구간에서 겹칩니다.
  • 따라서 [1, 9] 구간에 두 개 이상의 선분이 겹쳐있으므로, 8을 return 합니다.

나의 풀이

첫 시도 (잘못된 풀이)

package programmers;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;

public class OverlappingLine {
	public static int solution(int[][] lines) {
		
		List<Integer> numbers = new ArrayList<>();
        int finalNum = 0;
        
        for(int i = 0; i < lines.length; i++) {
        	for(int j = lines[i][0]; j< lines[i][1]; j++) {
        		
        		numbers.add(j);
        	    
        	}
        	
        }
        System.out.println(numbers);
        Set<Integer> set = new LinkedHashSet<>();
        Set<Integer> dupNum = new LinkedHashSet<>();
        
        for(Integer number :numbers) {
        	
        	if(!set.add(number)) {
        		dupNum.add(number);
        	}
        }
        
        List<Integer> newList = new ArrayList<>();
        for(Integer number : dupNum) {
        	newList.add(number);
        }
        System.out.println(newList);
        Collections.sort(newList);
        
        if(newList.size() == 2){
            finalNum = 0;
        } else if (newList.size() > 2){
            int firstIdx = 0;
            int lastIdx = dupNum.size() - 1;
            finalNum = newList.get(lastIdx) - newList.get(firstIdx);
        }
       
        		
        
        System.out.println(finalNum);
        
        
        
        return finalNum;
	}
	

	
	
	public static void main(String[] args) {	
		
		int[][] lines = {{0,3},{-3,-1},{-2,3}};
		solution(lines);
	}

}

나의 생각

첫번째 시도

나는 이 문제를 해결하면서 이 문제의 핵심은 중복된 값을 제거하는 것이다 라고 생각하였다. 그래서, Index를 돌며, 각 원소의 시작점과 끝점을 이용하여 for문 반복을 돌려 모든 인덱스의 원소값을 다 추출 하여 set 컬렉션에 넣어, set에 number을 대입하여, 값이 들어가지 않으면 즉, 중복된 값이 존재하면, dupNum에 중복된 값을 넣어주는 방법을 사용하였다.

하지만, 내가 잘못 생각했던 이유는 위와 같은 방법을 사용하면, 중복된 값이 선이 아닌, 점도 중복으로 포함시키기 때문에 (겹친 부위가 점으로 존재해도) 예상치 못한 값도 포함될 수 있다.

입출력 예의 테스트는 통과하지만, 제출결과 테스트 케이스 1번, 9번 반례가 존재함을 확인

두번째 시도 (정답)

import java.util.*;
class Solution {
    public int solution(int[][] lines) {
       int[] rail = new int[201];
        for (int[] line : lines) {
            for (int j = (line[0] + 100); j < (line[1] + 100); j++) {
                rail[j]++;
            }
        }

        int answer = 0;
        for (int value : rail) {
            if (value > 1) answer++;
        }
        return answer;
        
        
    }
}

나의 생각

두번째 시도

풀이법을 순서로 나열해보자.

  1. 크기가 201인 rail 배열을 선언한다.

    각 index가 특정 위치를 나타내며, 그 위치에 몇 개의 선분이 존재하는지를 나타내는 값이 저장됨

  2. 매개변수lines의 2차원 배열을 순회하는데, 각 요소는 [시작점, 끝점]의 형태를 가지며, 시작점과 끝점은 실제 위치에 100을 더한 값이다. ( 위치가 음수일 수 도 있음을 고려)
  3. 각 선분에 대해 시작점부터 끝점까지 rail 배열의 해당 index 값을 1씩 증가 시킴

    rail 배열은 각 위치에 대해 몇 개의 선분이 겹쳐 있는지를 나타냄

  4. rail 배열을 순회하며, 값이 1보다 큰 경우를 찾음

    이는 해당 위치에 2개 이상의 선분이 겹쳐 있다는 것을 의미

  5. 겹치는 선분의 수를 answer에 더하고, 이를 반환

{{0,5},{3,9},{1,10}} 이 매개변수 lines를 통해 들어오면, 해당 index의 원소값을 +1 해줌

마지막 인덱스를 순회할때 해당 원소값이 중복된 점의 개수가 되고, 그 원소의 값이 1보다 크면 2개 이상의 선분이 겹쳐있다는 것을 의미하게 되므로, 원하는 값을 추출할 수 있음

평행

📑 문4) 점 네 개의 좌표를 담은 이차원 배열 dots가 다음과 같이 매개변수로 주어집니다.

[[x1, y1], [x2, y2], [x3, y3], [x4, y4]]

주어진 네 개의 점을 두 개씩 이었을 때, 두 직선이 평행이 되는 경우가 있으면 1을 없으면 0을 return 하도록 solution 함수를 완성해보세요.

제한사항

  • dots의 길이 = 4
  • dots의 원소는 [x,y] 형태이며 x,y는 정수
    • 0 ≤ x, y ≤ 100
  • 로 다른 두개 이상의 점이 겹치는 경우는 없습니다.
  • 두 직선이 겹치는 경우(일치하는 경우)에도 1을 return 해주세요.
  • 임의의 두 점을 이은 직선이 x축 또는 y축과 평행한 경우는 주어지지 않습니다.

입출력 예

dotsresult
[[1, 4], [9, 2], [3, 8], [11, 6]]1
[[3, 5], [4, 1], [2, 4], [5, 10]]0

입출력 예 설명

입출력 예 #1

  • 점 [1, 4], [3, 8]을 잇고 [9, 2], [11, 6]를 이으면 두 선분은 평행합니다.

입출력 예 #2

  • 점을 어떻게 연결해도 평행하지 않습니다.

나의 풀이

package programmers;

public class Parallel {
	   
	 public static double findSlope(int[] dot1, int[] dot2) {
	        // 기울기 구하는 공식 : (y2 - y1) / (x2 - x1)
	        return (double) (dot2[1] - dot1[1]) / (dot2[0] - dot1[0]);
	    }

	    public static int solution(int[][] dots) {
	        int answer = 0;

	        
	        if (findSlope(dots[0], dots[1]) == findSlope(dots[2], dots[3])) {
	            return 1;
	        }

	        
	        if (findSlope(dots[0], dots[2]) == findSlope(dots[1], dots[3])) {
	            return 1;
	        }

	        
	        if (findSlope(dots[0], dots[3]) == findSlope(dots[1], dots[2])) {
	            return 1;
	        }

	        return answer;
	    }
	   
	   public static void main(String[] args) {
	      int[][] dots = {{3,5},{4,4},{8,9},{6,11}} ;
	      solution(dots);
	   }
	}

나의 생각

Level 0 막바지에 다가오니 문제가 점점 어려워지는건지, 집중을 잘 못하고 있는듯한 느낌이 많이 들고 있다. 이번 문제에서는 어렵게 생각하면 한 없이 어렵게 , 쉽게 생각하면 한 없이 쉽게 풀 수 있는 문제였던거 같다. 나 역시 반복문을 어떻게 돌려야할까. 어떻게 하면 세련되게 문제를 풀 수 있을지만 생각했지, 쉬운 문제도 마치 어렵게 푸는 그런 마법을 부린듯한 느낌이 들었다. 먼저, findSlope 기울기를 찾는 메서드 부터 보자.

 public static double findSlope(int[] dot1, int[] dot2) {
 	// 기울기 구하는 공식 : (y2 - y1) / (x2 - x1)
    return (double) (dot2[1] - dot1[1]) / (dot2[0] - dot1[0]);
 }

기울기 : 기울기 구하는 공식 : (y2 - y1) / (x2 - x1) 이다. 

public static int solution(int[][] dots) {
	int answer = 0;


    if (findSlope(dots[0], dots[1]) == findSlope(dots[2], dots[3])) {
        return 1;
    }


    if (findSlope(dots[0], dots[2]) == findSlope(dots[1], dots[3])) {
        return 1;
    }


    if (findSlope(dots[0], dots[3]) == findSlope(dots[1], dots[2])) {
        return 1;
    }

    return answer;
    }

{3,5},{4,4},{8,9},{6,11}의 네점으로 이루어진 2차원 배열이 있다고 할때, 2차원 배열을 원소 하나씩 쪼개어 생각하는 것이다.

findSlope(dots[0], dots[1]) = findSlope({3,5},{4,4})
findSlope(dots[2], dots[3]) = findSlope({8,9}, {6,11})

즉 , index[0]은, index[1], index[2], index[3] 과 (네점을 모두)비교하기 때문에, 모든 조건을 충족할 수 있다. 세 가지의 조건만 비교하면, 문제에서 주어진 제한사항은 자연스레 만족하기 때문에 쉽게 문제를 해결할 수 있다.

옹알이 (1)

📑 문5) 머쓱이는 태어난 지 6개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음을 최대 한 번씩 사용해 조합한(이어 붙인) 발음밖에 하지 못합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요.

제한사항

  • 1 ≤ babbling의 길이 ≤ 100
  • 1 ≤ babbling[i]의 길이 ≤ 15
  • babbling의 각 문자열에서 "aya", "ye", "woo", "ma"는 각각 최대 한 번씩만 등장합니다.
    • 즉, 각 문자열의 가능한 모든 부분 문자열 중에서 "aya", "ye", "woo", "ma"가 한 번씩만 등장합니다.
  • 문자열은 알파벳 소문자로만 이루어져 있습니다.

입출력 예

babbingresult
["aya", "yee", "u", "maa", "wyeoo"]1
["ayaye", "uuuma", "ye", "yemawoo", "ayaa"]3

입출력 예

입출력 예 #1

  • ["aya", "yee", "u", "maa", "wyeoo"]에서 발음할 수 있는 것은 "aya"뿐입니다. 따라서 1을 return합니다.

입출력 예 #2

  • ["ayaye", "uuuma", "ye", "yemawoo", "ayaa"]에서 발음할 수 있는 것은 "aya" + "ye" = "ayaye", "ye", "ye" + "ma" + "woo" = "yemawoo"로 3개입니다. 따라서 3을 return합니다.

유의사항

네 가지를 붙여 만들 수 있는 발음 이외에는 어떤 발음도 할 수 없는 것으로 규정합니다. 예를 들어 "woowo"는 "woo"는 발음할 수 있지만 "wo"를 발음할 수 없기 때문에 할 수 없는 발음입니다.

나의 풀이

package programmers;

import java.util.ArrayList;

public class Babbling {
	
	public static int solution(String[] babbling) {
        String[] str = {"aya","ye","woo","ma"};
        ArrayList<String> bab = new ArrayList<>();
        int cnt = 0;

        for(int i = 0; i < babbling.length; i++) {
        	bab.add(babbling[i]);
        	for(int j = 0; j < str.length; j++) {
	        	if(bab.get(i).contains(str[j])) {
	        		String replaced = bab.get(i).replace(str[j], " ");
	        		bab.set(i, replaced);
	        		if(bab.get(i).trim().isEmpty()) {
	        			cnt++;
	        		}
	        	}
        	}

        }
        
    
        return cnt;
    }
	
	
	public static void main(String[] args) {
		
		String[] babbling ={"aya", "yee", "u", "maa", "wyeoo"};	
		solution(babbling);
	}

}

클린 코드로 작성

package programmers;

public class Babbling {
	
	public static int solution(String[] babbling) {
        String[] str = {"aya","ye","woo","ma"};
        int cnt = 0;
        
        for(int i = 0; i < babbling.length; i++) {
        	for(String word :str) {
        		if(babbling[i].contains(word)){
        			babbling[i] = babbling[i].replace(word, " ");
        			if(babbling[i].trim().isEmpty()) {
        				cnt++;
        			}
        		}
        	}
        }
        return cnt;
    }
	
	
	public static void main(String[] args) {
		
		String[] babbling ={"aya", "yee", "u", "maa", "wyeoo"};	
		solution(babbling);
	}

}

나의 생각

이번 문제는, 불특정한 단어들 속에, 특정 단어가 얼마나 포함됐는가? 를 찾는 문제였다.
예를들어, String[] babbling ={"aya", "yee", "u", "maa", "wyeoo"}; 가 있을 때, 아기가 발음 할 수 있는 단어는 String[] str = {"aya","ye","woo","ma"}; 불특정한 단어 속에 아기가 발음할 수 있는 단어를 지우고 나면, " ", "e", "u", " a","w oo"가 된다.
나는 여기서 배열의 isEmpty 메서드를 활용하여 배열이 비어 있으면, cnt를 증가시켜 단어가 모두 포함됐으면 빈 배열로 존재하기 때문에 이를 검출 할 수 있겠다고 생각했다. 하지만 여기에도 문제가 있으니, 과연 " "를 빈 배열로 인식할 것인가? 테스트를 해봤지만 역시나, 빈 배열로 인식하지 않는다... 이때, 내가 사용한 trim메서드는 문자열(String)의 양 끝에 있는 공백을 제거하는 역할을 하기 때문에, 빈 배열이 존재하면 ""로 존재할 것이기 때문에 isEmpty() 메서드로 카운트를 체크할 수 있겠다고 생각

드디어 Level 0 100문제 풀기를 끝냈다. 하루에 한 문제를 꼭 풀자는 마인드로, 혹시 못풀더라도 주말에 푸는 식으로 100문제 풀기를 완료할 수 있었다. 한 걸음씩 앞으로 나아가자! 👍🏻

profile
이강용
HW + SW = 1
이전 포스트

Programmers #16

다음 포스트

Programmers #18

0개의 댓글