삼성전자 코딩테스트(코테) 구현 모듈 (공유)

공부하면서, 삼성이 좋아하년 여러 구현 모듈들을 정리했다. 해당 모듈들은 Java로 구현되어 있다. 문제 제목은 모두 코드트리의 삼성기출문제를 기준으로 하였음을 명시한다. 

 

https://www.codetree.ai/training-field/frequent-problems/company/samsung/problems

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 [구현모듈]

 

1. 회전시키기 90도 방향으로 좌표 또는 일부분 회전하기, 반시계방향, 시계방향 모두

   - 코드트리에서의 '메이즈러너', '예술성' 문제 등 다양한 곳에서 일부 좌표를 90도 회전하는 문제가 나온다. 

int N=5;
int[][] map = new int[N][N];
for(int i=0; i<5; i++) {
    map[i][0]=1;
}

//기존에 map이 있다고 가정.
int start_x = 0, end_x = N;
int start_y = 0, end_y = N;

//90도 시계방향 회전
int[][] newMap = new int[N][N];

for(int i=start_x; i<end_x; i++){
    for(int j=start_y; j<end_y; j++){
        newMap[start_x+(j-start_y)][(end_y-1)-(i-start_x)] = map[i][j];
    }
}

 

 

2. Periodic boundary Condition - 주기적 경계문제. 경계를 넘어가는 순간 그 다음 경계에 영향을 준다.

   - 기존에 경계를 넘어 다음 경계로 넘어가는 문제 (코드트리 - '포탑 부수기' 문제)
   - 여기서 중요한 것은 index를 내가 '0'부터 잡느냐 아니면 '1'부터 잡느냐이다 0 ~ N-1 or 1 ~ N 이렇게 되면 달라진다.

//이 경우는 1칸씩 step by step으로 움직일때의 케이스
//0 ~ N-1 indexing잡았을 때
int new_x = (N + (x + dx[dir]))%N;
int new_y = (M + (y + dy[dir]))%M;

//1 ~ N indexing 잡았을 때 (밖에 1을 더해주고 내부적으로 1을 빼준다)
int new_x = (N+((x-1)+dx[dir]))%N + 1;
int new_y = (M+((y-1)+dy[dir]))%M + 1;
```

```java
//이 경우는 한 번에 크게 움직일때의 케이스
//0 ~ N-1 indexing잡았을 때
int distance = 150000000;
int new_x = Math.abs((N + (x + distance)))%N;
int new_y = Math.abs((M + (y + distance)))%M;

//1 ~ N indexing 잡았을 때 (밖에 1을 더해주고 내부적으로 1을 빼준다)
int new_x = Math.abs((N+((x-1)+distance)))%N + 1;
int new_y = Math.abs((M+((y-1)+distance)))%M + 1;

 

 

3. 거꾸로 방향 바꾸는 문제

   - 대표적으로 '주사위 문제3' 와 '토끼와 경주' 문제가 있다. 이 부분에 대해서 이해후 암기

 

 

4. Sort - 여러 조건에 따라 정렬하는 조건 (최근에 많이 나옴)

    - 최근에 빈번하게 4~5개 조건씩 해서 나오는 문제가 많이 나온다.

Collections.sort(list, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) { //양수면 순서대로, 음수면 역순

        if(o1<o2) {
            return 1; //이전거가 다음거보다 작을때 안바꾸면 오름차순, 바꾸면 내림차순 (양수 바꿔, 음수 안바꿔)
            //이걸 어떻게 생각하면 되냐면, o1기준으로 o2를 비교했을때 o1<o2이면 return 양수 -> 바꿔! o1과 o2가 바뀜.
        }else if(o1==o2) {
            return 0;
        }else {
            return -1;
        }
    }
});

//원래는 위와 같이 되어 있지만, 편하게 아래와 같이 생각하면 된다. (위의 case는 long type때문에)
Collections.sort(list, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) { 
        return o1-o2; //o1-o2 (오름차순) , o2-o1 (내림차순) o1 o2 순서대로 (오름), o2 o1 역으로 (내림)
    }
});

 

 

 그리고 Comparator는 기본적으로 int type을 반환하게 되어 있는데 만약 Long type이라면? 그냥 compareTo그대로 쓰면 된다.  [o1-o2 -> o1.compareTo(o2), o2-o1 -> o2.compareTo(o1)]

List<Long> list2 = new ArrayList<>(Arrays.asList(1L,30L,0L,0L,1L,3L,2L,1L,0L,5L,2L,0L,3L));
Collections.sort(list2, new Comparator<Long>() {
    @Override
    public int compare(Long o1, Long o2) {
        if (o1 == 0) {
            if (o2 == 0) {
                return 0; // o1과 o2가 둘 다 0이면 같다.
            } else {
                return 1; // o1만 0이므로 o1을 뒤로 보낸다.
            }
        } else if (o2 == 0) {
            return -1; // o2만 0이므로 o2를 뒤로 보낸다.
        } else {
            return o1.compareTo(o2); // o1과 o2가 둘 다 0이 아니면 숫자의 크기로 정렬한다.
        }
    }
});
System.out.println(list2);

 

6. BFS - 최단거리 찾는 문제

 대부분의 문제가 BFS를 요구하지만, Trace를 모두 가져와야 하는지 등에 대해서 조건이 달라질수 있고 구현이 달라질수 있다. ('포탑 부수기'문제)

 

7. Spiral - 나선형 좌표 
 - Spiral 좌표문제가 한때 자주 나왔었다. 혹시 모르니 익혀가야 한다 ('백준의 - 상어와 블리자드' 문제 및 '스톰' 문제)
 - 추가적으로 숨바꼭질 문제에서는 좌표만이 아니라 방향 또한 저장했어야 했다 <- 이거 착각한거때문에 고생함.

static void makeSpiral() {
		
		int[] dx = {0,1,0,-1};
		int[] dy = {-1,0,1,0};
		
		int index = 0;
		int dir = 0, rDir=2;
		int cur_depth = 0;
		int ref_depth = 1;
		int turn=0;
		
		int x_0 = N/2;
		int y_0 = N/2;
		spiralMap.put(index, new Node(x_0, y_0, dir, rDir));
		
		while(true) {
			
			index++;
			if(index==N*N) {
				break;
			}
			
			int new_x = x_0 + dx[dir];
			int new_y = y_0 + dy[dir];
			
			spiralMap.put(index, new Node(new_x, new_y, dir, rDir));
			cur_depth++;
			
			if(cur_depth == ref_depth) {
				
				dir = (dir+1)%4;
				rDir = (dir+2)%4;
				cur_depth=0;
				turn ++;
				spiralMap.put(index, new Node(new_x, new_y, dir,rDir));
				if(turn==2) {
					ref_depth++;
					turn=0;
				}

			}
			
			x_0 = new_x;
			y_0 = new_y;

		}
		
		
	}

 

 

내가 했던 실수들 

 

1. 전역 조건, 국부 조건

 문제 읽을때 조심해야 하는 부분 - 어떤 조건이 있을때, 그 조건이 시뮬레이션이 돌아가는 전체동안에 해당되는 것인지 아니면, 국부적으로만 해당되는것인지 확실히 알아야 한다.

(예제)

1. '포탑 부수기 문제' - 시계열에 따라 최근 포탑을 포탑이 공격한 횟수로 착각함
2. '토끼와 경주' - K번 돌아가는 조건내에서 한 번이라도 jump한 토끼에 해당되는데 전체 시뮬레이션에서 한 번이라도 jump한 토끼로 착각함.

 

 

2. 동시성 문제

 List에서 remove했을때 for loop를 그냥 돌려버리면, 하나를 그냥 건더 띄어 버린다. 이럴 경우 remove가 될 경우 i--를 함으로써 동시성 문제를 해결할수 있다.  동시에 remove시키면서 전진시키니까 [1,2,3,4,5] -> 만약 index 2일때 3을 remove했을때 그 다음 index는 3이 된다. 하지만 list안에는 [1,2,4,5] 4가 아닌 5를 가리키게 된다. (조심해야 할 부분)
 

(예제) - '숨바꼭질'문제에서도 --안해서 동시성 문제 발견함.

 

3. Loop 빠질때 break 여부 확인

  '꼬리잡기' 문제에서 1번 머리가 그 다음 갈 곳을 찾을때 4방향에 대해서 탐색하게 되는데, 이때 '4'를 찾고 break하지 않으면, 이상한걸로 update가 되게 된다.

 

  /*(예를 들어 아래와 같은 과정을 거쳐야 하는데, 두 번째 케이스에서 보면 1이 4를 찾아서 옮겨가고 여기서 break를 하지 않으면,
   4를 찾고 나서도 이후 이상한 값으로 덮어 씌워질수 있다.)*/
  
  4 3 2 1         4 3 2 1        4 3 2 2         4 3 3 2        4 4 3 2
  4 0 0 4    ->   4 0 0 1   ->   4 0 0 1   ->    4 0 0 1   ->   4 0 0 1
  4 4 4 4         4 4 4 4        4 4 4 4         4 4 4 4        4 4 4 4

 

 

연습했었던 구현 부분들 공유드립니다.