알고리즘 스터디 - 4주차 1

15721

• 알고리즘 : 브루트포스 알고리즘
• 난이도 :실버5

문제

15721

접근

• 뻔데기 순서를 저장하는 배열 또는 LinkedList를 만든다.
• 사람 수 만큼의 인덱스를 번데기 크기만큼 반복하여 저장한다.
• 구하고자 하는 위치 값을 받는다.

가정

• 일단 이런 문제들은 주어진 상수들의 크기를 파악하는 것이 중요한거 같다.
  • A는 2,000보다 작거나 같은 자연수
  • 구하고자 하는 번째 T(T ≤ 10000)
• 중첩 될 경우 시간 복잡도를 생각한다.
  • 한번 중첩 N 100,000,000
  • 두번이상 중첩하면 안되겠구나...
• 중첩 없이도 풀 수 있을 것 같다.

풀어보기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	public static void main(String[] args) throws IOException {
		// 뻔데기들 저장할 공간 size * 2 (뻔 또는 데기)
		// 뻔 0 , 데기 1
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int people = Integer.parseInt(bf.readLine());
		int size = Integer.parseInt(bf.readLine());
		int bbunOrDegi = Integer.parseInt(bf.readLine());

		int myTurnSayCount = 0;
		int repeat = 2;
		int totalSize = 0;
		while(myTurnSayCount < size){
			List<Integer> talk = new ArrayList<>();
			talk.add(0);
			talk.add(1);
			talk.add(0);
			talk.add(1);
			for(int i = 0; i < repeat; i++){
				talk.add(0);
			}
			for(int i = 0; i < repeat; i++){
				talk.add(1);
			}
			for(int i = 0; i < talk.size(); i++){
				if(talk.get(i) == bbunOrDegi){
					myTurnSayCount++;
				}
				if(myTurnSayCount == size){
					System.out.println(totalSize % people);
					break;
				}
				totalSize++;
			}
			repeat++;
		}


	}
}

시행착오

메모리 초과로 테스트 통과를 하지 못하였습니다.
ArrayList를 새로 초기화 해야하는데 한번에 해결하려고 해서 메모리 초과 된 것 같다.
반복문이 끝날 때 마다 ArrayList를 초기화 해야한다.

참고자료

• 없음