카드를 뒤집어라!

[문제]

1 ~ 100까지의 카드가 있다. 모든 카드는 뒷면이 위를 향한 상태로 놓여있다.

2번 카드부터 1장 간격으로 카드를 뒤집는다. 3번부터 2장 간격으로 카드를 뒤집는다.

이렇게 n번째의 카드부터 n-1장 간격으로 카드를 뒤집는 작업을 뒤집을 카드가 더는 없을 때 까지 계속해

뒷면이 위를 향한 카드의 번호를 구해 보세요. 

 

[언어]

Java(1.8)

 

[풀이]

//카드의 정보를 담을 Map 초기화 모든 카드는 뒷면이 위를 향한 상태로 놓여있기 때문에 Object의 기본값 null이 뒷면
Map<Integer, Object> map = new HashMap<Integer, Object>();
 
//n번째 카드의 n-1장 간격으로 뒤집기 때문 n은 2 이상
for(int i = 2; i <= 100; i++) {
    //n-1장 간격이기 때문에 n번째 카드를 뒤집는다
    for(int j = i; j <= 100; j+=i) {
        if(map.get(j) == null) {
            map.put(j, new Object());
        }else {
            map.put(j, null);
    }
    }
}
        
for(int i = 1; i <= 100; i++) {
    if(map.get(i) == null) {
        System.out.println(i);
    }
}

 

[답]

1, 4, 9, 16, 25, 36, 49, 64, 81, 100