본문 바로가기
PS/BOJ

백준 15738 자바 - 뒤집기 (boj 15738 java)

by Nahwasa 2022. 4. 20.

문제 : boj15738

 

 

  풀이 첫 줄에 강력한 스포가 있다. 혹시 아직 못 풀어서 이걸 어떻게 풀지? 생각되어 풀이를 봤다면, 이하 풀이를 보면 많이 짜증날 수 있으니 다시 한번 문제를 잘 읽어보고 직접 도전해보는걸 추천한다.

 

 

 

 

 

 

 

 

-------

 

 

 

 

 

 

 

 

  풀이 : 애초에 배열 A가 아무런 의미가 없다 ㅋㅋㅋ 그냥 입력받은 n과 k만 가지고 각 m개의 연산에 따라 사칙연산으로 k의 위치만 바꿔주면 된다.

 

A. i가 양수일 때 i < k 라면 무시하면 된다. -> 그리고 i-k+1로 k를 변경해주면 된다.

B. i가 음수일 때 n+i+1 까지 영향을 끼치므로, 그보다 k가 작다면 무시하면 된다. -> 그리고 2*n-k+i+1로 k를 변경해주면 된다!

 

따라서 시간복잡도는 O(M)이다. N은 아무런 영향을 끼치지 않는다. 이하 코드에서도 배열 A는 그냥 무시해버린다. 이 문제를 해결하는데 아무런 의미도 없는 정보이기 때문이다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        br.readLine();  // throw
        while (m-->0) {
            int i = Integer.parseInt(br.readLine());
            if (i > 0 && i < k) continue;
            if (i < 0 && n+i+1 > k) continue;
            k = i>0 ? i-k+1 : 2*n-k+i+1;
        }
        System.out.println(k);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

댓글