이코테 0724 - 구현 기출문제2)

HyeJi9908·2022년 7월 24일
0

[JAVA] ThisIsCodingTest

목록 보기
10/12

📚 뱀(삼성 기출)

✔ 클래스 생성

  • X시간 뒤 C방향으로 방향 전환 리스트
  • 좌표 y,x가 멤버인 클래스 생성

✔ 뱀의 몸통이 있는 좌표들을 표현할 큐

  • 사과가 있을 때, 뱀의 마지막 좌표(꼬리)부분이 생기는 거 -> 큐에 offer
  • 사과가 없을때, 뱀의 꼬리부분이 이동 -> 큐의 첫번째 원소 poll

✔ 처음에는 오른쪽을 보고 있으므로 동->남->서->북 순으로 방향 리스트 초기화
d = {{0,1},{1,0},{0,-1},{-1,0}}
: 'R'이면 dir++ / 'L'이면 dir-- / 직진이면 현재 dir값 그대로해서
ny= y + d[dir] / nx= x+ d[dir]

✔ BFS 살짝

import java.util.*;

class TurnDir{
	public TurnDir(int time, char dir) {

		this.time = time;
		this.direction = dir;

	}

	public char getDirection() {
		return this.direction;
	}

	public int getTime() {
		return this.time;
	}

	private int time;
	private char direction;
}

class Position{
	
	private int y,x;
	public Position(int y,int x) {
		this.y = y;
		this.x = x;
	}
	public int getY() {
		return this.y;
	}
	public int getX() {
		return this.x;
	}
}

public class Java0724_1 {
	
	public static int n,k,l;
	public static int[][] arr;
	public static ArrayList<TurnDir> plan = new ArrayList<TurnDir>();
	// 회전 시간, 방향 정보 

	public static int[][] d = {{0,1},{1,0},{0,-1},{-1,0}};
	// 동,남,서,북
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		k = sc.nextInt();
 
		arr = new int[n][n];
		for(int i=0;i<k;i++) 
		{
			int y = sc.nextInt()-1; // 문제에서 주는 입력값은 좌표 시작점 (1,1)임
			int x = sc.nextInt()-1;
			arr[y][x] = 1; // 사과가 있는 위치는 1을 가짐
		}
		
		l = sc.nextInt();
		for(int i=0;i<l;i++) {
			int time = sc.nextInt();
			//sc.nextLine(); // nextInt 다음 nextLine할 때만
			
			char str = sc.next().charAt(0);
			
			plan.add(new TurnDir(time,str));
		}
		
		System.out.print(simulate());

	}


	private static int simulate() {
		
		int y=0,x=0;
		arr[y][x] = 2; 
		// 뱀이 있는 위치 2/ 사과가 있는 위치/ 그 외 0으로 정하자

		int dir =0; // 방향 인덱스
		int t=0;
		int idx=0; // ArrayList plan의 인덱스
		
		Queue<Position> q = new LinkedList<>();
		q.offer(new  Position(y, x));
		
		while(true) {
			
			int ny = y+d[dir][0];
			int nx = x+d[dir][1];
			
			if(nx>=0&&ny>=0&&ny<n&&nx<n&&arr[ny][nx]!=2) {
				
				// 사과가 없다면 이동 후 꼬리가 위차한 좌표는 큐에서 없애기
				if(arr[ny][nx]==0) {
					arr[ny][nx]=2;
					q.offer(new Position(ny, nx));
					Position tail = q.poll();
					arr[tail.getX()][tail.getY()] = 0;
				}
				else if(arr[ny][nx]==1) {
					// 사과가 있으면 이동 후에 큐에 이동한 좌표 넣기
					arr[ny][nx] = 2;
					q.offer(new Position(ny, nx));
				}
				
			}
			else { // 벽이나 몸에 부딪혔다면
				t++;
				break;
			}
			
			x = nx; y = ny; // 다음 위치로 이동
			t++;
			
			if(idx<l&&plan.get(idx).getTime() == t) {
				dir= turn(dir,plan.get(idx).getDirection());
				idx++;
			}
		}
		
		return t;
	}


	public static int turn(int dir,char direction) {
		if(direction == 'L') 
			dir = (dir==0)? 3:dir-1;
		else
			dir = (dir+1)%4;
		
		return dir;
	}
}

📚 기둥과 보 설치(카카오 기출)

✔ 각 기둥/보 설치하고 구조물자체!!를 검사하고 불가능하면 해당 기둥/보 삭제하기/ 각 기둥/보 삭제하고 구조물 자체!!를 검사하고 불가능하면 해당 기둥/보 다시 설치하기!
✔ 설치하기 전 해당 기둥/보 설치가 가능한지 알아보고 가능하면 새로운 2차원 배열에 하나씩 설치하는 방법은 예외처리가 많음. 위의 방법이 비효율적이더라도 build_frame의 최대수가 1000이기에 가능함

  • 빠른 이해를 위한 파이썬 코드
# 현재 설치된 구조물이 '가능한' 구조물인지 확인하는 함수
def possible(answer):

    for x, y, stuff in answer:
    
        if stuff == 0: # 설치된 것이 '기둥'인 경우
            # '바닥 위' 혹은 '보의 한쪽 끝 부분 위' 이거나
            if y == 0 or [x - 1, y, 1] in answer or [x, y, 1] in answer:
                continue
            # '다른 기둥 위'라면 정상
            if [x, y - 1, 0] in answer:
                continue
                
            return False  
            
        elif stuff == 1: # 설치된 것이 '보'인 경우
            # '한쪽 끝부분이 기둥 위' 이거나
            if [x, y - 1, 0] in answer or [x + 1, y - 1, 0] in answer:
                continue
            # '양쪽 끝부분이 다른 보와 동시에 연결'이라면 정상
            if [x - 1, y, 1] in answer and [x + 1, y, 1] in answer:
                continue
                
            return False  
            
    return True

def solution(n, build_frame):
    answer = []
    
    for frame in build_frame:  
        x, y, stuff, operate = frame
        
        if operate == 0: # 삭제하는 경우
            answer.remove([x, y, stuff]) # 일단 삭제를 해본 뒤에
            if not possible(answer): # 가능한 구조물인지 확인
                answer.append([x, y, stuff]) # 가능한 구조물이 아니라면 다시 설치

		if operate == 1: # 설치하는 경우
            answer.append([x, y, stuff]) # 일단 설치를 해본 뒤에
            if not possible(answer): # 가능한 구조물인지 확인
                answer.remove([x, y, stuff]) # 가능한 구조물이 아니라면 다시 제거
                
    return sorted(answer) # 정렬된 결과를 반환
    
  • 자바 코드
import java.util.*;

class NodeXYStuff implements Comparable<NodeXYStuff>{
	public NodeXYStuff(int x,int y, int stuff) {
		this.x = x;
		this.y = y;
		this.stuff = stuff;
	}

	private int x,y,stuff;

	public int getX() {
		return this.x;
	}

	public int getY() {
		return this.y;
	}

	public int getStuff() {
		return this.stuff;
	}
	
	// x,y,stuff 순서대로 오름차순 정렬
	@Override
	public int compareTo(NodeXYStuff o) {
		
		// 우선순위 3, x도 같고 y도 같을 때 : stuff가 기준
		if(this.x==o.x&&this.y==o.y) 
			return Integer.compare(this.stuff, o.stuff);
		
		// 우선순위 2, x가 같을 때 : y가 기준
		if(this.x==o.x)
			return Integer.compare(this.y, o.y);
		
		// 우선순위 1 , x기준
		return Integer.compare(this.x, o.x);
	}
}

public class Java0724_2 {
    public int[][] solution(int n, int[][] build_frame) {
    	
    	ArrayList<ArrayList<Integer>> answer = new ArrayList<ArrayList<Integer>>();
    	
    	for(int[] b:build_frame) {
    		
    		int x = b[0];
    		int y = b[1];
    		int stuff = b[2]; // 기둥/보
    		int operate = b[3]; // 설치/삭제
    		
    		if(operate==0) { 	// 삭제하는 경우// 일단 해당 stuff 삭제하기
    			int idx =0;
    			
    			// ArrayList에서 해당 명령이 있는 인덱스 찾기
    			for(int i=0;i<answer.size();i++) {
    				if (x==answer.get(i).get(0)&& y==answer.get(i).get(1) &&stuff==answer.get(i).get(2) )
    					idx = i;	
    			}
    			
    			ArrayList<Integer> erased = answer.get(idx);
    			answer.remove(idx);
    			
    			if(!possible(answer))	// 불가능한 구조물이라면 다시 설치
    				answer.add(erased);
    		}
    		else {				// 설치하는 경우 // 일단 설치
    			
    			ArrayList<Integer> inserted = new ArrayList<Integer>();
    			inserted.add(x);
    			inserted.add(y);
    			inserted.add(stuff);
    			
    			answer.add(inserted); // 왜 굳이 클래스 객체로 안넣고 이차원 리스트로 이렇게 한거지?
    								  // 삭제하는 경우 삭제를 하고 막상 불가능한 구조물이되면
    								  // 그 stuff를 찾아 다시 추가해야하는데, 
    								  // 이때 인덱스로 찾을 수 있도록 리스트를 사용
    			
    			if(!possible(answer)) // 불가능한 구조물이라면
    				answer.remove(answer.size()-1);	// 삭제
    			
    		}
    	}
    	
    	//  x좌표 기준 오름차순 정렬 + x좌표가 같을 경우 y좌표 기준으로 오름차순 정렬
        ArrayList<NodeXYStuff> ans = new ArrayList<NodeXYStuff>();
        for(int i=0;i<answer.size();i++)
        	ans.add(new NodeXYStuff(answer.get(i).get(0),answer.get(i).get(1),answer.get(i).get(2)));
    	
        Collections.sort(ans);
    	
        // 배열로 바꿔 반환
        int[][] res = new int[ans.size()][3];
        for(int i=0;i<ans.size();i++) {
        	res[i][0] = ans.get(i).getX();
        	res[i][1] = ans.get(i).getY();
        	res[i][2] = ans.get(i).getStuff();
        }
        
        return res;
    }

	public boolean possible(ArrayList<ArrayList<Integer>> answer) {
		
		for(int i=0;i<answer.size();i++) {
			int x= answer.get(i).get(0);
			int y= answer.get(i).get(1);
			int stuff = answer.get(i).get(2);
			
			if(stuff ==0) { 		// 기둥일 때
				boolean check = false;
				
				if(y==0) check = true; // 바닥 위일 때 정상
				
				for(int j=0;j<answer.size();j++) {
					
					// 보의 끝점 끝부분 위 일때 정상 
					if(x-1==answer.get(j).get(0)&& y==answer.get(j).get(1)&& answer.get(j).get(2)==1)
						check = true;
					// 보의 시작점 끝부분 위 일때 정상
					if(x==answer.get(j).get(0)&& y==answer.get(j).get(1)&& answer.get(j).get(2)==1)
						check = true;
					// 다른 기둥 위 일때 정상
					if(x==answer.get(j).get(0)&& y-1==answer.get(j).get(1)&& answer.get(j).get(2)==0)
						check = true;
				}
				
				if(!check) return false;
			}
			else {				// 보 
				boolean check = false;
				boolean left = false;
				boolean right = false;
				
				for(int j=0;j<answer.size();j++) {
					
					// 보의 시작점이 기둥 위일 때 정상
					if(x==answer.get(j).get(0)&&y-1==answer.get(j).get(1)&&answer.get(j).get(2)==0)
						check = true;
					// 보의 끝점이 기둥 위일때 정상
					if(x+1==answer.get(j).get(0)&&y-1==answer.get(j).get(1)&&answer.get(j).get(2)==0)
						check = true;
					// 보의 시작점이 다른 보의 끝점과 연결되었을 때 정상
					if(x-1==answer.get(j).get(0)&&y==answer.get(j).get(1)&&answer.get(j).get(2)==1)
						left = true;
					// 보의 끝점이 다른 보의 시작점과 연결되었을 때 정상
					if(x+1==answer.get(j).get(0)&&y==answer.get(j).get(1)&&answer.get(j).get(2)==1)
						right = true;
				}
				
				if(left&&right) check = true;
				if(!check) return false;
				
			}
		}
		return true;
	}
}

0개의 댓글