개발 블로그

4
123 1 1
356 1 0
327 2 0
489 0 1

2

접근 방법

완전 탐색으로 접근했다. 

답이 될 수 있는 숫자 조건은 000 ~ 999 중에 아래 두 조건을 만족해야 한다.  만족하지 않으면 배열 값을 -1 로 표시한다. 

1) 모두 다른 숫자로 구성되어 있어야 함

2) 숫자에 0이 들어가면 안됨

그 후 반복문을 돌면서 스트라이크, 볼 갯수를 카운트하고

카운트 한 스트라이크, 볼 갯수가 처음에 입력한 스트라이크/볼 수와 일치하면

그 인덱스의 배열 값을 +1 한다. (ex. 처음 입력한 숫자가 123 1 1 이고, 비교 대상이 324이면 1strike, 1ball을 만족하므로 arr[324]++)

그리고 마지막에 arr[i]의 값이 N과 동일하면, 즉 N번을 물어봤기 때문에 그 물어본 횟수만큼 테스트를 통과했으면(스트라이크, 볼 갯수가 일치했으면) 그 i는 후보가 된다. 그 i가 몇개인지 카운트 하면 이 문제의 답을 구할 수 있다. 

[반례]

입력
2
123 0 0
456 0 0

정답
6

import java.util.*;

public class BOJ_2503_숫자야구 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int ans = 0;

//        Integer[] arr = new Integer[1000];
        int[] arr = new int[1000];
        for (int i = 123; i <= 987; i++) {  //서로 다른 숫자 세개로 구성하므로
            String str = Integer.toString(i);   //각 자리수 비교하기 위해 형변환

            if (str.charAt(0) == str.charAt(1) || str.charAt(0) == str.charAt(2) || str.charAt(1) == str.charAt(2)
                ||str.charAt(0)=='0' || str.charAt(1)=='0' ||str.charAt(2)=='0') {  //서로 다른 숫자로 구성되지 않았으면 -1로 지정
                arr[i] = -1;
            }
        }
        //ArrayList<String> strNumList = new ArrayList<>();
        String strNum;
        //ArrayList<Integer> strikeList = new ArrayList<>();
        //ArrayList<Integer> ballList = new ArrayList<>();
        int strike;
        int ball;
        for (int i = 1; i <= N; i++) {       //N : 민혁이가 영수에게 질문한 횟수
            strNum = sc.next();
            //strNumList.add(strNum);
            strike = sc.nextInt();
            //strikeList.add(strike);
            ball = sc.nextInt();
            //ballList.add(ball);

            int strikeCnt = 0;
            int ballCnt = 0;

            for (int idx = 123; idx <= 987; idx++) {    //반복문 돌면서 strike, ball 검사
                if (arr[idx] == -1) continue;
                //System.out.print(arr[idx] + " ");
                int passCnt = 0;
                //strike 검사
                strikeCnt = 0;
                String strIdx = Integer.toString(idx);
                for (int j = 0; j < 3; j++) {
                    if (strNum.charAt(j) == strIdx.charAt(j)) strikeCnt++;
                }

                //strike 수는 맞았으니 Ball 검사
                ballCnt = 0;
                for (int p = 0; p < 3; p++) {
                    for (int q = 0; q < 3; q++) {
                        if ((strNum.charAt(p) == strIdx.charAt(q)) && (p != q)) {
                            ballCnt++;
                        }
                    }
                }
                if ((strike != strikeCnt) || ball != ballCnt) {
                    arr[idx] = -1;
                    continue;
                }

				//통과된 횟수 카운트
                if ((strike == strikeCnt) && (ball == ballCnt)) {
                    arr[idx]++;
                }
            }

        }

        for (int i = 123; i <= 987; i++) {

            if (arr[i] != -1 && arr[i] == N) {	//물어본 횟수만큼 다 만족했으면 그 숫자는 답
                ans++;
               // System.out.println(i);
            }
        }
        System.out.println(ans);

    }
}

문제 링크 : https://www.acmicpc.net/problem/16234

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

접근 방법

각 땅 (r,c) 에 대해 무한루프를 돌면서 

     - BFS를 이용해 국경선을 서로 열 수 있는 땅을 Queue에 다 넣고, BFS 탐색이 끝나면 인구이동을 해준다. 

     - 모든 칸에 대해 인구이동 여부를 탐색 했으면 다시 처음으로 돌아가서 visited를 초기화 시킨 후 재 탐색한다. (만약 이 단계에서 탐색이 끝났을 때 인구이동이 한 번도 발생하지 않았다면 무한루프를 종료시킨다.)

import java.util.*;

class Pair16234{
	Integer r, c;
	public Pair16234(Integer _r, Integer _c) {
		this.r = _r;
		this.c = _c;
	}
	public int getRow() {
		return this.r;
	}
	public int getCol() {
		return this.c;
	}
	
}
public class SM_BOJ16234_인구이동 {

	static int N, L, R, answer;
	static int[][] map, visited; 
	static int[] dr,dc;

	static boolean chk(int a, int b) {
		int sub = Math.abs(a-b);
		if(L <= sub && sub <=R) return true;
		else return false;
	}
	
	static boolean BFS(int r, int c) {
		
		Queue<Pair16234> que = new LinkedList<Pair16234>();
		ArrayList<Pair16234> vec = new ArrayList<Pair16234>();
		int sum = 0;
		
		Pair16234 p = new Pair16234(r,c);
		que.add(p);
		vec.add(p);
		sum = map[r][c];
		
		while(!que.isEmpty()) {
			Pair16234 pair = que.poll();
			int cr = pair.getRow();
			int cc = pair.getCol();
			
			visited[cr][cc] = 1;
			
			for(int i = 0; i<4; i++) {
				int nr = cr + dr[i];
				int nc = cc + dc[i];
				if(nr<1 || nr>N || nc<1 || nc>N || visited[nr][nc]==1) continue;
				
				if(chk(map[cr][cc], map[nr][nc])) {
					visited[nr][nc] = 1;
					Pair16234 p_next = new Pair16234(nr,nc);
					que.add(p_next);
					vec.add(p_next);
					sum += map[nr][nc];
				}
			}
		}
		
		if(vec.size()==1) {
			visited[vec.get(0).getRow()][vec.get(0).getCol()] = 0;
			return false;
		}
		else {
			int avg = sum / vec.size();
			for(int i = 0; i<vec.size(); i++) {
				int row = vec.get(i).getRow();
				int col = vec.get(i).getCol();
				map[row][col] = avg;
			}
			return true;
		}
		
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		dr = new int[4];
		dc = new int[4];
		dr[0] = -1; dr[1] = 0; dr[2] = 1; dr[3] = 0;
		dc[0] = 0; dc[1] = 1; dc[2] = 0; dc[3] = -1;

		N = sc.nextInt();
		L = sc.nextInt();
		R = sc.nextInt();
		
		map = new int[51][51];
		visited = new int[51][51];
		for(int i = 1; i<=N; i++) {
			for(int j = 1; j<=N; j++) {
				map[i][j] = sc.nextInt();
				visited[i][j] = 0;
			}
		}
		
		answer = 0;

		int cnt = 0;	
		while(true) {
			
			if(cnt==N*N) break;
			cnt = 0;
			
			boolean flag = false;
			
            //인구 이동 끝나고 초기화 
			for(int r = 1; r<=N; r++) {
				for(int c = 1; c<=N; c++) {
					visited[r][c] = 0;
				}
			}
			
			for(int i = 1; i<=N; i++) {
				for(int j = 1; j<=N; j++) {

					if(visited[i][j]==0) {
						boolean res = BFS(i,j);		//국경선 열렸으면 true 
						if(res) {
							flag = true;
						}					
						else cnt++;
					}
				}
			}
			
			if(flag) answer++;
		}
		System.out.println(answer);
	}

}

문제 링크 : www.acmicpc.net/problem/16927

문제

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 10^9
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 108

접근 방법

nanyoungkim.tistory.com/78

문제와 동일한데, 조건 하나가 다르다. R의 범위가 1000에서 10^9 까지 늘어났다는 것이다. 

예를 들어보자.

여기서 map[0][0]이 1번 전진하면 map[1][0]으로 간다. 그런데 1번 전진이 아니라 13번, 25번 전진해도 map[1][0]으로 간다. 

즉,

1 mod 12

13 mod 12

25 mod 12

는 모두 1임을 알 수 있는데, 여기서 modulus 12는 가장 바깥쪽 박스의 칸 수가 된다. 이는 2*N + 2*M -4 로 구할 수 있다. (-4는 각 모서리의 수들이 반복돼서 더해준 것을 뺀 것이다.)

박스가 하나씩 안 쪽으로 들어갈 때마다 가로, 세로의 길이는 각각 2씩 감소하는 것을 알 수 있다.

배열 돌리기 1번에서는 "각 박스에 대해 1칸 전진" 을 R번 반복 했다면, 

배열 돌리기 2번에서는 "박스 한개에 대해 R번 전진" 을 박스 개수만큼 반복해줬다.

결론은 박스 개수만큼 반복하는데, 한 박스마다 회전할 수를 R이 아닌 "R mod 박스칸수" 로 지정해서 R이 10^9처럼 큰 수가 들어와도 효율적으로 돌아갈 수 있게 했다.

//21.03.10
//next가 배열 범위 넘어가면 dr[],dc[]의 인덱스 증가
//top, right, bottom, left 순서로 칸 이동시킴
//(시계 반대방향으로 전진해야하므로 dr,dc의 인덱스는 오,아,왼,위 순서)

#include <iostream>
#include <algorithm>


using namespace std;

int map[301][301];
int N,M,R;

//오, 아, 왼, 위
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};

void rotate(int start, int len){
    
    int r = R%len;			//len은 박스의 총 칸 수
    for(int i = 0; i<r; i++){   //r칸 전진
        
        int startVal = map[start][start];
        int r = start;
        int c = start;
        
        int k = 0;
        while(k<4){
            
            int nr = r + dr[k];     //map[nr][nc]는 옮길 대상임 (map[r][c]로 옮겨야 함)
            int nc = c + dc[k];
            
            if(nr==start && nc==start) break;
            if(start<=nr && nr<N-start && start<=nc && nc<M-start){
                
                //차례로 시계 반대방향으로 옮김
                map[r][c] = map[nr][nc];
                r = nr;
                c = nc;
                
            }
            else{       //다음에 옮길 칸이 배열 범위 넘어가버리면 해당 라인은 다 옮긴거라서 k 증가
                k++;
            }
        }
        map[start+1][start] = startVal; //처음에 시작지점 빼놨던거 마지막에 빈 자리에 넣어줌.
        
    }

    
}


int main(){
    
    cin >> N >> M >> R;
        
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cin >> map[i][j];
        }
    }
    
    int cnt = min(N,M)/2;       //  박스 수


    int n=N, m=M;
    
    for(int i = 0; i<cnt; i++){ //반복문 1번에,  박스 1개가 R만큼 전진함
            //시작 지점
        rotate(i, 2*n + 2*m -4);
        n-=2;	//박스 안으로 들어갈때마다 가로,세로 2씩 줄어듦.
        m-=2;
        
    }
    
    
    
    
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cout << map[i][j] << " ";
        }cout <<"\n";
    }
    
    
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/16926

문제

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 1,000
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 108

접근 방법

모든 박스에 대해서 시계 반대 방향으로 요소를 1칸씩 이동시키며, 이를 R번 반복한다.

여기서 박스는

이렇게 두개이다.

박스의 시작지점은 map[0][0] -> map[1][1] -> map[2][2]...... map[박스수][박스수] 이런 순으로 가게 된다.

박스의 개수는 min(N,M) / 2 개이며 문제의 조건에서 min(N,M) mod 2=0이라고 했으므로 둘 중하나는 짝수이고 (3x3) 이나 (5x5) 같은 경우는 고려하지 않아도 된다.

먼저 각 박스에 대해서 1칸 시계 반대방향으로 이동하는 걸 생각해보자.  1) map[0][0]을 시작지점으로 잡는다.

2) Top : 왼쪽으로 이동한다. 

next 칸이 now칸의 오른쪽에 있으므로 dr[],dc[]는 오른쪽.

3) Right : 위쪽으로 이동한다.

next 칸이 now칸의 아래쪽에 있으므로 dr[],dc[]는 아래.

4) Bottom : 오른쪽으로 이동한다.

next 칸이 now칸의 왼쪽 있으므로 dr[],dc[]는 왼쪽.

5) Left : 아래쪽으로 이동한다.

next 칸이 now칸의 위에 있으므로 dr[],dc[]는 위.

전체적인 로직은 위와 같으며, next 칸이 시작점으로 돌아왔을 때 반복을 멈추고, 남은 자리에 1)에서 저장했던 값을 넣어주면 된다.

//21.03.10
//next가 배열 범위 넘어가면 dr[],dc[]의 인덱스 증가
//top, right, bottom, left 순서로 칸 이동시킴
//(시계 반대방향으로 전진해야하므로 dr,dc의 인덱스는 오,아,왼,위 순서)

#include <iostream>
#include <algorithm>


using namespace std;

int map[301][301];
int N,M,R;

//오, 아, 왼, 위
int dr[4] = {0,1,0,-1};
int dc[4] = {1,0,-1,0};

void rotate(int box){
    
    for(int i=0; i<box; i++){   //박스수만큼 반복(1칸 전진)(시작점은 start, start+1, start+2..)
        int startVal = map[i][i];       //각 박스 시작은 [0][0] -> [1][1] -> [2][2]...
        int r = i;
        int c = i;
        
        int k = 0;
        while(k<4){
            
            int nr = r + dr[k];     //map[nr][nc]는 옮길 대상임 (map[r][c]로 옮겨야 함)
            int nc = c + dc[k];
            
            if(nr==i && nc==i) break;
            if(i<=nr && nr<N-i && i<=nc && nc<M-i){
                
                //차례로 시계 반대방향으로 옮김
                map[r][c] = map[nr][nc];
                r = nr;
                c = nc;
                
            }
            else{       //다음에 옮길 칸이 배열 범위 넘어가버리면 해당 라인은 다 옮긴거라서 k 증가
                k++;
            }
        }
        map[i+1][i] = startVal; //처음에 시작지점 빼놨던거 마지막에 빈 자리에 넣어줌.
     
    }
 
    
}


int main(){
    
    cin >> N >> M >> R;
        
    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cin >> map[i][j];
        }
    }
    
    int cnt = min(N,M)/2;       //  박스 수
    
    for(int i = 0; i<R; i++){       //반복문 한번에 1칸 전진하는것. 총 R칸 전진
        rotate(cnt);
    }


    for(int i = 0; i<N; i++){
        for(int j = 0; j<M; j++){
            cout << map[i][j] << " ";
        }cout <<"\n";
    }
    
    
    
    return 0;
}

참고 : 4ngeunlee.tistory.com/219