네임 들을 캐피털 화 시키는 작업이다. Sql의 서브 스트링을 알고 있다면 손쉽게 풀 수 있는 문제이다.
# Write your MySQL query statement below
select user_id,concat(upper(left(name,1)),lower(substring(name,2))) as name
from users
order by user_id;
concat을 이용해 문자열을 붙이고 , left()와 subString을 이용해 문자를 각각 나누어 주었다.
left(name,1)을 이용해 왼쪽 에서부터 1개,
substring (스트링,시작,끝) 인데 끝이 없다면 끝까지 들고 온다. 이후 각각 upper와 lower를 이용해서 이어 붙이면 끝
1484.Group Sold Products By The Date
이번 문제는 은근 애를 먹었다, 그룹 바이를 이용해 데이터 별로 나누어 주었지만 products 에 어떻게 나열해야 할지 생각 이 잘 나질 않아서 구글링 끝에 작성했다.
# Write your MySQL query statement below
select a.sell_date,
count(distinct a.product) as num_sold,
group_concat(distinct product order by product asc) as products
from activities a
group by sell_date
order by sell_date
select 안의 date 부분은 뭐 문제에서 요구 되어지는 부분이고 특별할 것이 없어 넘어간다.
count(distinct a.product) 이부분은 count를 이용해서 하자니 중간에 겹치는 문자가 있다면 그걸 전부 카운트해버리는 것이 아닌가...
중복을 제거해주는 distinct 를 한번 넣어 봤는데 오류 없이 작동하더라, 저렇게 안쪽에도 선언 이 되는지는 이번에 처음 알게 되었다.
group_concat 나를 제일 애먹인 부분이다.
그룹별로 데이터를 나열할 때 사용되어지는 이 함수이다, 사용법은 간다 하게 나열하고 싶은 데이터를 함수 안에 인자로 패스해주면 된다. 문제에서 요구되어지는 순서와 중복이 없어야 하기 때문에 나는 위와 같이 추가적인 제한사항을 적어 주었다.
1527.Patients With a Condition
간만에 자신감 있게 풀고 틀리고 한 번 더 제출해서 통과했다. ㅋㅋ 특별할 것 없이 DIAB1 이 포함된 문자열을 찾아서 퍼올려주는 문제이다.
지난번에 배운 like를 이용해 작성했다.
# Write your MySQL query statement below
select patient_id,patient_name,conditions
from patients
where conditions like'DIAB1%' or conditions like '% DIAB1%';
처음 작성할때 like '% DIAB1%' 이런 식으로 작성하니 테스트 12번에서 걸린다 ㅋㅋㅋ {"headers": ["patient_id", "patient_name", "conditions"], "values": [[1, "Daniel", "SADIAB100"]]} 위의 like 로 때려버리면 이 인풋은 1개의 값을 반환하게 된다. DIAB1의 prefix 인 경우를 찾아야 하는데 내가 찾은 건 단순 한 번이라도 사용되었다면 반환하기 때문에 이렇게 에러가 발생한다.
or를 이용해서 startsWIth 느낌 나게 한 개, 공백을 이용해서 시작하는 단어로 구분을 지어 주었다.
알고리즘 과 는 달리 SQL 문제들은 discuss의 글들이 대부분 비슷하다... db 가 다르지 않은 이상 거의 유사하기 때문에 discuss 보는 재미가 많이 반감되었다..
보너스 계산해서 퍼올리는 문제이다. 대신 조건은 아이디가 홀수인 경우 , 그리고 이름이 'M'으로 시작하지 않는 경우에만 보너스가 주어지고, 아니라면 0 쿼리 결과로 띄워주어야 한다.
select 문 그리고 bonus라는 결괏값에 if 문을 넣어 적을 생각을 하였다.
# Write your MySQL query statement below
select employee_id,
if(name not like 'm%' and employee_id % 2 = 1,salary,0) as bonus
from employees
order by employee_id;
if( 조건, 참, 거짓) 3항 연산자가 생각나는 표현법이지 않은가 직관적이고 좋다.
문자의 시작을 검사할 때 like '문자%' 이런 기법이 있다는 것을 검색하면서 알게 되었다.
like '문자 %' 문자로 시작하는 걸 검색할 때
like '% 문자' 문자로 끝나는 걸 검색할 때
like '% 문자%' 문자가 들어 있는 걸 검색할 때
627.Swap Salary
성별을 업데이트해주는 쿼리를 날려야 한다.
set을 이용하고, 조건이 단 2가지 이기 때문에 If를 사용할 생각을 했다, 이보다 많다면 아마 case를 쓰지 않을까 싶다.
# Write your MySQL query statement below
update
salary
set
sex = if(sex='f','m','f');
심플하다 특이사항 없이 위에 작성한 그대로다.
디스커스를 둘러보던 중 케이스를 작성한 사람이 있어 코드를 보자.
UPDATE
Salary
SET
sex =
(CASE
WHEN (sex='f') THEN 'm'
WHEN (sex='m') THEN 'f'
END);
솔직히 이렇게 case로 작성하는 것이 보다 직관적 이여서 추후 복잡한 로직이라면 이런 케이스의 경우가 더선호되지 않을까 싶다.
196.Delete Duplicate Emails
딜리트 쿼리를 이용해서 중복된 이메일을 지워주어야 한다, 대신 아이디가 높은 아이들이 지워져야 한다.
음 막막해서 구글링 해서 이것저것 붙여 넣어서 완성했다.. ㅋㅋ
# Please write a DELETE statement and DO NOT write a SELECT statement.
# Write your MySQL query statement below
delete p1 from person as p1
inner join person as p2
where p1.id>p2.id and p1.email = p2.email;
지난번 작성한 join을 여기서 또 작성한다. 동일한 테이블을 조인시킨다면 모든 값이 올라가고, 그중에 조건을 걸어서 지워주는 것이다.
동일한 이메일에 아이디가 크다면. 조인을 이렇게도 사용한다는 것이 신기했다.
DELETE FROM Person
WHERE ID NOT IN
(SELECT * FROM
(
SELECT MIN(ID) FROM Person
GROUP BY email
) as Person1
);
그룹바이를 이용해 이메일 별로 가장 작은 아이디 값을 가져오고 그것이 person에 없다면 지워주는 방식이 새로웠다.
테이블 안 에서 각각 영역이 3M 이상 , 인구수가 25M 이상인 곳을 퍼올려서 보여주면 된다 코드는 비교적 간단하다.
# Write your MySQL query statement below
select
name,population, area
from world
where area >= 3000000 or population >= 25000000;
단순한 select 문을 이용해 쿼리의 결과를 보여줄 name, population, area 를 선택하고
where 를 이용해 조건을 걸어주었다. or 를 사용해 2개의 조건을 걸어주고 Programming 언어와 유사하게 and 도 가능하다.
1757.Recyclable and Low Fat Products
위의 문제와 비슷하게 select 로 low fat and recyclable 을 퍼올리면 된다.
# Write your MySQL query statement below
select
product_id
from products
where low_fats = 'Y' and recyclable = 'Y';
' ' 를 이용해 enum type 으로 주어지는 테이블의 값을 받아올수 있다. 첫번쨰 문제 와 크게 다를바 없다고 생각한다.
584.Find Customer Referee
커스터머 테이블 에서 추천 아아디가 2가 아닌 경우를 퍼올리는거다. 단순하게 select ,!= 을 이용해서 작성 하고 테스트를 돌려보니 추천 아이디 1 인 zack 만 넘어오는게 아닌가.... null 이 값에 포함되어 있는경우 not null 혹은 is null 과 같은 추가 코드를 작성해야 null 값을 핸들링 해줄수 있다... 자칫 잘못하다간 select 내의 다른값이 업데이트 되는경우가 있으니 주의하자.
# Write your MySQL query statement below
select
name
from customer
where referee_id != 2 or referee_id IS NULL;
183.Customers Who Never Order
query 로 커스터머, 주문을 한번도 한적이 없는 coustomers 의 이름을 받아 오는것이다. 음 이제는 생각을 좀 해서 작성해야한다.
이중 쿼리로 작성해서 데이터를 받아올 생각을 했다.
# Write your MySQL query statement below
select name as Customers
from customers
where id not in (select customerId from orders);
최초 작성을 id is not 을 작성했더니 select 로 받아오는 값이 여러개 의 값이여서 에러가 난다고 한다... 이 부분을 해결해 주기 위해 찾다보니 not in 이라는 조건이 존재하더라.. not in/in (여러개의 값) 을 이용해서 필요한 부분만 을 필터링 해서 사용해줄수 있다. 처음 알았다...뭔가 영어 그대로 직관적인데 왜 이 방법이 즉각적으로 떠오르지 않았는지 ... 이 풀이 외에 조인을 이용해서 풀이한 사람들도 있다. 바로 도전해봤다.(구글과 함께..)
# Write your MySQL query statement below
select c.name,o.customerId
from customers as c
left join orders as o
on c.id = o.customerId;
우선 left join 을 잘모르기 떄문에 한줄씩 테스트를 해보자. 이런식으로 결과값을 받아보니 name,id ["값","값"] 이런식으로 넘어오는데... Customers 에는 id 가 있지만 . order 에는 customerId 에 없다면, null 값으로 리턴해주는것이아닌가... 그러면 null 인 값들의 name 만 반환해준다면 답인것이다..
# Write your MySQL query statement below
select c.name,o.customerId
from customers as c
left join orders as o
on c.id = o.customerId
where o.customerId is null;
그냥 사용만했지 정확히 어떠한 기능을 하는지 알아보자
Join 에는 두가지 종류가 있다. Inner Join , Outer Join
1. Inner Join
Select <열목록>
From <첫번째 테이블>
Inner Join<두번쨰 테이블>
On <조건>
Where [검색조건]
과 같이 되는데 ... inner 라는 부분은 생략이 가능하다더라.. 대신 이 조인을 이용해 sql을 퍼오릴 경우는 두테이블 모두 있는 내용만 조인되는 방식이다. , 위의 문제 처럼 한곳에 있는 내용을 조인하기 위해서 사용 되는것이 외부 조인이다.
2. Outer Join
Select <열목록>
From <첫번째 테이블(Left 테이블)>
<Left | Right | Full> Outer join <두번째 테이블(Right 테이블)>
On <조건>
Where [검색조건]
내부조인 보다는 조금 더 복잡하지만, 사용법은 비슷하다. left outer join 은 적어도 왼쪽의 내용은 모두 퍼올리다는 의미이다. 그래서 is null 을 이용한 검색 조건을 이용한다면 left 테이블 의 차집합 ? 값만 퍼올린다고 이해했다. 위에는 outer 부분이 생략되어 있는데 inner 와 동일하게 생략이 가능하다. 구글에 검색해보니 큰차이는 없고 오히려 left join 이 보다 직관적이여서 이걸 추천하는 사람들도 종종 보인다.
long beforeTime = System.currentTimeMillis(); //코드 실행 전에 시간 받아오기
//실험할 코드 추가
// ex)
/***/
long afterTime = System.currentTimeMillis(); // 코드 실행 후에 시간 받아오기
long secDiffTime = (afterTime - beforeTime)/1000; //두 시간에 차 계산
System.out.println("시간차이(m) : "+secDiffTime);
최단 경로를 구하는 알고리즘 중 하나이다. 지난번 cs 네트워크 라우터 관련 검색하다가 잠깐 살펴본 내용인데 이번 기회에 흐름을 익혀보고자 글을 작성한다.
위의 그래프 에서 각 노드 간 의 최단거리를 구하는 방법 중 하나이다.
distance 의 배열이 존재하고 모두 최대 값 혹은 엄청 큰수로 초기화를 진행한다. 배열 의 수는 노드의 갯수 만큼 구성해서 계속 저장해 가며 값을 기록한다.
0번 에서 출발한다고 할시 갈수 있는경우 0-1, 0-2 이 가존재하며 배열에는 아래와 같이 기록한다.
distance = 0 | 5 | 1 | INF | INF | INF => 최초 시작점을 0 으로 대입해 시작 하며 이후 다음 노드는 거리가 가장 짧은 2번 부터 진행한다. 이렇게 진행하며 현재 진행 중인 간선의 수가 노드의 갯수-1 이된다면 진행을 멈추고 마지막 값을 리턴하면 그것 이 최단 거리가 된다.
코드로 구현해보자.
class Node{
int to;
int distnace;
public Node(int to, int distance) {
this.to = to;
this.distnace = distance;
}
}
각각 의 노드 에 대한 정보를 기록하기 위해 이너클래스 로 노드를 하나 구성해준다.
class Dijkstra{
public void dijkstra(int[][] locateInfo, int edge, int start){
ArrayList<ArrayList<Node>> graph = new ArrayList();
for(int i=0;i<edge;i++){
graph.add(new ArrayList());
}
for(int i=0;i< locateInfo.length;i++){
int from = locateInfo[i][0];
int to = locateInfo[i][1];
int distance = locateInfo[i][2];
graph.get(from).add(new Node(to,distance));
}
}
}
노드 를 담기 위한 2중 리스트를 생성 해준다. 각 첫번째 리스트 는 현재 엣지 를 의미하고 그안에 담긴 리스트 들은 갈수 있는 경로 를 생성해 더해준다.
public void dijkstra(int[][] locateInfo, int edge, int start){
ArrayList<ArrayList<Node>> graph = new ArrayList();
for(int i=0;i<edge;i++){
graph.add(new ArrayList());
}
for(int i=0;i< locateInfo.length;i++){
int from = locateInfo[i][0];
int to = locateInfo[i][1];
int distance = locateInfo[i][2];
graph.get(from).add(new Node(to,distance));
}
int[] shortest_dist = new int[edge];
Arrays.fill(shortest_dist,1,shortest_dist.length,1<<30);
PriorityQueue<Node> q = new PriorityQueue<>((x,y)->x.distnace - y.distnace);
boolean[] visit = new boolean[edge+1];
q.offer(new Node(start,0));
}
거리 들을 기록할 배열을 하나 생성해주고 , 2^31-1 이 int 의 최대값이니 그전 까지 업데이트 해주자 전에 한번 overflow 나고 나서부터는 이렇게 초기화를 진행하고 있다.
우선순위 큐를 거리가 짧은 순으로 해서 생성해주고, 마지막까지 가는데 있어 중복 계산을 피할 방문 배열을 생성해준다.
처음 시작점을 변수로 제공받기 떄문에 큐안에 시작점을 넣어주자
public void dijkstra(int[][] locateInfo, int edge, int start){
ArrayList<ArrayList<Node>> graph = new ArrayList();
for(int i=0;i<edge;i++){
graph.add(new ArrayList());
}
for(int i=0;i< locateInfo.length;i++){
int from = locateInfo[i][0];
int to = locateInfo[i][1];
int distance = locateInfo[i][2];
graph.get(from).add(new Node(to,distance));
}
int[] shortest_dist = new int[edge];
Arrays.fill(shortest_dist,1,shortest_dist.length,1<<30);
PriorityQueue<Node> q = new PriorityQueue<>((x,y)->x.distnace - y.distnace);
boolean[] visit = new boolean[edge+1];
q.offer(new Node(start,0));
while(!q.isEmpty()){
Node cur = q.poll();
if(visit[cur.to]) continue;
visit[cur.to] = true;
for (int i = 0; i < graph.get(cur.to).size(); i++) {
Node next = graph.get(cur.to).get(i);
if(visit[next.to]) continue;
if(shortest_dist[next.to] > cur.distnace+next.distnace){
shortest_dist[next.to] = cur.distnace+next.distnace;
q.offer(new Node(next.to,shortest_dist[next.to]));
}
}
}
System.out.println(Arrays.toString(shortest_dist));
}
큐 안이 비어있기 전까지 계속 반복문 을 돌려준다. 대신 모든 곳을 방문 했다면 큐 를 계속해서 뽑아오기 때문에 반복문 아래부분 까지 내려가지 않고 계속 뽑아주어 함수를 종료해준다.
현재 가려는 방향의 엣지를 받아와 그안에 들어있는 갈수있는 방향들에 대한 정보들을 뽑아와 기록 되어있는 거리와 현재 거리+다음 노드의 거리 를 이용해 최소값을 계속 업데이트 하는 방식이다. 만약 그렇게 업데이트 가 되었다면 큐에 다시 넣어주어 새로운 지점에서 시작하는 노드를 넣어준다. 2~3 번 이상 계속 노트에 손코딩 하다보니 외워버렸지만 미래에 찾고있을 나를 위해 이렇게 정리해 보았다.
전형적인 재귀 문제라고 생각한다. 4등분을 해서 타고 타고 타고 비교 가능한 최소 단위까지 타고 들어가서 비교를 시작해 가면서 밖으로 나가면 된다.라고 생각하고 한참 고민했다 코드를 작성하는데.... 특히 좌표를 어떻게 넘겨주어야 할까? 를 제일 많이 고민했던 부분이다. 지난번 제로베이스 1차인가 2차 코테 당시 4번 문제를 사분면으로 나눠서 풀었던 기억이 남아있어 어렵지 않게 접근은 가능했으나... 시간 안에 풀지 못했다... 문제를 푸는 데 있어 1시간 정도 걸렸던 것 같다.
코드를 보자.
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
int[][] arr = new int[N][N];
for (int i = 0; i < N; i++) {
String[] inputs = bf.readLine().split(" ");
for (int j = 0; j < inputs.length; j++) {
arr[i][j] = Integer.parseInt(inputs[j]);
}
}
bf.close();
Boj b = new Boj();
b.main(arr);
}
}
class Boj {
int white = 0;
int blue = 0;
int[][] arr = {};
public void main(int arr[][]) {
this.arr = arr;
helper(0, 0, arr.length);
System.out.println(white);
System.out.println(blue);
}
public void helper(int row, int col, int n) {
if (checker(row, col, n)) {
if (arr[row][col] == 0) {
white++;
} else {
blue++;
}
return;
}
int half = n / 2;
helper(row, col, half);
helper(row, col + half, half);
helper(row + half, col, half);
helper(row + half, col + half, half);
}
public boolean checker(int row, int col, int n) {
int target = arr[row][col];
for (int i = row; i < row + n; i++) {
for (int j = col; j < col + n; j++) {
if (arr[i][j] != target) {
return false;
}
}
}
return true;
}
}
전반적인 아이디어는 위에 작성한 대로 4 등분해서 넘겨줄 방법과 좌표를 처음 시작점을 넘겨주는 것에 착안해서 작성했다.
또한 함수 탈출 조건을 위한 한 개 의 종이를 이용해 색구분을 확인하고, 현재 진행 중인 재귀의 색 분별을 통해 재귀 종료 혹은 다음 재귀로 넘겨주는 것이다.
적다 보니 말 몇 줄 안되는걸 약 1시간 동안 이리저리 구른 나를 생각하니 화가 난다.
helper 함수를 재귀적 호출할 메인으로 삼고 이 친구를 4등분 나눠주면서 진행한다. checker를 안에 넣어서 확인하려고 했으나 코드가 길어져서 함수로 따로 빼주었다. 따로 특이한 점 없는 코드다.
나머지 분들 코드도 이와 매우 유사해 코드 가져오신 분의 보다 직관적인 코드를 소개하고자 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Practice094 {
static int[][] arr;
static int blueCnt, whiteCnt, gap;
static boolean cutFlag;
// cut 풀이에 추가로 필요한 변수
static int[] leftUpIdx, rightDownIdx;
// cut2 풀이에 추가로 필요한 변수
static int x, y;
public static void solution(int gap) {
cut(new int[]{0,0}, new int[]{gap - 1, gap - 1}, gap - 1);
System.out.println(whiteCnt);
System.out.println(blueCnt);
}
public static void cut(int[] leftUpIdx, int[] rightDownIdx, int gap) {
cutFlag = false; // 초기화
// 1칸짜리 종이임
if(Arrays.equals(leftUpIdx, rightDownIdx)) {
if(arr[leftUpIdx[0]][leftUpIdx[1]] == 1) {
blueCnt++;
} else {
whiteCnt++;
}
return;
}
// 다른 숫자가 있으면 잘라
for (int i = 0; i <= gap; i++) {
for (int j = 1; j <= gap; j++) {
if(arr[leftUpIdx[0] + i][leftUpIdx[1]] != arr[leftUpIdx[0] + i][leftUpIdx[1] + j]) {
cutFlag = true;
break;
}
}
if(i < gap && arr[leftUpIdx[0] + i][leftUpIdx[1] + gap] != arr[leftUpIdx[0] + i + 1][leftUpIdx[1]]) {
cutFlag = true;
break;
}
if(cutFlag) {
break;
}
}
// 잘라야 하면
if(cutFlag == true) {
gap = (rightDownIdx[0] - leftUpIdx[0]) / 2; // gap은 종이의 가로&세로 사이즈
int next = gap + 1; // next는 다음 종이까지의 인덱스 차이
cut(new int[]{leftUpIdx[0], leftUpIdx[1]}, new int[]{leftUpIdx[0] + gap, leftUpIdx[1] + gap}, gap); // 왼쪽 위
cut(new int[]{leftUpIdx[0], leftUpIdx[1] + next}, new int[]{rightDownIdx[0] - next, rightDownIdx[1]}, gap); // 오른쪽 위
cut(new int[]{leftUpIdx[0] + next, leftUpIdx[1]}, new int[]{rightDownIdx[0], rightDownIdx[1] - next}, gap); // 왼쪽 아래
cut(new int[]{rightDownIdx[0] - gap, rightDownIdx[1] - gap}, new int[]{rightDownIdx[0], rightDownIdx[1]}, gap); // 오른쪽 아래
} else {
if(arr[leftUpIdx[0]][leftUpIdx[1]] == 1) {
blueCnt++;
return;
} else {
whiteCnt++;
return;
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
gap = Integer.parseInt(br.readLine());
arr = new int[gap][gap];
for (int i = 0; i < gap; i++) {
String[] s = br.readLine().split(" ");
for (int j = 0; j < gap; j++) {
arr[i][j] = Integer.parseInt(s[j]);
}
}
solution(gap);
}
}
구현에 있어 어려운 좌표 해결을 위와 같이 배열에 좌표를 담아 앞뒤로 넘겨준다. 처음 이렇게 시도하다가 좌표를 계산에 머리가 고장이 나서 지우고 다른 방법으로 접근했다. 구현하려고 하다 실패한 부분을 다른 사람의 코드로 보니 다음에 어떤 식으로 접근해야 할지 영감을 받았다.
인용문 배열의 개수를 이용해서 현재 진행되는 인용문의 횟수를 이용해 계산하는 방식이다. 하.. 나는 바보인가 ㅠ
다른 분의 코드를 보자.
import java.util.*;
class Solution {
public int solution(int[] citations) {
Arrays.sort(citations);
for (int i = 0; i < citations.length; i++) {
int h = citations.length - i;
if (citations[i] >= h) {
return h;
}
}
return 0;
}
}
문제가 너무 길다 하... 대충 설명하자면 점프와 순간이동을 할 수 있는 슈트 가 있고 점프는 에너지를 1 소모 하지만 순간이동은 에너지를 소모하지 않는다. 즉 최대한 순간이동을 많이 하면 된다. 문제 설명이 길어서 그렇지 비교적 간단한 로직이다. 잉 막상 그려보고 구현하려고 하다 보니 줄줄이 빨간색이다. 최대한 순간이동을 많이 하려면 어떻게 해야 할까... 생각하다 보니 어쨌든 최초 시작 후 순간이동을 계속하다 보면 2의 배수로 늘어난다는 사실을 깨달았다... 이걸 테스트해보기 위해 5000을 2로 나누기 시작 모든 나머지들 더하고 보니 5라는 숫자가 나왔다. 저기 있는 예제가 나에게 힌트를 주었다. 25분 고민하고 코드 1분 작성했다.
import java.util.*;
public class Solution {
public int solution(int n) {
int ans = 0;
while(n/=2>0)ans = i%2 != 0 ? ans+1 : ans;
return ans;
}
}
현재 값을 while을 이용해 계속 2로 나눠 주며 답을 업데이트하고 반환한다.ㅋㅋㅋ
문제 가져오신 분의 코드를 보자.
import java.util.*;
public class Solution {
public static int solution(int n) {
return Integer.bitCount(n);
}
public static void main(String[] args) {
System.out.println(solution(15));
}
}
응??? ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 이렇게 생각을 하지 않은 건 아니다. 쉬프트 하면서 1<<n 하면서 문제를 풀려고 했으나 접근법이 틀렸다고 생각했는데 ㅋㅋㅋ 비트 카운트라는 매우 훌륭한 스테틱 매서드를 제공해준다... ㅋㅋㅋㅋㅋㅋㅋ 자바는 알면 알수록 신기한 메서드가 참 많은데 왜 싫어하는 사람들이 많은지 모르겠다...
1번 문제와 유사하지만 다르다... ㅋㅋㅋ 아 재귀 그만 쓰고 싶다 ㅠㅠㅠ 그렇지만 문제 보자마자 재귀적 풀이 밖에 떠오르지 않았고, 당연히 30분 안에 풀지 못했다. 약 1시간 정도 투자해서 코드를 작성했다. 아이디어는 위와 동일하게 4 등분씩 나눠 가면서 현재 사이즈가 4라면 그냥 계산해서 재귀 탈출하는 것을 조건으로 하였다. 최초 작성은 priorityqueue를 이용해 두 번째 큰 수를 제거해주었으나. 1300 초가 넘어간다. ㅋㅋㅋ 그래서 스터디 원 분 중 한분은 arr, 정렬을 그냥 하셨길래 이용했더니 약 900까지 당겨진다. ㅋㅋ
class kubin{
int[][] arr;
public void main() throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int input = Integer.parseInt(bf.readLine());
arr = new int[input][input];
for (int i = 0; i < input; i++) {
String[] inputs = bf.readLine().split(" ");
for (int j = 0; j < inputs.length; j++) {
arr[i][j] = Integer.parseInt(inputs[j]);
}
}
System.out.println(helper(new int[]{0,0},input));
}
public int helper(int[] start,int size) {
if(size == 2){
int[] n = new int[4];
int x = 0;
int row = start[0],col = start[1];
for (int i = row; i < row+2; i++) {
for (int j = col; j < col+2; j++) {
n[x++] = arr[i][j];
}
}
Arrays.sort(n);
return n[2];
}
int mid = size/2;
int curRow = start[0];
int curCol = start[1];
int[] needToSort = new int[4];
needToSort[0] = (helper(new int[]{curRow,curCol},size/2));
needToSort[1] = (helper(new int[]{curRow,curCol+mid},size/2));
needToSort[2] = (helper(new int[]{curRow+mid,curCol},size/2));
needToSort[3] = (helper(new int[]{curRow+mid,curCol+mid},size/2));
Arrays.sort(needToSort);
return needToSort[2];
}
}
배열 만들어서 다음 계산으로 넘겨주고 현재 사이즈를 줄여가는 것이다. 별로 특별할 것 없는 1번과 매우 유사한 코드인데 1번도 고민하고 이것도 고민하다니.... 바보가 맞는가 보다 ㅋㅋ.
재귀가 아닌 for 문을 이용해서 푸신분의 코드를 보자.
package backjoon17829;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
public class Main {
static int N;
static int[][] matrix;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
// 입력받은 수로 N * N 행렬 만드는 부분
matrix = new int[N][N];
for (int i = 0; i < N; i++) {
String[] s = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
matrix[i][j] = Integer.parseInt(s[j]);
}
}
int size = N;
while (size > 1) { // N * N 행렬의 가로 세로가 1보다 클 때 까지 반복
// 현재 행렬 가로(세로)길이를 2로 나눈 값을 제곱하면 다음 N * N 행렬을 만드는 데 필요한 수를 저장할 수 있는 1차원 배열의 사이즈를 알 수 있음
// 예를 들어 현재 N * N 행렬의 가로(세로)길이가 8이면 (8 / 2)^2 = 16 -> 4 * 4의 행렬을 만들 수 있음
// 그리고 고정된 2 * 2 크기의 행렬 안에서 두 번째 큰 수를 구해야 하므로 i, j를 +2 씩 증가 시키면서 반복, small_matrix에 저장
int[] small_matrix = new int[(int) Math.pow(size / 2, 2)];
int idx = 0;
for (int i = 0; i < size; i += 2) {
for (int j = 0; j < size; j += 2) {
small_matrix[idx++] = getNum(i, j);
}
}
// N * N 행렬을 전체 탐색 후 크기를 반으로 줄임
// 4 * 4 행렬로 예를 들면 small_matrix의 길이는 16이고 i = 0 ~ 15까지 반복하면서
// row = 0 / 4 = 0, col = 0 % 4 = 0
// row = 1 / 4 = 0, col = 0 % 4 = 1
// row = 2 / 4 = 0, col = 0 % 4 = 2
// row = 3 / 4 = 0, col = 0 % 4 = 3
// row = 4 / 4 = 1, col = 4 % 4 = 0
// row = 5 / 4 = 1, col = 5 % 4 = 1
// row = 6 / 4 = 1, col = 6 % 4 = 2
// row = 7 / 4 = 1, col = 7 % 4 = 3
// 이런식으로 4 * 4 행렬의 값을 채워줄 수 있음
matrix = new int[size / 2][size / 2];
for (int i = 0; i < small_matrix.length; i++) {
int row = i / (size / 2);
int col = i % (size / 2);
matrix[row][col] = small_matrix[i];
}
// matrix에 새로운 값을 넣어준 후 size를 줄여줌
size /= 2;
}
// 맨 마지막에 남은 값 출력
System.out.println(matrix[0][0]);
}
public static int getNum(int row_start, int col_start) {
// 두 번째 큰 수를 뽑기위한 내림차순 우선순위 큐
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
for (int i = row_start; i < row_start + 2; i++) {
for (int j = col_start; j < col_start + 2; j++) {
priorityQueue.offer(matrix[i][j]);
}
}
priorityQueue.poll();
return priorityQueue.poll();
}
}
재귀로 푼걸 이렇게 for 문을 이용해 작성한 걸 보면 새로운 문제처럼 보인다... while을 이용해 현재 배열이 줄은 상태의 배열을 선언해 안에서 작업해준 후 다음 while 문으로 점점 줄여나간다. 멋진 아이디어 같다. 중간에 행, 열 계산을 나눗셈과 나머지 연산을 사용한 트릭이 인상 깊다. 이분 코드도 priorityqueue 가 아닌 배열을 이용하면 800ms까지 시간 단축이 가능한 코드이니 재귀가 싫다면 이렇게 작성하는 것도 하나의 좋은 해결책이 될 수 있다. 주석 이 깔끔하니 주접 그만 떨고 다음 문제로 넘어간다.
스도쿠는 그냥 문제를 외워 버렸다. 지난번도 그렇고 이번에도 그렇게 그냥 문제와 풀이 방식을 달달 외웠다.
위의 포스팅에서 자세한 내용이 있으니 설명 은 생략하고 코드만 공유하겠다.
class Solution1 {
public void solveSudoku(char[][] board) {
helper(board,0,0); // 좌표
for(char[] c : board){
System.out.println(Arrays.toString(c));
}
}
public boolean helper(char[][] board, int row,int col){
if(col == 9){ //한줄끝나서 다음줄로 넘겨주는 조건
return helper(board,row+1,0);
}
if(row == 9){
return true; //우리가 찾을 케이스 단하나.
}
if(board[row][col] == '.'){
for (int i = 1; i <= 9; i++) {
if(validateCheck(board,row,col,i)){
board[row][col] = (char)(i+'0');
// return helper(board,row,col+1);
if(helper(board,row,col+1)){
return true;
// }
}
}
board[row][col] = '.';
//위에서 함수 가 다음으로 나아기자못하고 아래로 내려온다면 ? 다시 원복 시키고 false 를 리턴해
// 현재 진행중인 재귀를 종료시켜줍니다.
return false;
}else{
return helper(board,row,col+1);
}
}
public boolean validateCheck(char[][] board,int row,int col,int target){
char tg = (char)(target+'0');
//Col check
for (int i = 0; i < 9; i++) {
if(board[i][col] == tg) return false;
}
//Row check
for (int i = 0; i < 9; i++) {
if(board[row][i] == tg) return false;
}
//Subbox check
int nRow = row/3*3;
int nCol = col/3*3;
for (int i = nRow; i < nRow+3; i++) {
for (int j = nCol; j < nCol+3; j++) {
if(board[i][j] == tg) return false;
}
}
return true;
}
}
//Coordinate Intermediate
class Solution2 {
public void solveSudoku(char[][] board) {
helper(board,0);
for(char[] c : board){
System.out.println(Arrays.toString(c));
}
}
public boolean helper(char[][] board,int n){
if(n == 81)return true; // 왜 끝났으니깐 9*9 ? 81 우리는 0부터 출발합니다.
int row = n/9,col = n%9; // 로우칼럼 계산하기 항상 칼럼으로 나누고 나머지 연산 해주면 로우칼럼 나오는 트릭.
if(board[row][col]!= '.') return helper(board,n+1); // 비어있지 않기 떄문에 넘겨줍니다.
for (int i = 1; i <= 9; i++) { //어떤 숫자가 검증이 된지 모르기 떄문에 for 를돌려줍니다. 1번부터 가던 9번부터 가던 어쩃든 모든 숫자 돌면됩니다.
if(validateCheck(board,row,col,i)){ // 검증 된 숫자라면 진행 시켜 줍니다.
board[row][col] = (char) (i + '0');
if(helper(board,n+1)){
//false 가 경우 단하나. helper 함수가 끝까지 내려가는경우
// 즉 어는 숫자도 검증되지 못해 여기서 다음 재귀로 넘어가지 를 못해 아래로 내려가는 경우
return true;
}
}
}
board[row][col] = '.'; // 저 위에서 다음 재귀로 못넘어간 나머지 가치 가 없으니 원복시키고 함수를 종료 합니다.
return false;
}
public boolean validateCheck(char[][] board,int row,int col,int target){
char tg = (char)(target+'0');
//row check && col check;
for (int i = 0; i < 9; i++) {
if(board[row][i] == tg || board[i][col] == tg){
return false;
}
}
//3*3 chcck;
int nRow = row/3*3;
int nCol = col/3*3;
for (int i = nRow; i < nRow+3; i++) {
for (int j = nCol; j < nCol+3; j++) {
if(board[i][j] == tg) return false;
}
}
return true;
}
}
//Coordinate Master 10.9k view Solution
class Solution3 {
public void solveSudoku(char[][] board) {
dfs(board,0);
}
private boolean dfs(char[][] board, int d) {
if (d==81) return true; //found solution
int i=d/9, j=d%9;
if (board[i][j]!='.') return dfs(board,d+1);//prefill number skip
boolean[] flag=new boolean[10];
validate(board,i,j,flag);
for (int k=1; k<=9; k++) {
if (flag[k]) {
board[i][j]=(char)('0'+k);
if (dfs(board,d+1)) return true;
}
}
board[i][j]='.'; //if can not solve, in the wrong path, change back to '.' and out
return false;
}
private void validate(char[][] board, int i, int j, boolean[] flag) {
Arrays.fill(flag,true);
for (int k=0; k<9; k++) {
if (board[i][k]!='.') flag[board[i][k]-'0']=false;
if (board[k][j]!='.') flag[board[k][j]-'0']=false;
int r=i/3*3+k/3;
int c=j/3*3+k%3;
if (board[r][c]!='.') flag[board[r][c]-'0']=false;
}
}
}
지난번에 이어 이번에 도 시간 안에 푼 건 1문제밖에 없다.. ㅠㅠ 알고리즘 이란 녀석은 알면 알수록 점점 나에게서 멀어지는 기분이 든다.
아는 만큼 보이는게 아니라 아는만큼 생각을 하게 돼서 생각하는 시간이 점점 길어지는데 이걸 어떻게 줄여나가야 할지... 코드를 그냥 외워서 비슷한 유형에 사용하는 방법밖에 모르겠다.
