no image
백준 1261 알고스팟 node.js
2206번 벽 부수고 이동하기와 매우 유사한 0-1bfs, 데이크스트라 문제이다. 두가지 해결법이 있는데, 0-1bfs로 접근한다면 dist배열에는 2차원 배열에서 해당 좌표까지 도착했을 때 벽을 부순 횟수를 기록하고 벽을 부순 횟수가 더 적을 때 deque에 삽입한다 우리는 최대한 벽을 부수지 않으면서 멀리 갈 수 있어야 한다. 때문에 벽을 부수지 않고 전진하는 경우 deque의 front에 삽입하고 벽을 부수는 경우 deque의 back에 삽입한다. 하지만 이건 내가 데이크스트라를 통해 문제를 해결한 이후에 본 풀이법이다. 데이크스트라로 접근하는 것이 더 이해가 쉬울 수 있다. 기존 데이크스트라는 탐색 시점 최단 거리의 노드를 queue에 넣고, 방문한 노드 기준으로 다시 연결된 노드의 최단거리를 갱..
2024.03.15
no image
백준 1700 멀티탭 스케줄링 node.js
이 문제는 사실 정석으로 접근했다면 풀지 못했을 것이다. 운영체제 내용과 관련이 있는 흥미로운 문제이다. 스케쥴링은 필요한 자원을 적절히 할당하여 효율적으로 리소스를 활용하는 것이다. 페이징 기법 프로세스가 사용하는 메모리 공간을 잘게 나누어 비연속적으로 사용하는 기법이다. 프로세스 적재를 위해 연속된 메모리를 요구하지 않기 때문에 한정된 메모리 공간을 효율적으로 사용할 수 있다. 가상 메모리 공간의 단위를 page, 물리 메모리 공간을 frame 이라고 하고 둘의 크기는 같다. 하지만 물리 메모리는 한정적이기 때문에, 운영체제는 물리 메모리와 보조 저장공간의 swap 공간을 함께 활용하게 되는데, 이 때 참조한 페이지가 물리 메모리에 올라가 있지 않을 때(invalid) 참조하는 페이지를 교체해서 새롭..
2024.03.12
no image
백준 17298 오큰수 자바스크립트
입력 크기에서 힌트를 얻는 편이다. n이 1000000까지 들어온다는 것은 시간복잡도 O(n)으로 해결해야 1초로 끊을 수 있다는 뜻이다. 그러므로 배열을 선형으로 한번만 순회하면서 해결할 수 있는 방법을 생각해 보는 것이 좋겠다. 배열이 계속 내림차순 이라면 오큰수는 나올 수 없다. 반대로 배열이 오름차순이라면 맨 마지막 수를 제외한 모든 수는 자신의 앞에 수를 오큰수로 가질 것이다. 이를 토대로 생각해보면, 현재 내가 순회하는 숫자를 기준으로 내림 차순이 이어지면 오큰수는 알 수 없고, 나보다 큰 수가 나왔다면, 그 수는 여태 오큰수를 알 수 없던 모든 수의 오큰수 '후보'가 되는 것이다. 이제 해결법을 떠올릴 수 있다. 내림차순이라면 현재 순회하는 수의 정보를(값, 인덱스) 잠시 저장해두고, 오름차..
2024.03.04
no image
백준 9934 완전 이진트리 node.js
접근법을 알면 쉽게 풀 수 있지만, 당연히도 접근법 생각하는 게 쉽지 않았던 문제이다. 입력으로 주어지는 배열은 트리를 중위순회한 값이라는 걸 알 수 있다. 이것이 매우 중요하다. 중위순회임임을 통해서 적절한 부분 배열로 나누었을 때 (자식 노드) - (부모 노드) - (자식 노드) 의 패턴이 유지된다는 것을 유추해야 한다. 여기가 어렵다. 입력의 인덱스 중앙값은 항상 트리의 루트 노드이다 즉 전체 배열 기준으로 양 부분 배열 사이의 노드가 부모 노드라는 뜻이다. 그리고 부모 노드 기준으로 양쪽 부분배열로 나누었을 때, 그 부분 배열 또한 부모 노드와 자식 노드를 포함하는 서브 트리임을 알 수 있다. 큰 문제를 같은 패턴의 작은 문제로 나눌 수 있고, 서로 독립적이다. 그러므로 재귀를 이용한 풀이를 생각..
2024.02.25
no image
프로그래머스 여행경로 자바스크립트
어렵게 접근해서 조금 헤맸다. 일반적인 dfs 경로 탐색과 유사하지만 '알파벳 순이 빠른 경로' 라는 조건때문에 어렵게 생각했다. 프로그래머스 문제는 명쾌하게 풀리는 편이라고 생각한다. 그러므로 너무 복잡하게 접근하지 않는 편이 좋을 것 같다. 중복 경로(같은 티켓이 또 들어오는 경우)인 케이스와 첫번째 정렬 경로로 모두 방문할 수 없는 경우 이 2가지를 고려하는 게 핵심이다. function solution(tickets) { var answer = []; const map = []; const visited = []; for(let i = 0; i < tickets.length; i++){ if(map[tickets[i][0]] === undefined){ map[tickets[i][0]] = [];..
2024.02.20
no image
구름톤 챌린지 3주 차 문제 14 학습 일기
https://goor.me/wDFSjuDNjzXTTqH4A ​ import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken(..
2024.02.18
no image
구름톤 챌린지 4주 차 문제 18 학습 일기
https://goor.me/wDFSjuDNjzXTTqH4A ​ import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); Pair[][] arr = new Pair[n + 1][n + 1];..
2024.02.18
no image
구름톤 챌린지 3주 차 문제 13 학습 일기
https://goor.me/wDFSjuDNjzXTTqH4A ​ import java.io.*; import java.util.*; class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(st.nextToken()); int [][]map = new int[N][N]; int []ans..
2024.02.18

2206번 벽 부수고 이동하기와 매우 유사한 0-1bfs, 데이크스트라 문제이다.

두가지 해결법이 있는데,

0-1bfs로 접근한다면

 

dist배열에는 2차원 배열에서 해당 좌표까지 도착했을 때 벽을 부순 횟수를 기록하고

벽을 부순 횟수가 더 적을 때 deque에 삽입한다

 

우리는 최대한 벽을 부수지 않으면서 멀리 갈 수 있어야 한다.

때문에 벽을 부수지 않고 전진하는 경우 deque의 front에 삽입하고

벽을 부수는 경우 deque의 back에 삽입한다.

 

하지만 이건 내가 데이크스트라를 통해 문제를 해결한 이후에 본 풀이법이다.

 

데이크스트라로 접근하는 것이 더 이해가 쉬울 수 있다.

기존 데이크스트라는 탐색 시점 최단 거리의 노드를 queue에 넣고, 

방문한 노드 기준으로 다시 연결된 노드의 최단거리를 갱신시켜 주는데

 

이 문제에서는 기준을 최단거리가 아닌 벽을 부순 횟수로 바꾸면 된다.

 

const readline = require('readline');
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout
})

const input = [];
rl.on('line', (line)=>{
	input.push(line);
}).on('close', ()=>{

	const [m,n] = input[0].split(' ').map(Number);

	const map = Array.from(Array(n), () => Array(m).fill(0));

	for(let i = 0; i < n; i++){
		const arr = input[i+1].split('').map(Number);
		for(let j = 0; j < m; j++)
			map[i][j] = arr[j];
	}

	const dist = Array.from(Array(n), () => Array(m).fill(Infinity));
	const bfs = () => {
		const q = [];
		q.push([0,0,0]);

		while(q.length > 0){
			const [y_,x_,v] = q.shift();

			const a = [1,-1,0,0];
			const b = [0,0,-1,1];

			for(let i = 0; i < 4; i++){
				const y = y_ + a[i];
				const x = x_ + b[i];
				if(x >= 0 && x < m && y >= 0 && y < n){
					if(map[y][x] === 0 && dist[y][x] > v){
						dist[y][x] = v;
						q.push([y,x,v]);
					}
					else if (map[y][x] === 1 && dist[y][x] > v + 1){
						dist[y][x] = v + 1;
						q.push([y,x,v+1]);
					}
				}
			}
		}
	}

	bfs();
	if(dist[n-1][m-1] === Infinity)
		console.log(0)
	else
		console.log(dist[n-1][m-1]);

})

 

이 문제는 사실 정석으로 접근했다면 풀지 못했을 것이다. 운영체제 내용과 관련이 있는 흥미로운 문제이다.

스케쥴링은 필요한 자원을 적절히 할당하여 효율적으로 리소스를 활용하는 것이다.

페이징 기법

 

프로세스가 사용하는 메모리 공간을 잘게 나누어 비연속적으로 사용하는 기법이다.

프로세스 적재를 위해 연속된 메모리를 요구하지 않기 때문에 한정된 메모리 공간을 효율적으로 사용할 수 있다.

가상 메모리 공간의 단위를 page, 물리 메모리 공간을 frame 이라고 하고 둘의 크기는 같다.

하지만 물리 메모리는 한정적이기 때문에, 운영체제는 물리 메모리와 보조 저장공간의 swap 공간을 함께 활용하게 되는데,

이 때 참조한 페이지가 물리 메모리에 올라가 있지 않을 때(invalid) 참조하는 페이지를 교체해서 새롭게 물리 메모리에 적재해야 한다.

 

여기서 사용하는 것이 페이지 교체 알고리즘이다

 

페이지 교체 알고리즘 (Page Replacement Algorithm)

페이지 교체 알고리즘에는 여러가지가 있다.

 

FIFO - 가장 먼저 메모리에 올라온 페이지를 교체한다

LRU - 가장 오랫동안 사용되지 않은 페이지를 교체한다

 

그 중에서 OPT(Optimal) 알고리즘이 있다.

이름부터가 Optimal..

 

OPT(Optimal) 알고리즘

 

페이지를 교체 하려는 시점에서, 이후에 페이지가 참조될 시점이 가장 늦은 페이지를 교체한다.

즉 가장 오랫동안 사용되지 않을 페이지를 교체하는 것이다

 

그림으로 봤을 때, 첫번째 교체 시점에서 1이 가장 나중에 참조되기 때문에 1을 3으로 교체하고

4를 교체해야 하는 시점에서 뒤에 바로 나오는 2,3을 고려해 0을 교체한다.

다시 0을 교체해야 할 때는 이후 4는 참조되지 않기 때문에 4와 0 을 교체한다.

 

이는 가장 적은 page fault를 보장하는 최적화 알고리즘이다.

하지만 실제로는 운영체제 입장에서 앞으로 사용할 페이지를 알아야 하기 때문에 구현하기 어렵다. 

 

 

그러나,

이 문제에서는 용품의 사용 순서가 주어지기 때문에 우리는 미래를 알고있다.

가장 적은 교체, 가장 적은 페이지 부재를 보장하는 Optimal을 적용해서

교체가 필요한 시점을 기준으로 가장 늦게 사용하는 용품을 교체해주면 되겠다.

 

그래서 이 관련없어 보이는 얘기를 한 것이다.

운영체제 내용으로 조금 야매로 풀었지만 그래서 오히려 재밌는 문제다.

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

let input = [];

rl.on('line', function (line) {
  input.push(line);
}).on('close', function () {

	const [n,k] = input[0].split(' ').map(Number);

	const con = Array(n).fill(0);
	const arr = Array(k);

	const tmp = input[1].split(' ').map(Number);
	for(let i = 0; i < k; i++)
		arr[i] = tmp[i];

	const find_least = (idx) => {

		let tmp = -Infinity;
		let index;

		for(let i = 0; i < con.length; i++){
			let num = 0;
			for(let j = idx; j < arr.length; j++){
				if(arr[j] !== con[i])
					num++;
				else
					break;
			}
			if (tmp < num) {
					tmp = num;
					index = i;
				}
			}
			return index;
		}

	let answer = 0;
	for(let i = 0; i < k; i++){

		if(con.indexOf(arr[i]) !== -1)
			continue;

		const idx = con.indexOf(0);

		if(idx !== -1)
			con[idx] = arr[i];
		else{
			const index = find_least(i);
			con[index] = arr[i];
			answer += 1;
		}
	}

	console.log(answer);
})

 

 

 

 

 

 

 

입력 크기에서 힌트를 얻는 편이다.

n이 1000000까지 들어온다는 것은 시간복잡도 O(n)으로 해결해야 1초로 끊을 수 있다는 뜻이다.

그러므로 배열을 선형으로 한번만 순회하면서 해결할 수 있는 방법을 생각해 보는 것이 좋겠다.

 

 

배열이 계속 내림차순 이라면 오큰수는 나올 수 없다. 반대로 배열이 오름차순이라면 맨 마지막 수를 제외한 모든 수는 자신의 앞에 수를 오큰수로 가질 것이다.

이를 토대로 생각해보면, 현재 내가 순회하는 숫자를 기준으로 내림 차순이 이어지면 오큰수는 알 수 없고,

나보다 큰 수가 나왔다면, 그 수는 여태 오큰수를 알 수 없던 모든 수의 오큰수 '후보'가 되는 것이다.

 

이제 해결법을 떠올릴 수 있다. 내림차순이라면 현재 순회하는 수의 정보를(값, 인덱스) 잠시 저장해두고, 오름차순일 때는 저장된 값들 중에서 오큰수의 조건을 만족하는 값들을 갱신해주면 되는 것이다.

여기서 쉽게 떠올릴 수 있는 구조가 바로 스택 이다. 근데 난 문제를 풀 때는 생각이 안났고 최소힙이 생각났다.

최소힙에서 조건에 맞을때마다 요소룰 빼면서 오큰수를 갱신해주면 된다.

스택도 이와 동일하게 생각하면 된다.

 

const readline = require('readline');
const rl = readline.createInterface({
	input:process.stdin,
	output:process.stdout
})

const input = [];
rl.on('line', (line)=>{
	input.push(line);
}).on('close', () =>{

	const n = Number(input[0]);
	const arr = input[1].split(' ').map(Number);
	const ans = Array(n).fill(0);
	const q = [];


	for(let i = 0; i < n; i++){
		const j = i+1;
		if(j === n)
			break;
		if(arr[j] <= arr[i]){
			q.push([i, arr[i]]);
		}
		else{
			ans[i] = arr[j];
			q.sort((a,b) => a[1] - b[1])
			while(q.length > 0){
				if(q[0][1] < arr[j]){
					ans[q[0][0]] = arr[j];
					q.shift();
				}
				else
					break;
			}

		}
	}

	for(let i = 0; i < ans.length; i++){
		if(ans[i] === 0)
			ans[i] = -1;
	}


	console.log(ans.join(' '));

})

 

이 코드는 sort연산에서 O(nlogn)이 나오기 때문에 시간초과가 뜬다.

그래서 우선순위 큐를 직접 구현하면 통과가 된다. (코드가 길어서 올리진 않았다) 물론 오래 걸린다. 거의 꼴지 수준이다. 요소를 뺄 때 log(n)이 걸려서 그럴 것이다. 아마 몇없는 우선순위 큐로 통과한 사람중 하나인 것 같다. 그러니까 O(1)의 스택을 사용하도록 하자.

 

접근법을 알면 쉽게 풀 수 있지만, 당연히도 접근법 생각하는 게 쉽지 않았던 문제이다.

입력으로 주어지는 배열은 트리를 중위순회한 값이라는 걸 알 수 있다. 이것이 매우 중요하다.

중위순회임임을 통해서 적절한 부분 배열로 나누었을 때 (자식 노드) - (부모 노드) - (자식 노드) 의  패턴이 유지된다는 것을 유추해야 한다. 여기가 어렵다.

 

입력의 인덱스 중앙값은 항상 트리의 루트 노드이다 즉 전체 배열 기준으로 양 부분 배열 사이의 노드가 부모 노드라는 뜻이다.

그리고 부모 노드 기준으로 양쪽 부분배열로 나누었을 때, 그 부분 배열 또한 부모 노드와 자식 노드를 포함하는 서브 트리임을 알 수 있다.

큰 문제를 같은 패턴의 작은 문제로 나눌 수 있고, 서로 독립적이다. 그러므로 재귀를 이용한 풀이를 생각해낼 수 있다.

 

부모 노드는 항상 부분 배열의 중앙으로 확정이기 때문에, 부모 노드를 해당 높이의 트리(배열)에 넣은 후 이후 부모 노드 기준으로 다시 양쪽 배열로 분할한 후 재귀 함수를 호출한다.

let readline = require("readline");

let rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});

let input = [];

rl.on("line", (line)=> {
	input.push(line);
}).on("close", () => {

	const k = Number(input[0]);
	const arr = input[1].split(' ').map(Number);

	const ans = Array(k+1);
	for(let i = 0; i <= k; i++)
		ans[i] = '';


	const make = (arr, depth) => {

		if(depth > k || arr.length === 0)
			return;

		const mid = Math.floor(arr.length / 2);
		if(ans[depth].length === 0)
			ans[depth] += arr[mid].toString();
		else
		ans[depth] += ' ' + arr[mid].toString();
		const leftarr = arr.slice(0, mid);
		const rightarr = arr.slice(mid+1, arr.length);

		make(leftarr, depth + 1);
		make(rightarr, depth + 1);
	}

	make(arr, 1);

	console.log(ans.slice(1,ans.length).join('\n'))
})

 

 

 

 

어렵게 접근해서 조금 헤맸다.

일반적인 dfs 경로 탐색과 유사하지만 '알파벳 순이 빠른 경로' 라는 조건때문에 어렵게 생각했다.

프로그래머스 문제는 명쾌하게 풀리는 편이라고 생각한다. 그러므로 너무 복잡하게 접근하지 않는 편이 좋을 것 같다.

중복 경로(같은 티켓이 또 들어오는 경우)인 케이스와 첫번째 정렬 경로로 모두 방문할 수 없는 경우

이 2가지를 고려하는 게 핵심이다.

function solution(tickets) {
    
    var answer = [];
    
    const map = [];
    const visited = [];
    
    for(let i = 0; i < tickets.length; i++){
        if(map[tickets[i][0]] === undefined){
            map[tickets[i][0]] = [];
            visited[tickets[i][0]] = [];
        }
        map[tickets[i][0]].push(tickets[i][1]);
        visited[tickets[i][0]].push(0);
    }
    
    const dfs = (air, br, k) => {
        
        
        if(k === tickets.length + 1 && answer.length === 0) {
            answer = [...br];
            return;
        }
        
        if(answer.length > 0)
            return;

        const arr = map[air];
        if(arr === undefined)
            return;
        
        arr.sort();
        for(let i = 0; i < arr.length; i++){
            if(visited[air][i] === 0){
                visited[air][i] = 1;
                br[k] = arr[i];
                dfs(arr[i], br, k+1);
                visited[air][i] = 0;
            }
        }
    }

 

같은 티켓이 또 들어오는 경우가 있기 때문에,

방문때마다 visited를 일반적인 공항이름을 넣거나 하면 같은 티켓을 탐색할 수 없다.

때문에 visited를 map과 동일한 배열을 만들어서 방문 체크를 진행했다.

한 경로에 탐색이 끝나고 해당 경로로 모든 경로를 방문할 수 없을 때를 위해

탐색이 끝나면 visited를 다시 방문하지 않은 것으로 되돌린다.

 

import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		ArrayList<ArrayList<Integer>> arr = new ArrayList<>();
		for(int i =0; i <= N; i++){
			arr.add(new ArrayList<Integer>());
		}
		for(int i = 0; i < M; i++){
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr.get(a).add(b);
			arr.get(b).add(a);
		}
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		boolean []visited = new boolean[N+1];
		
		for(int i = 0; i < arr.get(K).size(); i++){
			pq.add(arr.get(K).get(i));
		}
		
		visited[K] = true;
		int ans = K;
		int cnt = 1;
		while (!pq.isEmpty()){
			int node = pq.poll();
			if(visited[node] == false){
				ans = node;
				cnt++;
				visited[node] = true;
				pq = new PriorityQueue<Integer>();
				for(int i = 0; i < arr.get(node).size(); i++){
						pq.add(arr.get(node).get(i));
				}
			}
		}
		System.out.print(cnt);
		System.out.println(" " + ans);
	}
}

 

행렬 탐색 문제이다. 본인 또한 대부분 사람들과 비슷하게 그래프 탐색 원툴이기 때문에 그리디, dp같은건 잘 못푼다. 그래서 탐색 위주로 풀었다.

시작 노드로부터 인접 노드로 방문하는데

  1. 한번 방문한 노드는 방문할 수 없고
  2. 방문할 수 있는 노드중에 번호가 가장 작은 노드로 이동한다.

번호가 작은 노드로 이동한다는 규칙에서 우선 순위 큐 를 활용하는 아이디어를 바로 낼 수 있다.

물론 구름 측에서 제시한 코드를 보니 일반 큐에 넣은 후 정렬을 이용함. 아무거나 해도 상관 없을 것이다.

다만 우선순위 큐를 활용한다면, 매번 방문 후 다음에 방문할 노드를 큐에 넣을 때, 큐를 초기화해줘야 하는데, 이를 위해서 new를 사용하면 메모리 할당이 많아져 속도가 느려질 수도 있겠다. 근데 난 그냥 했다.

그리고 그래프에서 간선의 존재 유무를 굳이 확인할 필요가 없다면 인접행렬보단 인접 리스트로 구현하는 것이 공간 복잡도와 탐색 속도 면에서 낫기 때문에 arraylist를 이용한 인접 리스트를 선택한다.

 

 

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Pair[][] arr = new Pair[n + 1][n + 1];
        for(int i=0; i<=n; i++){
            for(int j=0; j<=n; j++){
                arr[i][j] = new Pair();
            }
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            char c= st.nextToken().charAt(0);
            
            if(c == 'R'){
                for(int k=x;k<=n;k++)
                    arr[y][k].x += 1;
                
            } else if(c == 'L'){
                for(int k=1;k<=x;k++)
                    arr[y][k].x += 1;
                
            } else if(c == 'D'){
                for(int k=y;k<=n;k++)
                    arr[k][x].y += 1;
                
            } else if(c == 'U'){
                for(int k=1;k<=y;k++)
                    arr[k][x].y += 1;
             }
         }

         long ans=0;

         for(int i=1;i<=n;i++){
             for(int j=1;j<=n;j++){
                 ans+=arr[i][j].x*arr[i][j].y;
             } 
         }

         System.out.println(ans);
     }

     static class Pair{
         long y;
         long x;

         public Pair(){
             this.y=0;
             this.x=0;
          } 
      }
}

 

이 문제는 꽤 재밌었다.

탐색 + dp 문제

세로선 가로선이 교차하는 점의 개수를 구하면 되는데, 가로선끼리 세로선끼리는 겹치지 않는다.

그래서 2차원 배열로 맵을 만들고 각 칸마다 세로선과 가로선의 개수를 기록해준다.

이후에 세로선 개수 X 가로선 개수 를 누적합하면 정답이 나온다.

아까 공개된 정답 코드 봤는데 완벽하게 이해하지는 못했고 아마 비슷한 접근인 듯 한데, 정답 코드는 굳이 3차원 배열 써서 조건문 돌 때 마다 누적합까지 해줬고

나는 pair를 2차원 배열에 저장해서 세로선과 가로선을 기록했다.

이렇게 해서 네이버 페이 10000원을 벌었다.

 

 

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

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int [][]map = new int[N][N];
		int []ans = new int [32];
		
		Queue<Node> q = new LinkedList<>();
			
		int []dx = {-1, 1, 0, 0};
		int []dy = {0, 0, -1, 1};
		
		for(int i = 0; i <N; i++){
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++){
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int max = 0;
		int res = 0;
		
		for(int i = 0; i <N; i++){
			for(int j = 0; j < N; j++){
				int cnt = 0;
				if(map[i][j] != 0){
					cnt++;
					q.add(new Node(i, j));
					int num = map[i][j];
					map[i][j] = 0;
					while(!q.isEmpty()){
						Node node = q.poll();
						for(int k = 0; k <4; k++){
							int newi = node.i + dx[k];
							int newj = node.j + dy[k];
							if(newi >=0 && newi < N && newj >=0 && newj < N && map[newi][newj] == num){
								cnt++;
								q.add(new Node(newi, newj));
								map[newi][newj] = 0;
							}
						}
					}
					if (cnt >= K){
						ans[num] ++;
					}
				}
			}
		}
		for(int i =0; i<32; i++){
			if (ans[i] >= max){
				max = ans[i];
				res = i;
			}
		}
		System.out.println(res);
	}
}

class Node{
	int i;
	int j;
	
	Node(int i, int j){
		this.i = i;
		this.j = j;
	}
}

탐색 문제이다. bfs로 풀었다.

백준 10026 적록색약 문제와 유형이 비슷하다.

같은 정수가 상하 좌우로 k개 이상 인접해있다면 1개의 단지로 볼 수 있는데, 단지가 가장 많은 정수를 출력하면 된다.

같은 수가 3개 이상 인접해있다면 단지로 볼 수 있다면

1 1 1 2

2 2 1 3

1 1 3 3

이 예시에서는 1단지 1개 2단지 0개 3단지 1개 이다.

탐색을 통해 인접 행렬을 탐색하고 같은 수가 k개 이상 붙어있다면 단지의 수를 1개 늘려주면 된다.

주의해야할 점이 있다면 단지의 갯수만 따져야한다. 단지 + 숫자의 갯수까지 따지면 안된다.

예를 들어

1 1 1 1 1

1 1 1 1 3

1 1 1 3 3

3 3 3 1 1

이런 예시가 있다면 1단지 1개 3단지 2개로 3을 출력해야 한다. 1이 많다고 출력하면 안된다.

그리고 이거 리뷰 쓰면 네이버 포인트 5000원 준다.