> 문제
문제 : [리틀 프렌즈 사천성]
문제풀이
Map을 활용하였는데,
board의 문자를 Map의 key값으로 세팅하고, board의 문자가 작은 값부터 수행해주기 위해, TrieMap을 활용하였다.
작은 문자부터 조건에 맞는다면 차례대로 문자를 삭제해주었다.
한 쌍의 타일을 A와 B라고 정의할 때, 총 네가지 케이스를 가질 수 있다. AB가 수평일때, 수직일때, A가 B보다 왼쪽 위에 있을때, A가 B보다 오른쪽 위에 있을때의 경우를 그림으로 그려서 풀이하였다.
소스는 다음과 같다.
package level3;
import java.util.*;
class Solution {
static class Node implements Comparable<Node>{
int x,y;
Node(int x, int y){
this.x = x;
this.y = y;
}
@Override
public int compareTo(Node n){
if(this.x < n.x) return 1;
else if(this.x == n.x){
if(this.y < n.y) return 1;
else return -1;
}else return -1;
}
}
static class Pair{
List<Node> pair;
Pair(){
pair = new ArrayList<>();
}
public void add(Node node){
pair.add(node);
}
}
static public String solution(int m, int n, String[] board) {
char[][] boardtoChar = new char[m][n];
for(int i=0; i<m; i++) {
boardtoChar[i] = board[i].toCharArray();
}
M = m;
N = n;
Map<Character, Pair> map = new TreeMap<>();
Pair pair;
for(int i=0; i<boardtoChar.length; i++){
for(int j=0; j<boardtoChar[i].length; j++){
char c = boardtoChar[i][j];
if(c == '*' || c == '.') continue;
if(map.get(c) == null){
pair = new Pair();
pair.add(new Node(i,j));
map.put(c, pair);
}else{
map.get(c).add(new Node(i,j));
}
}
}
StringBuilder sb = new StringBuilder();
while(!map.isEmpty()){
boolean flag = false;
Iterator<Character> it = map.keySet().iterator();
while(it.hasNext()){
char c = it.next();
pair = map.get(c);
if(isOk(c,pair,boardtoChar)){
for(int i=0; i<pair.pair.size(); i++) {
Node node = pair.pair.get(i);
boardtoChar[node.x][node.y] = '.';
}
sb.append(c);
map.remove(c);
flag = true;
break;
}
}
if(!flag) return "IMPOSSIBLE";
}
return sb.toString();
}
static int M,N;
static boolean check(int x, int y){
if(x>=0 && x<M && y>=0 && y<N)
return true;
else return false;
}
static boolean isOk(char c, Pair pair, char[][] boardtoChar){
Node A = pair.pair.get(0);
Node B = pair.pair.get(1);
int dx, dy;
if(A.x == B.x){ // A보다 B가 y값이 크다.
dx = A.x;
dy = A.y;
while(check(dx,dy+1)
&& (boardtoChar[dx][dy+1] == '.' || boardtoChar[dx][dy+1] == c)){
dy ++;
if((dx == B.x && dy == B.y) && boardtoChar[dx][dy] == c) return true;
}
}else{ // A보다 B가 x값이 크다.
if(A.y == B.y){
dx = A.x;
dy = A.y;
while(check(dx+1,dy)
&& (boardtoChar[dx+1][dy] == '.' || boardtoChar[dx+1][dy] == c)){
dx ++;
if((dx == B.x && dy == B.y) && boardtoChar[dx][dy] == c) return true;
}
}else if(A.y < B.y){ // A보다 B가 x,y값이 크다.
// A에서 오른쪽으로 먼저 이동했을 경우.
dx = A.x;
dy = A.y;
while(check(dx,dy+1)
&& (boardtoChar[dx][dy+1] == '.' || boardtoChar[dx][dy+1] == c)
&& dy+1 <= B.y){
dy ++;
}
if(dy == B.y){
while(check(dx+1,dy)
&& (boardtoChar[dx+1][dy] == '.' || boardtoChar[dx+1][dy] == c)){
dx ++;
if((dx == B.x && dy == B.y) && boardtoChar[dx][dy] == c) return true;
}
}
// A에서 밑으로 먼저 이동했을 경우.
dx = A.x;
dy = A.y;
while(check(dx+1,dy)
&& (boardtoChar[dx+1][dy] == '.' || boardtoChar[dx+1][dy] == c)
&& dx+1 <= B.x){
dx ++;
}
if(dx == B.x) {
while(check(dx,dy+1)
&& (boardtoChar[dx][dy+1] == '.' || boardtoChar[dx][dy+1] == c)){
dy ++;
if((dx == B.x && dy == B.y) && boardtoChar[dx][dy] == c) return true;
}
}
}else{ // A보다 B가 x크지만, y는 작다.
// A 에서 왼쪽으로 먼저 이동했을 경우.
dx = A.x;
dy = A.y;
while(check(dx,dy-1)
&& (boardtoChar[dx][dy-1] == '.' || boardtoChar[dx][dy-1] == c)
&& dy-1 >= B.y){
dy --;
}
if(dy == B.y){
while(check(dx+1,dy)
&& (boardtoChar[dx+1][dy] == '.' || boardtoChar[dx+1][dy] == c)){
dx ++;
if((dx == B.x && dy == B.y) && boardtoChar[dx][dy] == c) return true;
}
}
// A에서 밑으로 먼저 이동했을 경우.
dx = A.x;
dy = A.y;
while(check(dx+1,dy)
&& (boardtoChar[dx+1][dy] == '.' || boardtoChar[dx+1][dy] == c)
&& dx+1 <= B.x){
dx ++;
}
if(dx == B.x) {
while(check(dx,dy-1)
&& (boardtoChar[dx][dy-1] == '.' || boardtoChar[dx][dy-1] == c)){
dy --;
if((dx == B.x && dy == B.y) && boardtoChar[dx][dy] == c) return true;
}
}
}
}
return false;
}
}
문제 출처 : Programmers
PREVIOUS[프로그래머스] Level4 - 도둑질