안드 공부를 해볼까?

1. 문제분석 기본적인 DFS 문제다. 나는 visited배열 + 재귀형식으로 구현을 했다. 단지별로 모여있다는 것은 출발점에서 DFS를 통해 탐색이 가능한 경우를 1개로 친다. 예시인 1단지를 보자. 만약 방문이 가능하다면 DFS를 실행한다. 그렇다면 해당 구역을 전부 찾았을 것 이다. 찾은 구역의 visited값을 false로 두고 다음 탐색 가능 구역을 가면 된다. 탐색이 가능하면 단지의 개수를 증가하고 ArrayList에 넣어주었다. 마지막 단지개수와 오름차순으로 정렬한 단지 값을 출력하면 된다. 2. 구현 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.ut..

1. 문제분석 빙고가 3개일 때 몇번째 입력에서 됐는지 출력하는 문제다. 빙고판은 5 * 5로 고정이니 쉽게 풀 수 있다. 빙고가 되는 조건은 간단하다. 가로, 세로, 왼쪽 대각선, 오른쪽 대각선이다. 구현에서 자세히보자. 2. 구현 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int count = 0; static int check = 0; static int[][] board = new int[5][5]; static boolean[][] checkArr = new boolean[5][5]; public static voi..

1. 문제분석 정말 쉬운 투포인터 문제다. 슬라이딩 윈도우 기법을 사용해서 연속합을 구하면 된다. 구간의 범위를 정하고 start ~ end까지의 범위를 구한다. 그 후, start와 end는 1씩 증가하고 end가 배열의 크기면 break한다. 어려운건 없으니 바로 구현을 하면 된다. 2. 구현 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStream..

1. 문제분석 주어진 크기의 종이를 각 번호에 맞게 자르는 문제다. 단순히 생각해서 종이 크기만큼의 배열을 초기화하고 문제를 해결할려고 하면 힘들 것 이다. 나는 자르는 부분의 위치를 기억하고 개수를 더하는 방식으로 해결했다. 테스트케이스 1을 보자. 10 * 8의 직사각형이고 세로는 4, 가로는 2, 3을 자른다고 한다. 여기서 볼 점은 3을 자르면 이미 3:7인데 여기서 2를 자른다고 7이 변할까? 이다. 즉, 내가 자르고 남은 것의 가장 큰 가로, 세로를 구해서 곱하면 되는 것이다. 세로부터 보자. 4위치를 자른다고 한다. 그렇다면 4 : 6으로 나뉠 것이고 우리는 6을 기억한다. 가로를 보면 3을 먼저 자른다. 3 : 5로 나뉘게 된다. 그 다음 2를 자르면 2 : 1 : 5이 된다. 지금 5가 ..

1. 문제분석 처음은 스위치의 개수와 정보를 주고 남학생과 여학생, 스위치의 위치가 주어진다. 남자는 쉽게 풀 수 있다. 만약 위치가 3이라면 3, 6, 9.. 이런식으로 스위치의 정보를 바꾼다. 반면 여자의 경우는 조금 생각을 해야한다. 테스트 케이스를 보자. 여자면서 3번 스위치가 주어졌다. 3번을 기준으로 왼쪽, 오른쪽 대칭을 확인한다. 만약 대칭이라면 변경한다. 또한 대칭이 아에 없다면 3번만 꺼주면 된다. 밑의 그림을 보고 확인하자. 그대로 구현해주면 되는 문제지만 필자는 계속 시간초과가 났다. 필자는 처음 구현할 때, 인덱스 범위만 맞는다면 while을 진행시켰다. 하지만 시간초과가 났다. 분명 정보도 많이 없을텐데 왜 시간초과가 날까 생각해 데이터를 조금 정제할 필요가 있다고 생각했다. 여기..

1. 문제분석 삼성코테 IM등급 문제를 가볍게 풀려다가 너무 현타가와서 정리를 한다. 맨날 DFS, BFS만 머리에 있어서 기본적인 것도 못풀었다. 문제는 간단하다. 왼쪽아래 좌표와 오른쪽 위의 좌표 총 4개가 주어지고 이들의 면적을 구하는 것이다. 단순히 생각하면 면적을 구하고 곂치는걸 빼면 되는구나! 라고 생각을 했다. 그러다보니 조건도 복잡하고 코드도 너무 더러워졌다. 저 그림을 보면 무엇이 생각날까? 바로 배열이다. 해당하는 부분을 1로 채우면 곂치던 말던 범위는 구해진다. 좌표를 받아 반복문으로 배열안의 값을 넣어주면 끝이다. 2. 구현 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringT..

1. 문제분석 문제는 생각보다 간단하다. 각 명령어에 맞게 변경해주면 되고 구현만 하면 끝이다. 이 문제는 3, 4번을 구현할 때 비트마스킹으로 구현한다고 한다. 비트마스킹이 정말 뭔지 모르기 때문에 이 포스팅에서는 단순 for문으로 구현했다. 1번과 2번은 정말 쉽게 구현할 수 있으니 넘어가겠다. 3번 같은 경우는 승객이 한칸씩 밀리고 마지막에 20번째에 사람이 있다면 하차를 한다. 단순히 for문으로 arr[기차][자리] = arr[기차][전의 자리(자리 - 1)]해주면 끝이다. 4번은 승객을 한칸씩 앞으로 댕기고 1번째의 자리에 있다면 하차한다. 마찬가지로 arr[기차][자리] = arr[기차][앞자리 (자리 +1)]하면 된다. 그 다음 조건을 보자. 이미 존재하는 기차가 있다면 그 기차는 통과하지..

1. 문제 분석 문제는 정말 간단한데 구현하는데 짜증이 좀 난 문제다. 투포인터 문제인건 알았지만 그 전에 그냥 for문으로 구현을 해보았다. 당연히 시간초과가 난다. 이제 투포인터로 풀어보자.. (문제에서 값이 없는 경우는 -1을 표시해줘야 한다고 한다. 문제좀.. 보자..) 나는 여기서 투포인터 알고리즘을 활용한 슬라이딩 윈도우를 사용했다. 간단하게 설명하면 특정범위를 한칸씩 옮겨가며 값을 확인하는 방법이다. 입력값으로 배열의 크기와 몇개를 포함해야하는지 알려줬으므로 라이언 인형일 때 인덱스를 구해둔다. 테스트케이스 1은 현재 0, 4, 6, 9가 된다. 즉 구하는 것은 (0, 4, 6), (4, 6, 9)만 구하면 끝이다. 이렇게 간단한 문제를 제대로 안읽어서 고생을 했다.. 2. 구현 import..