[백준]1253 좋다 - 자바/Java

2164번: 카드2

🌱풀이

어려운 문제는 아니었다. Queue는 선입선출이므로, 꺼내고 다시 넣으면 가장 마지막 순서로 배정된다. Queue의 크기가 1이 될 때까지 반복해주면 된다.

💡 메모리 : 51024KB, 시간 148ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		Queue<Integer> q = new LinkedList<>();
		for(int i = 1; i<N+1; i++) q.add(i);
		
		while(q.size() > 1) {
			q.poll();
			int cur = q.poll();
			q.add(cur);
		}
		System.out.print(q.poll());
		
	}
}

---

🪴코드 리뷰

🌿

시간이 좀 더 걸렸을지언정 메모리는 대폭 줄였다. 이런 코드는 대체 언제 만든거지

Boolean형 배열 num의 값이 true이면 버려진 상태, false이면 카드가 버려지지 않은 상태다. 인덱스가 카드의 번호를 의미한다. i는 1부터 증가하여, 카드의 번호를 1부터 순차적으로 증가시키는 기능을 수행한다. i는 N에 도달해도 계속 증가하기 때문에 초기화 과정이 필요하다. 그 과정을 n이 수행한다. 모듈러 연산을 통해 i을 N+1로 나누면 그 나머지는 1부터 N까지 반복된다. 카드는 한 번 버려지고 한 번 버려지지 않으므로, 1씩 증가하는 j를 기준으로 2로 나누었을 때 1이면 버리고, 아니면 살려둔다. 버릴 때마다 사이즈는 1씩 감소한다.

Queue를 사용하지 않고 배열을 활용하여 문제를 해결했다. 모듈러 연산의 응용을 연습하려고 한 것 같다.

💡 풀이자 : 본인, 메모리 : 13364KB, 시간 160ms

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		boolean[] num = new boolean[N+1];
		num[0] = true;
		int size = N;
		int i = 1;
		int j = 1;
		int n = 1;
		while(true) {
			if(size == 0) {
				System.out.print(n);
				break;
			}
			if(!num[i%(N+1)]) {
				if(j%2 == 1) { // 버리기
					num[i%(N+1)] = true;
					size--;
				}
				else
					n = i%(N+1);
				j++;
			}
			i++;
		}
		
	}
}

---

Conclusion

• 다른 사람들은 대부분 Queue를 이용해 풀었고, 로직은 완전히 동일했다.
• 모듈러 연산을 통해 풀이한 코드는.. 자료 구조의 사용을 최소화하여 메모리를 최적화 해야할 때 활용하면 좋을 것 같다.