• https://gompangs.tistory.com/entry/Spring-Redis-Template-Transaction

• https://wildeveloperetrain.tistory.com/137#google_vignette

  • https://redis.io/docs/latest/develop/interact/transactions/

• https://giron.tistory.com/125

잘 돌아가던 로직에 아 맞다 transactional~ 하면서 애노테이션을 추가하자 nullpointerException을 마주쳤다. 분명히 직접 cli로 조회하면 값이 존재하는데 왜?? 라는 의문이 생겨 무심코 마우스를 올렸다가 답을 찾았다

Returns: null when used in pipeline / transaction

JPA에서 트랜잭션에서의 조회연산(select)은 트랜잭션 격리수준에 따라 값의 유지여부는 갈리지만, 바로 데이터베이스로 전송되어 실행된다. update 쿼리와 다르게 어딘가 저장되어 있다가 commit시점에 실행되는 것이 아니다.

하지만 Redis는 MULTI-EXEC 방식으로 트랜잭션이 동작하기 때문에 JPA와 조금 다른 결과가 생길 수 있다

A Redis Transaction is entered using the MULTI command. The command always replies with OK. At this point the user can issue multiple commands. Instead of executing these commands, Redis will queue them. All the commands are executed once EXEC is called.

MULTI - 이후에 오는 연산들은 전부 queued, 이후에 exec 명령이 호출되는 시점에 한 번에 실행된다.

get이든 set이든 exec시점에 날라가 실행되기 때문에 transaction 내부에서 조회를 하게 되면, exec이 끝난 후에 get의 값을 얻기 때문에 의미가 없어 null을 리턴한다

따라서 조회, 수정 로직을 구분에 transaction 단위를 나누는 것이 중요해보인다.

request - 인증, 예외처리 과정

1.request -> servlet filter 거침 2-1. filter를 통과한 요청은 Dispatch Servlet -> 일치하는Controller 단으로 전달 : 이후에 발생하는 Exception들은 @ControllerAdvice로 처리 가능

2-2. 하지만 filter에서 걸린 예외들은 DispatchServlet까지 전달되지 않기 때문에 @ControllerAdvice로 처리할 수 없다 : 따라서 인증과정에서 발생하는 예외를 처리하기 위한 AuthenticationEntryPoint를 구현하여 처리해야 함

- AuthenticationEntryPoint 구현체

public class JwtAuthenticationEntryPoint implements AuthenticationEntryPoint {

    private final static String EXCEPTION = "exception";
    private final static String LOGOUT = "logout";
    private final static String MALFORMED = "malformed";
    private final static String EXPIRED = "expired";
    private final static String HEADER = "header";
    private final static String BEARER = "bearer";

    @Override
    public void commence(HttpServletRequest request, HttpServletResponse response, AuthenticationException authException) throws IOException, ServletException {
        String exception = (String)request.getAttribute(EXCEPTION);
        response.setContentType("application/json; charset=UTF-8");

        if(exception!=null) {
            if (exception.equals(EXPIRED)) {
                setResponse(response,HttpStatus.UNAUTHORIZED.value(),"만료된 토큰입니다", 1000);
            } if (exception.equals(MALFORMED)) {
                setResponse(response,HttpStatus.BAD_REQUEST.value(), "잘못된 형식의 토큰입니다");
            } if(exception.equals(HEADER)) {
                setResponse(response,HttpStatus.BAD_REQUEST.value(), "Authorization 헤더가 존재하지 않습니다.");
            } if(exception.equals(LOGOUT)) {
                setResponse(response, HttpStatus.BAD_REQUEST.value(), "로그아웃 처리된 토큰입니다.");
            } if(exception.equals(BEARER)) {
                setResponse(response, HttpStatus.BAD_REQUEST.value(), "Bearer 형식이 잘못됐습니다.");
            }
        }
    }
    public void setResponse(HttpServletResponse response,int status,String msg) throws IOException{
        ObjectNode json = new ObjectMapper().createObjectNode();
        json.put("status",status);
        json.put("success", false);
        json.put("message", msg);
        String newResponse = new ObjectMapper().writeValueAsString(json);
        response.getWriter().write(newResponse);
        response.setStatus(status);
    }
    public void setResponse(HttpServletResponse response,int status,String msg, int code) throws IOException{
        ObjectNode json = new ObjectMapper().createObjectNode();
        json.put("status",status);
        json.put("success", false);
        json.put("message", msg);
        json.put("code", code);
        String newResponse = new ObjectMapper().writeValueAsString(json);
        response.getWriter().write(newResponse);
        response.setStatus(status);
    }

- 원하는 결과가 나오지 않았던 filter

@RequiredArgsConstructor
public class JwtAuthenticationFilter extends OncePerRequestFilter {

    private final JwtProvider jwtProvider;
    private final RefreshTokenRepository refreshTokenRepository;
    private final static String EXCEPTION = "exception";
    private final static String LOGOUT = "logout";
    private final static String MALFORMED = "malformed";
    private final static String EXPIRED = "expired";
    private final static String HEADER = "header";
    private final static String BEARER = "bearer";

    @Override
    protected void doFilterInternal(HttpServletRequest request, HttpServletResponse response, FilterChain filterChain)
            throws ServletException, IOException {
        try {
            System.out.println("in auth filter");
            String token = resolveToken(request);
            //로그아웃 한 토큰인지 검증
            Optional<RefreshToken> refreshToken = refreshTokenRepository.findByToken(token);
            if(!refreshToken.isEmpty()) {
                if(refreshToken.get().getMemberId().equals("blackList")) {
                    //TODO:: 필터내부 오류는 ControllerAdvice로 처리 불가
                    // -> catch해서 AuthenticationEntryPoint : ServletResponse & ObjectMapper로 직접 예외처리
                    throw new LogOutToken();
                }
            }
            //유효한 토큰인지 검증
            if (jwtProvider.validateToken(token)) {
                Authentication authentication = jwtProvider.getAuthentication(token);
                SecurityContextHolder.getContext().setAuthentication(authentication);
            }
            //위치 문제
            System.out.println("done auth filter");
            filterChain.doFilter(request, response);
        } catch (LogOutToken e) {
            request.setAttribute(EXCEPTION,LOGOUT);
        } catch (MalformedJwtException e) {
            request.setAttribute(EXCEPTION,MALFORMED);
        } catch (ExpiredJwtException e) {
            request.setAttribute(EXCEPTION, EXPIRED);
        } catch (NoAuthorizationHeader e) {
            request.setAttribute(EXCEPTION, HEADER);
        } catch (NoBearer e) {
            request.setAttribute(EXCEPTION,BEARER);
        }

    }

    //헤더에서 토큰 정보 추출
    private String resolveToken(HttpServletRequest request) {
        String bearerToken = request.getHeader("Authorization");
        if(!StringUtils.hasText(bearerToken)) throw new NoAuthorizationHeader();
        if(!bearerToken.startsWith("Bearer")) throw new NoBearer();
        return bearerToken.substring(7);
    }
}

filter 내부에서 Exception이 발생하면 request의 exception이라는 필드에 오류 발생내역을 기록해서 넘기고, 이 exception을 전달받은 AuthenticationEntryPoint에서 오류 내용을 확인하고 직접 custom 한 예외처리를 하는 방식이다.

아직 프론트에서 어떻게 처리할 지 정확히 정해진 바가 없어서 일단 만료된 토큰의 경우에는 reissue 요청을 해야하므로 더 구분하기 편하게 response에 code라는 필드를 추가해봤다.

오류발생

하지만 테스트 해보려고 스웨거를 켜니까 화면이 나오지 않는 오류가 발생했다

ㅜㅜ

로그를 확인하니, in auth filter만 있고 done auth filter는 찍히지 않은 것으로 보아 filter 내부에서 발생한 exception 때문인 것으로 보인다

의문점

permitAll 안됨 근데 스웨거는 white_list에 등록해서 permitAll 해 둔 url인데..? 라는 의문이 생겨서 구글링 해본 결과 아주 도움되는 글을 찾았다

https://velog.io/@choidongkuen/Spring-Security-SecurityConfig-%ED%81%B4%EB%9E%98%EC%8A%A4%EC%9D%98-permitAll-%EC%9D%B4-%EC%A0%81%EC%9A%A9%EB%90%98%EC%A7%80-%EC%95%8A%EC%95%98%EB%8D%98-%EC%9D%B4%EC%9C%A0#jwtauthenticationentrypointclass

정리하자면 permitAll()은 필터체인을 아예 거치지 않게 해주는 것이 아니라 필터를 거치되, ExceptionTranslationFilter를 통한 예외처리 과정을 거치지 않고, 인증 객체 존재 여부 상관 없이 정상적으로 API를 호출할 수 있게 해준다는 것

이 점을 알고 살펴보니.. 순서에 문제가 있는 점이 보였다

- 고친 후의 filter

try {
            System.out.println("in auth filter");
            String token = resolveToken(request);
            //로그아웃 한 토큰인지 검증
            Optional<RefreshToken> refreshToken = refreshTokenRepository.findByToken(token);
            if(!refreshToken.isEmpty()) {
                if(refreshToken.get().getMemberId().equals("blackList")) {
                    //DONE:: 필터내부 오류는 ControllerAdvice로 처리 불가
                    // -> catch해서 AuthenticationEntryPoint : ServletResponse & ObjectMapper로 직접 예외처리
                    throw new LogOutToken();
                }
            }
            //유효한 토큰인지 검증
            if (jwtProvider.validateToken(token)) {
                Authentication authentication = jwtProvider.getAuthentication(token);
                SecurityContextHolder.getContext().setAuthentication(authentication);
            }
        } catch (LogOutToken e) {
            request.setAttribute(EXCEPTION,LOGOUT);
        } catch (MalformedJwtException e) {
            request.setAttribute(EXCEPTION,MALFORMED);
        } catch (ExpiredJwtException e) {
            request.setAttribute(EXCEPTION, EXPIRED);
        } catch (NoAuthorizationHeader e) {
            request.setAttribute(EXCEPTION, HEADER);
        } catch (NoBearer e) {
            request.setAttribute(EXCEPTION,BEARER);
        }
        //위치 변경
        System.out.println("done auth filter");
        filterChain.doFilter(request, response);

try문 내부에 doFilter(다음 필터로 넘기는 뿐)을 넣은 것이 문제였다. permitAll 한 요청이어도 이 필터를 전부 거치기 때문에 Authentication 헤더가 없으므로 try의 마지막에 있던 doFilter에 도달하기 전에 exception이 발생하여 doFilter가 호출되지 못하고, 필터체인이 연쇄되지 않으므로 api 호출도 끝나버린 것이다.

따라서 doFilter를 try-catch 밖으로 빼버리는 것만으로 정상적으로 whiteList의 요청이 수행됐다.

또한 이것을 알게 되니 JwtProvider.validate()도 수정할 부분이 보였다

public boolean validateToken(String token) {
        Jwts.parserBuilder().setSigningKey(key).build().parseClaimsJws(token);
        return true;
        /* 기존의 코드
        try {
            Jwts.parserBuilder().setSigningKey(key).build().parseClaimsJws(token);
            return true;
        } catch (io.jsonwebtoken.security.SecurityException | MalformedJwtException e) {
            System.out.println("Invalid Token "+e);
        } catch (ExpiredJwtException e) {
            System.out.println("Expired Token "+e);
        } catch (UnsupportedJwtException e) {
            System.out.println("Unsupported Token "+e);
        } catch (IllegalArgumentException e) {
            System.out.println("JWT claims string is empty."+e);
        }
        return false;
         */
    }

기존에는 validate 안에서 exception을 catch 해서 그냥 로그만 찍어버리고 있었다.. 이렇게 하면 filter로 exceptio이 전달이 안 되므로 원하는 방식으로 exception Response를 처리하지 못 한다

따라서 그냥 try를 빼서 Exception이 발생하게 두고, filter에서 알아서 처리하도록 하며 / 발생하지 않는다면 valid하므로 true를 반환하도록 수정했다.

parseClaim 수정

private Claims parseClaims(String accessToken) {
        //reissue 하는 경우에 토큰 관련 exception은 여기서 걸림
        try {
            return Jwts.parserBuilder().setSigningKey(key).build().parseClaimsJws(accessToken).getBody();
        } catch (ExpiredJwtException e) {
            return e.getClaims();
        } catch (MalformedJwtException e) {
            throw new MalformedJwtException("잘못된 형식의 토큰입니다");
        }
    }

처음엔 filter에서 사용하는 validate & parseClaims(getAuthentication에서 사용)에서 try-catch를 전부 빼버렸었다.

하지만 그렇게 하니까 이 메소드를 호출하는 reissue에서 예외처리가 전혀 되지 않는다는 문제가 발생했다. reissue는 filter단이 아니라 controller 내부이기 때문이다..

하지만 filter에서 validate - parseClaims의 순서를 생각해보니 parseClaim의 try-catch는 그대로 둬도 된다고 판단했다. 어차피 validate와 parseClaim의 기능이 비슷하므로 validate에서 exception이 전부 검증이 되기 때문에 validate를 통과하면 parseClaim에서는 예외가 발생하지 않을 것이기 때문이다.

즉 parseClaim에서 발생하는 ExpiredJwtException & MalformedJwtException은 Authentication 과정에서 발생하는 filter에서 걸러지는 부분이 아니라, reissue 요청으로 받은 accessToken을 검증하는 파트에서만 발생하는 예외가 된 것이다.

필터부분이 아니므로 ControllerAdvice로 편하게 처리할 수 있다

• 참고

• https://velog.io/@choidongkuen/Spring-Security-SecurityConfig-%ED%81%B4%EB%9E%98%EC%8A%A4%EC%9D%98-permitAll-%EC%9D%B4-%EC%A0%81%EC%9A%A9%EB%90%98%EC%A7%80-%EC%95%8A%EC%95%98%EB%8D%98-%EC%9D%B4%EC%9C%A0#2-permitall-%EC%97%90-%EB%8C%80%ED%95%9C-%EB%82%98%EC%9D%98-%EC%9E%98%EB%AA%BB%EB%90%9C-%EC%9D%B4%ED%95%B4
• https://dmaolon00.tistory.com/entry/Spring-filter-%EB%82%B4%EC%97%90%EC%84%9C-%EB%B0%9C%EC%83%9D%ED%95%9C-%EC%98%88%EC%99%B8-%EC%B2%98%EB%A6%AC%ED%95%98%EA%B8%B0-AuthenticationEntryPoint-AccessDeniedHandler
• https://colabear754.tistory.com/172#%EC%95%84%EB%AC%B4%EB%9F%B0_%EC%84%A4%EC%A0%95%EC%9D%84_%ED%95%98%EC%A7%80_%EC%95%8A%EC%9D%80_%EC%83%81%ED%83%9C%EC%97%90%EC%84%9C_%EB%B0%9C%EC%83%9D%ED%95%98%EB%8A%94_%EC%98%88%EC%99%B8

JSON -> POJO (자바객체) : deserialize

• @RequestBody로 넘어온 JSON -> java Object로의 변환 수행 : Jackson2HttpMessageConverter

• converter 내부에서 ObjectMapper.readvalue() 호출

• readvalue : JsonDeserializer를 찾고 해당 JsonDeserializer로 deserialize(역직렬화)를 해서 Object를 반환

  • 이 과정에서 "기본생성자"를 사용해 object를 생성하고 -> 그 후에 값을 주입

  1. field가 public 이거나
  2. private인 경우 setter or getter 둘 중 하나가 필요함
  3. 기본생성자는 항상 필수

• 하지만 spring을 사용하는 경우, 내부에 jackson-module-parameter-names 모듈을 포함함 : 기본생성자가 없어도 다른 생성자에 역할을 위임하여 수행

• 인자가 1개인 생성자만 존재하는 경우엔 binding error 발생 : @Jacksonized / @JsonCreator 사용해 해결 필요

- 생성자 선택 전략

• com.fasterxml.jackson.databind.deser
• .BeanDeserializer -> deserializeFromObject()*
• 기본 생성자* 또는 모든 인자를 받는 생성자(파라미터명을 알 수 있는) : 프로퍼티 생성자를 사용해 객체를 생성 -> Reflection을 이용한 주입 참고링크 : https://velog.io/@appti/RequestBody-%ED%94%BC%EB%93%9C%EB%B0%B1%EC%9D%84-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B3%A0-%ED%95%B4%EA%B2%B0%ED%95%98%EA%B8%B0-%EC%9C%84%ED%95%9C-%EA%B3%BC%EC%A0%95

• 1. 기본생성자가 존재하는 경우*
• 기본생성자를 사용해 생성 : createUsingDefault

2. 프로퍼티 생성자 : 어떤 생성자 이용할 지 명시하는 방법

• @JsonCreator & @JsonProperty or @ConstructorProperties
  

• deserializefromObjectUsingNonDefault -> deserializeUsingPropertyBasedProperty 호출

@Builder와 생성자 - 직렬화

if a member is annotated, it must be either a constructor or a method. If a class is annotated, then a package-private constructor is generated with all fields as arguments (as if @AllArgsConstructor(access = AccessLevel.PACKAGE) is present on the class), and it is as if this constructor has been annotated with @Builder instead. Note that this constructor is only generated if you haven't written any constructors and also haven't added any explicit @XArgsConstructor annotations. In those cases, lombok will assume an all-args constructor is present and generate code that uses it; this means you'd get a compiler error if this constructor is not present.

즉 빌더는 클래스 레벨에 붙은 경우에는 다른 생성자가 없는 경우에만 전체생성자를 자동으로 붙여준다

• 그러므로 @Builder + @NoArgsConstructor -> 전체생성자가 없으므로 컴파일에러
• @Builder + @NoArgsConstructor + @AllArgsConstructor -> OK
• @Builder or @AllArgsConstructor : compile 에러는 없지만, 직렬화와 관련하여 오류발생
  • lombok에서 모든 인자를 받는 생성자를 붙여주는 경우, 직렬화에 이를 사용할 수 있도록 자동으로 @ConstructorProperties를 붙여줬었지만, 이 부분이 삭제되어 직렬화 과정에 오류 발생
  • 따라서 Builder 사용과 직렬화를 둘 다 수행해야 하는 경우에는 @Buider + @NoArgsConstructor (직렬화에 사용할 기본생성자) + @AllArgsConstructor (기본생성자가 존재하므로 전체생성자를 명시적으로 생성해야 함)을 사용하거나,
  • 사용할 프로퍼티 생성자를 직접 작성해주자

참고링크

• https://beaniejoy.tistory.com/75
• https://jojoldu.tistory.com/407 https://velog.io/@conatuseus/RequestBody%EC%97%90-%EA%B8%B0%EB%B3%B8-%EC%83%9D%EC%84%B1%EC%9E%90%EB%8A%94-%EC%99%9C-%ED%95%84%EC%9A%94%ED%95%9C%EA%B0%80
• https://velog.io/@conatuseus/RequestBody%EC%97%90-%EC%99%9C-%EA%B8%B0%EB%B3%B8-%EC%83%9D%EC%84%B1%EC%9E%90%EB%8A%94-%ED%95%84%EC%9A%94%ED%95%98%EA%B3%A0-Setter%EB%8A%94-%ED%95%84%EC%9A%94-%EC%97%86%EC%9D%84%EA%B9%8C-3-idnrafiw
• https://velog.io/@shinhyocheol/Lombok-%EA%B3%BC-Jackson-Deserialize-%EA%B4%80%EA%B3%84
• https://findmypiece.tistory.com/104

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        //1. 테이블 정의
        //d[i] : i번째 삼각형을 더하고 가장 긴 나선의 길이
        for (int i = 0; i < n; i++) {
            int m = Integer.parseInt(br.readLine());
            long[] d = new long[m+1];

            //2. 초기값 설정
            d[0] = 1; d[1] = 1; if(m>1) d[2] = 1;

            //3. 점화식
           for (int j = 3; j < m; j++) d[j] = d[j-2]+d[j-3];
           //4. 출력
            System.out.println(d[m-1]);
        }
    }
}

1. 테이블 정의 d[i] : i번째 삼각형을 더하고 가장 긴 나선의 길이
2. 초기값 설정 d[0] = 1; d[1] = 1; if(m>1) d[2] = 1;
3. 점화식 d[i-2] + d[i-3]

• 조심할 부분

1. 숫자가 커지면 int 범위를 넘어가므로 long 배열을 사용하자 : 오버플로우인 경우 틀렸습니다로 처리
2. n=1인 경우도 조건으로 처리해주자

진짜 열받게 많이 틀림;;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[] list = new int[n+1];
        for (int i = 0; i < n; i++)  list[i] = Integer.parseInt(st.nextToken());

        //1. 테이블 정의
        //d[i] : list[i] 탐색할 때의 최댓값
        int[] d = new int[n+1];

        //2. 초기값 설정
        d[0] = list[0];
        int max = d[0];

        //3. 점화식
        for (int i = 1; i < n; i++) {
            int max_i = list[i];
            int k=i-1;
            while(k>=0) {
                if(list[k]<list[i]) max_i = Math.max(max_i, d[k] + list[i]);
                k--;
            }
            d[i] = max_i;
            max = Math.max(d[i], max);
        }
        System.out.println(max);
    }
}

분명히 다른 예제들이 다 맞는데 아무리 고쳐봐도 1%에서 바로 틀린다면.... 같은 수가 여러 개인 경우가 반례일 수 있다

문제를 제대로 안 읽어서 같은 수가 여러개인 경우에도 증가하는 것으로 생각해서 다 더해버렸더니 제출하자마자 틀렸었다

1. 테이블 정의 d[i] : list[i] 탐색할 때의 누적합의 최댓값

2.초기값 설정 d[0] = list[0] 최댓값중 최댓값(출력할값)을 받기 위한 max 초기화

3. 점화식 이전 d[i]값들 중 최댓값을 선택해 더한다 = d[i]는 항상 최댓값인 경우의 수들만 저장됨

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        int[] list = new int[n+1];
        //1. 테이블 설정
        // d[i] : list[i]번째 수를 탐색할 때 누적합의 최댓값
        int[] d = new int[n];

        for (int i = 0; i < n; i++) list[i] = Integer.parseInt(st.nextToken());

        //2. 초기값 설정
        d[0] = list[0];
        int max = d[0];
        //d[1] = Math.max(d[0]+list[1], list[1]);

        //3. 점화식
        // 다음숫자도 누적합 or 다음숫자로 새로 시작
        for (int i = 1; i < n; i++) {
            d[i] = Math.max(d[i - 1] + list[i], list[i]);
            max = Math.max(max, d[i]);
        }

        //4. 출력
        System.out.println(max);
    }
}

1. 테이블 d[i] : list[i]번째 수를 탐색할 때 누적합의 최댓값

2. 초기값 설정 d[0] = list[0];

    int max = d[0];
    맨처음 값과 최댓값 비교를 위한 max 설정

3. 점화식 list[i]를 탐색하면서 d[i-1]+listi or list[i](다음숫자로 새로시작) 할 지 선택

한 번 작아지면 그 이후로도 더 커질 수 없기때문에 누적합 or 새로시작만 고민하면 됨

4. 출력 처음엔 배열(=list[i]번째 수를 탐색할 때 누적합의 최댓값)을 다 채우고 마지막에 정렬해서 배열의 최댓값을 구했더니 다른 제출들에 비해 시간이 느리게 나와서, 매 시도마다 max로 최댓값을 갱신해서 출력했다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        //1. 테이블설정
        // d[i] : 2 x i짜리 테이블을 채우는 경우의 수
        int[] d = new int[n+5];

        //2. 초기값 설정
        d[1] = 1;
        d[2] = 3;

        //3. 점화식
        // 0,0에 1x2를 사용한경우 : d[i-1]
        // 2x1을 사용한 경우 : d[i-2]
        // 2x2를 사용한 경우 : d[i-2]
        for (int i = 3; i <= n; i++) d[i] = (d[i-1] + 2*d[i-2])%10007;

        //4. 출력
        System.out.println(d[n]);
    }
}

11726이랑 문제는 같고 타일만 하나 추가된 조건 그래도 뭔가 달라질 줄 알았는데 정말 똑같다..

1. 테이블설정 d[i] : 2 x i짜리 테이블을 채우는 경우의 수
2. 초기값설정
3. 점화식 0,0에 1x2를 사용한경우 : d[i-1] 0,0에 2x1을 사용한 경우 : d[i-2] 0,0에 2x2를 사용한 경우 : d[i-2]

1. 2차원 배열을 쓴 경우

   import java.io.BufferedReader;
   import java.io.IOException;
   import java.io.InputStreamReader;
   

public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine());

    //1. 테이블설정
    //d[i][j] : 끝자리가 j인 i자리수의 이천수의 개수
    long[][] d = new long[n+5][2];

    //2. 초기화
    d[1][1] = 1; d[1][0] = 0;
    d[2][0] = 1; d[2][1] = 0;

    /*3. 점화식
    10
    100 101
    1000 1001 1010
    10000 10001 10010 10100 10101
    d[3][0] = d[2][0] + d[2][1]; d[3][1] = d[2][0];
    */
    for (int i = 3; i <= n; i++) {
        d[i][0] = d[i-1][0] + d[i-1][1];
        d[i][1] = d[i-1][0];
    }
    // 4. 출력
    System.out.println(d[n][0] + d[n][1]);
}

}

1. 테이블 설정
d[i][j] : 끝자리가 j인 i자리수의 이천수의 개수
2. 초기화
3. 점화식
d[i][[0] : d[i-1][0]이나 d[i-1][1]에 0을 붙이기 / d[i][1] : d[i][1]에 1붙이기

---

2. 1차원 배열

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;

public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine());

    //1. 테이블설정
    //d[i] : i자리수의 이천수의 개수
    long[] d = new long[n+5];

    //2. 초기화
    d[1] = 1; d[0] = 0;
    d[2] = 1;

    /*3. 점화식
    10
    100 101
    1000 1001 1010
    10000 10001 10010 10100 10101
    d[i-1]에 0을 붙이거나 / d[i-2]에 01을 붙이거나 = 피보나치
    */
    for (int i = 3; i <= n; i++) d[i] = d[i-1]+d[i-2];
    // 4. 출력
    System.out.println(d[n]);
}

}

```

1. 테이블 설정 d[i] : i자리수의 이천수의 개수
2. 초기화
3. 점화식 d[i-1]에 0을 붙이거나 / d[i-2]에 01을 붙이거나 = 피보나치

근데 결국 (d[i][1] = d[i-1][0]에 1을 붙이기) == (d[i-2]에 01을 붙이기) 라서 같은 방식이다 시간적으로는 아예 차이가 없었고, n이 작아서 따깋 메모리로도 큰 차이가 없어보이긴 하지만, 어쨋든 2번이 보기에도 훨씬 간결하고, 메모리적으로도 효율적인 것 같다

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        //1. 테이블설정 : d[i][j] : i번째 줄에서 j번째 숫자를 선택했을 때 최댓값
        int[][] d = new int[n+1][n+1];
        //2. 초기값 설정
        d[1][1] = Integer.parseInt(br.readLine());

        //3. 점화식
        for (int i = 2; i <= n; i++) {
            st = new StringTokenizer(br.readLine()," ");
            for (int j = 1; j <= i; j++) {
                if(j==1) d[i][1] = d[i-1][1] + Integer.parseInt(st.nextToken());
                else if(j==i) d[i][i] = d[i-1][i-1] + Integer.parseInt(st.nextToken());
                else d[i][j] = Math.max(d[i-1][j], d[i-1][j-1]) + Integer.parseInt(st.nextToken());
            }
        }
        //4. 출력
        Arrays.sort(d[n]);
        System.out.println(d[n][n]);
    }
}

1. 테이블 설정 d[i][j] : i번째 줄에서 j번째 숫자를 선택했을 때 최댓값

2. 초기값 설정 1차원은 1시작, 2차원은 0시작, ... 하면 헷갈릴 것 같아서 둘 다 1로 시작했다

3. 점화식 각 줄의 첫번째, 마지막 항은 한가지 선택지만 있으므로 그냥 받아옴 / 그 이외의 항들은 j, j-1번째 항 중 더 큰 값을 선택함

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 1. 테이블
        // d[i][2] : fibonacci(i)를 호출했을때 0, 1이 호출되는 횟수
        int[][] d = new int[41][2];

        // 2. 초기값
        d[0][0] = 1; d[0][1] = 0;
        d[1][0] = 0; d[1][1] = 1;
        d[2][0] = 1; d[2][1] = 1;
        d[3][0] = d[2][0]; d[3][1] = d[2][1]+1;

        //3. 점화식
        for (int k = 4; k <= 40; k++) {
            d[k][0] = d[k-1][0] + d[k-2][0];
            d[k][1] = d[k-1][1] + d[k-2][1];
        }

        //4. 출력
        for (int i = 0; i < n; i++) {
            int cur = Integer.parseInt(br.readLine());
            System.out.println(d[cur][0]+" "+d[cur][1]);
        }
    }
}

1. 테이블 설정 d[i][0] : fibonacci(i)를 호출했을때 0이 호출되는 횟수 d[i][1] : fibonacci(i)를 호출했을때 1이 호출되는 횟수

2. 초기값 설정 fibonacci(3) = fibonacci(2) + fibonacci(1) 이므로 d[3][0]까지 설정해줘야 함

3. 점화식 그냥 피보나치 그대로 i-1, i-2 더해주면 됨

1463번 1로만들기와 동일한데, 중간경로를 출력하는 부분이 추가된 문제이다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // 1. 테이블 설정
        // b[i] : i가 1이 되기위한 연산의 최솟값
        // q[i] : 경로를 출력하기 위해 저장하는 값,
        int[] b = new int[n+5];
        int[] q = new int[n+5];

        //2. 초기값설정
        b[1]=0; b[2]=1; b[3]=1;
        q[1]=1; q[2]=1; q[3]=1;

        //3. 점화식
        for (int i = 4; i <= n; i++) {
            b[i] = b[i - 1] + 1;
            q[i] = i - 1;
            if (i % 3 == 0) {
                if (b[i / 3]+1 < b[i]) {
                    b[i] = b[i / 3]+1;
                    q[i] = i / 3;
                }
            }
            if (i % 2 == 0) {
                if (b[i / 2]+1 < b[i]) {
                    b[i] = b[i / 2]+1;
                    q[i] = i / 2;
                }
            }
        }
        System.out.println(b[n]);
        int i=n;
        System.out.print(n+" ");
        while(i!=1) {
            System.out.print(q[i]+" ");
            i=q[i];
        }
    }
}

1. 테이블 b[i] : i가 1이 되기위한 연산의 최솟값 q[i] : 경로를 출력하기 위해 저장하는 배열

2. 초기값 설정

3. 점화식 b[i] = b[i - 1] + 1 하고 3, 2로 나누어 떨어지는 경우, i/3, i/2와 값 비교하여 최솟값 삽입 동시에 q값도 채워넣음

4. 출력 LinkedList처럼 배열에 저장된 값 타고가며 출력

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int[] r = new int[1005];
        int[] g = new int[1005];
        int[] b = new int[1005];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine()," ");
            r[i] = Integer.parseInt(st.nextToken());
            g[i] = Integer.parseInt(st.nextToken());
            b[i] = Integer.parseInt(st.nextToken());
        }

        // 1. 테이블 설정
        // d[i][3] : i번째 집이 각각 r / g / b일 때 합의 최솟값을 저장
        int[][] d = new int[1005][3];

        //2. 초기값 설정
        d[1][0] = r[1]; d[1][1] = g[1]; d[1][2] = b[1];

        // 3. 점화식
        for (int i = 2; i <= n; i++) {
            d[i][0] = Math.min(d[i-1][1], d[i-1][2]) + r[i];
            d[i][1] = Math.min(d[i-1][0], d[i-1][2]) + g[i];
            d[i][2] = Math.min(d[i-1][0], d[i-1][1]) + b[i];
        }
        System.out.println(Math.min(Math.min(d[n][0], d[n][1]), d[n][2]));
    }
}

1. 테이블설정 : d[i][3] : i번째 집이 각각 r / g / b일 때 합의 최솟값을 저장

• 즉 d[i][0] : i번째 집이 r인 경우 합의 최솟값 , d[i][1] : g인경우, d[[i][2] : b인경우 최솟값, ...

2. 초기값 설정 :첫번째 집의 각 rgb 값을 넣어준다

3. 점화식 [0] : i번째 집이 r인 경우 -> i-1번째 집의 g,b중 작은값 선택 + r[i]

[1] : i번째 집이 g인 경우 -> i-1번째 집의 r,b중 작은값 선택 + g[i]

[2] : i번째 집이 b인 경우 -> i-1번째 집의 r,g중 작은값 선택 + b[i]

https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x10.md 이 문제집을 푸는 중입니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] s = new int[305];
        for (int i = 1; i <= n; i++) s[i] = Integer.parseInt(br.readLine());

        //1. 테이블정의
        // d[i][2] : 계단을 밟았을 때 점수합의 최댓값, 2차원은 연속해서 n번 밟았을 때
        int[][] d = new int[305][2];

        //2. 초기값 설정
        d[1][0] = s[1]; d[1][1] = s[1];
        d[2][0] = s[2]; d[2][1] = s[1]+s[2];

        //3. 점화식 찾기
        //d[3][0] = Math.max(d[1][0], d[1][1])+s[3];
        //d[3][1] = d[2][0]+s[3];
        for (int i = 3; i <= n; i++) {
            d[i][0] = Math.max(d[i-2][0], d[i-2][1])+s[i];
            d[i][1] = d[i-1][0]+s[i];
        }

        System.out.println(Math.max(d[n][0], d[n][1]));
    }

}

1. 테이블 정의 계단을 밟았을 때 점수합의 최댓값 연속해서 밟는 경우의 수를 표현하기 위해 2차원배열(BFS에서 벽부수기 처럼) d[i][0] : i번째 계단을 연속 0번째로 밟은 경우 d[i][1] : i번째 계단을 연속 1번째로 밟은 경우

2. 초기값 설정 d[1], d[2] -> d[3] 구현할 수 있으므로 d[1], d[2] 설정

3. 점화식 찾기 d[i][0] : 연속 0번째이므로 d[i-2]에서 올라오는 경우, d[i-2][0] - d[i-2][1] 중 더 큰 값 + 계단의 s[i]

d[i][1] : 연속 1번째이므로 d[i-1]에서 올라오는 경우, d[i-1][1]에서는 더 연속해서 올라올 수 없으므로 (연속횟수 제한조건) d[i-1][0] + 계단의 s[i]

4. 결과 n d[n][0] - d[n][1]중 최댓값 출력

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

public class Main {
    static int[][] paper;
    static int zero = 0; static int p_one=0; static int m_one=0;
    static boolean isSame(int x, int y, int n) {
        int a = paper[x][y];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(a!=paper[i+x][j+y]) return false;
            }
        }
        return true;
    }
    static void cut(int x, int y, int n) {
        //시작점(x, y)에서  n * n 배열이 모두 일치하지 않으면 9등분하고, 각 숫자를 나타내는 종이의 개수를 더하는 함수
        int height = n/3;
        if(isSame(x,y,n)) {
            if(paper[x][y]==0) zero++;
            if(paper[x][y]==1) p_one++;
            if(paper[x][y]==-1) m_one++;
            return;
        }
        //base condition
        if(n==1) {
            if(paper[x][y]==0) zero++;
            if(paper[x][y]==1) p_one++;
            if(paper[x][y]==-1) m_one++;
            return;
        }
        for (int i = 0; i < n; i+=height) {
            for (int j = 0; j < n; j+=height) {
                cut(x+i,y+j,height);
            }
        }

    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        paper = new int[n][n];
        for(int i=0;i<n;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            for (int j = 0; j < n; j++) {
                paper[i][j]= Integer.parseInt(st.nextToken());
            }
        }
        cut(0,0,n);
        System.out.println(m_one);
        System.out.println(zero);
        System.out.println(p_one);
    }
}

https://www.acmicpc.net/problem/17478

처음에 제출한 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class P17478 {
    static int n;
    static StringBuilder sb = new StringBuilder();
    static String[] str = {
            "\"재귀함수가 뭔가요?\"\n",
            "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n",
            "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n",
            "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n",
            "\"재귀함수는 자기 자신을 호출하는 함수라네\"\n",
            "라고 답변하였지.\n",
            "____"
    };
    static void recursion(int N) {
        if(N==0) {
            sb.append(str[6].repeat(n-N));
            sb.append(str[0]);
            sb.append(str[6].repeat(n-N));
            sb.append(str[4]);
            sb.append(str[6].repeat(n-N));
            sb.append(str[5]);
            return;
        }
        sb.append(str[6].repeat(n-N));
        sb.append(str[0]);
        sb.append(str[6].repeat(n-N));
        sb.append(str[1]);
        sb.append(str[6].repeat(n-N));
        sb.append(str[2]);
        sb.append(str[6].repeat(n-N));
        sb.append(str[3]);
        recursion(--N);
        sb.append(str[6].repeat(n-N-1));
        sb.append(str[5]);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        sb.append("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n");
        recursion(n);
        System.out.println(sb);
    }
}

구린 점

아직 절차지향적 사고에 갇혀.. 아님 그냥 생각을 덜 해서..? 어차피 파라미터로 넘겨주는 변수 N을 직접 --N 할 필요가 없는데 그렇게 해서 마지막 repeat는 (n-N-1)을 하도록 만들어 버렸다. -> 1. 굳이 변수를 직접 바꿀 필요 없으니 그냥 파라미터로 넘기면서 빼라~

그리고 다른 코드들은 언더바를 정해진 만큼 더하거나, 저 부분을 함수로 빼던데 너무 일차적으로 해결한 감이 있다. 또 어차피 재귀라 코드 상으로 문장들을 반복해서 쓸 일이 적은데 냅다 배열로 만들어버렸다는 점이다. 굳이 해서 직관성이 떨어진 느낌

그리고 첫 번째 문장은 base condition일 때도 아닐 때도 포함 되므로 위로 빼도 된다는걸 캐치하지 못 했다.

바꿔본 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class P17478 {
    static int n;
    static StringBuilder sb = new StringBuilder();
    static void recursion(int N) {
        sb.append("____".repeat(N));
        sb.append("\"재귀함수가 뭔가요?\"\n");
        if(N==n) {
            sb.append("____".repeat(N));
            sb.append("\"재귀함수는 자기 자신을 호출하는 함수라네\"\n");
            sb.append("____".repeat(N));
            sb.append("라고 답변하였지.\n");
            return;
        }
        sb.append("____".repeat(N));
        sb.append("\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n");
        sb.append("____".repeat(N));
        sb.append("마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n");
        sb.append("____".repeat(N));
        sb.append("그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n");
        recursion(N+1);
        sb.append("____".repeat(N));
        sb.append("라고 답변하였지.\n");
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        sb.append("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n");
        recursion(0);
        System.out.println(sb);
    }
}

크게 다른 것 같진 않지만 ^-^ BFS는 그래도 재밌었는데, 이건 진짜 접근부터가 너무 생소해서 어렵다 계속 풀다보면 늘겠지~

https://blog.encrypted.gg/941 + https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x09.md 의 문제들을 풀어봅니다.

* P1926 - 그림

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

public class P1926 {
    public static int n; public static int m;
    public static int[] dx = {1,-1,0,0};
    public static int[] dy = {0,0,-1,1};
    public static int[][] board;
    public static int[][] visited;
    public static Queue<Pair> q = new LinkedList<>();
    public static int cnt =0;
    public static int max = 0;
    public static Pair cur;

    public static void BFS() {
        int b = 0;
        q.offer(cur); // 0,0
        while(!q.isEmpty()) {
            cur = q.poll(); b++;
            for(int dir=0;dir<4;dir++) {
                int nx = cur.x+dx[dir];
                int ny = cur.y+dy[dir];
                if(nx<0 || nx>=n || ny<0 || ny>=m) {continue;}
                if(board[nx][ny]==0 || visited[nx][ny]==1) {continue;}
                visited[nx][ny]=1;
                q.offer(new Pair(nx,ny));
            }
        }
        if(b>max) {max=b;}
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());

        board = new int[n][m];
        visited = new int[n][m];
        for(int i=0;i<n;i++) { //board 초기화
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<m;j++) {board[i][j] = Integer.parseInt(st.nextToken());}
        }
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                cur = new Pair(i,j);
                if(visited[i][j]==0 && board[i][j]==1) {
                    visited[i][j]=1;
                    BFS(); cnt++; }
            }
        }
        System.out.println(cnt);
        System.out.println(max);
    }

    static class Pair {
        int x;
        int y;
        Pair(int x,int y) {
            this.x = x; this.y=y;
        }
    }
}

• cnt : 그림의 개수를 세는 변수
• b : 현재 BFS를 그림의 너비를 저장하는 로컬변수
• max : 최대크기를 저장하는 변수

  ---

  • board의 모든 점들에 BFS 수행 (아직 방문하지 않았고 && boar[i][j]==1인경우)

• 그림의 개수 = BFS()를 호출한 횟수
• 각 그림의 너비 : BFS()를 수행하면서 q.pop() 을 수행한 횟수

* P7576 - 토마토

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

public class Main {
    public static int[][] box; public static int[][] dist;
    public static Queue<Pair> q = new LinkedList<>();
    public static int[] dx = {1,-1,0,0};
    public static int[] dy = {0,0,-1,1};
    public static Pair cur;
    public static int n; public static int m;

    public static void BFS() {
        while(!q.isEmpty()) {
            cur = q.poll();
            for(int dir=0;dir<4;dir++) {
                int nx = cur.x+dx[dir];
                int ny = cur.y+dy[dir];
                if(nx<0 || nx>=n || ny<0 || ny>=m) {continue;} //범위밖
                if(dist[nx][ny]!=-1 || box[nx][ny]==-1) {continue;} //이미방문했거나 토마토가 없으면
                dist[nx][ny]= dist[cur.x][cur.y]+1;
                q.offer(new Pair(nx,ny));
            }
        }
    }
    public static void main(String[] args) throws IOException {
        int max=0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //box 초기화
        m = Integer.parseInt(st.nextToken()); n = Integer.parseInt(st.nextToken());
        box = new int[n][m]; dist = new int[n][m];
        for(int i=0;i<n;i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<m;j++) {
                int in = Integer.parseInt(st.nextToken());
                box[i][j]=in; dist[i][j]=-1;
                if(in==1) {q.offer(new Pair(i,j)); dist[i][j]=0;}
            }
        }
        BFS();
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(box[i][j]==0 && dist[i][j]==-1) {max=-1; break;}
                if(max!=-1) {max=Math.max(max,dist[i][j]);}
            }
        }
        System.out.println(max);
    }

    public static class Pair {
        int x; int y;
        Pair(int x, int y) {this.x = x; this.y = y;}
    }
}

• 여러 개의 시작점에서 + 거리를 구하는
  • 큐에 시작점이 되는 위치를 넣어두고 → BFS를 돌리기
• 큐의 성질 (BFS) : 들어온 순서대로 나오기 때문에, 큐에 처음에 들어있었던 위치(익은토마토)들로 부터 같은 거리에 있는 순서대로 큐에 담기게 된다 : 즉 큐에는 반드시 거리순으로 쌓이게 된다

  0 1 2 1 2 / (0으로부터 거리가1) 2 / (0으로부터 거리가1) / (1로부터 거리가1) (0으로부터 거리가1) / (1로부터 거리가1) / (2로부터 거리가1)

  ---

  P1926번과 다른 점

• 여러 점에서 BFS를 수행한다는 점은 같지만
• 1926번은 이중for문으로 board를 순회하며 모든 점에서 BFS를 각각 수행
• 반면에 P7576번은 시작점을 큐에 넣어놓고 BFS를 한 번만 수행한다 → 각 점들에서 부터의 최소거리를 구한다

• 거리 : dist[][] : 맨 처음에 전부 -1로 & 익은 토마토의 위치만 0으로 초기화

- 알게된 부분

• 처음엔 거리를 기록하려고 Pair에 변수를 추가하고.. 뭔 카운트를 올리고.. 별 걸 다해봤는데, 그냥 visited(방문여부기록) 배열에 거리를 표시하면서 & 방문여부도 기록하는게 제일 효율적이었고
• 루프마다 cnt++ 하는 방식은 "거리기록"이 아니라 순회를 할 때마다 값이 커져버리므로

  dist[nx][ny]= dist[cur.x][cur.y]+1;

  지금 주변을 탐색하는 (cur) 좌표의 거리+1를 해주면 된다~ 당연한 건데 돌아돌아 알게 됨 ^-^

* P4179 - 불!

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

public class Main {
    public static int n; public static int m;
    public static char[][] board; public static int[][] dist_f; public static int[][] dist_j;
    public static Queue<Pair> q = new LinkedList<>();
    public static int[] dx = {1,-1,0,0};
    public static int[] dy = {0,0,-1,1};
    public static Pair J;

    public static void BFS_F() {
        while(!q.isEmpty()) {
            Pair cur=q.poll();
            for(int dir=0;dir<4;dir++) {
                int nx = cur.x + dx[dir];
                int ny = cur.y+dy[dir];
                if(nx<0 || nx>=n || ny<0 || ny>=m) {continue;}
                if(board[nx][ny]=='#' || dist_f[nx][ny]!=-1) {continue;}//벽이거나 이미 옮긴경우
                dist_f[nx][ny] = dist_f[cur.x][cur.y]+1;
                q.offer(new Pair(nx,ny));
            }
        }
    }
    public static int BFS_J() {
        while(!q.isEmpty()) {
            Pair cur = q.poll();
            for(int dir=0;dir<4;dir++) {
                int nx = cur.x + dx[dir];
                int ny = cur.y + dy[dir];
                int distance = dist_j[cur.x][cur.y]+1;
                //탈출성공
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                    System.out.println(distance);
                    return 0;
                }
                //벽이거나 이미 불이 옮겼거나 이미 갔던곳인경우
                if(board[nx][ny]=='#' || (dist_f[nx][ny]<=distance && dist_f[nx][ny]!=-1) || dist_j[nx][ny]!=-1) {continue;}
                dist_j[nx][ny]=distance;
                q.offer(new Pair(nx,ny));
            }
        }
        System.out.println("IMPOSSIBLE");
        return 0;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());
        board = new char[n][m]; dist_j = new int[n][m]; dist_f = new int[n][m];
        for(int i=0;i<n;i++) {
            String str = br.readLine();
            for(int j=0;j<m;j++) {
                board[i][j] = str.charAt(j);
                dist_f[i][j]=-1; dist_j[i][j]=-1;
                if (str.charAt(j)=='F') {
                    dist_f[i][j]=0; q.offer(new Pair(i,j));}
                else if(str.charAt(j)=='J') {
                    J = new Pair(i,j);
                    dist_j[i][j]=0;
                }
            }
        }
        BFS_F();
        q.offer(J);
        BFS_J();
    }
    public static class Pair {
        int x; int y;
        public Pair(int x, int y) {this.x = x; this.y = y;}
    }
}

• 불의 전파 + 지훈이의 이동 모두 BFS로 거리를 재야 함

• 다만, 불의전파 → 지훈이의이동 영향을 주므로 BFS_F → BFS_J 순서로 수행함
• 탈춭조건 : 기존에는 범위를 벗어나는 것으로 간주해 continue 해버렸던 보드 밖으로 벗어나는 것 : nx < 0 || nx >= n
• 벽이거나 이미 불이 옮겼거나 이미 갔던곳인경우 : continue
• 중간에 탈출하지 못하고 q가 비게 되면 탈출불가

P4179 - 반례

4 4 ###F #J.# #..# #..# 와 같이 불이 지훈이보다 늦게 오는 곳 뿐만 아니라 불이 아예 옮겨붙지 않은 곳도 지나갈 수 있다

if(board[nx][ny]=='#' || dist_f[nx][ny]!=-1) {continue;}//벽이거나 이미 옮긴경우

따라서 이렇게만 조건을 걸었을 때는 틀렸습니다를 봤다

*P1697 - 숨바꼭질

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

public class P1697 {
    public static void main(String[] args) throws IOException {
        int[] dist = new int[100005];
        int[] dx = new int[3]; dx[0]=1; dx[1]=-1;
        Queue<Integer> q = new LinkedList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken());
        dist[n]=1; //시작점을 1로 두자
        q.offer(n);
        while(dist[m]==0) {
            int cur = q.poll();
            dx[2]=cur;
            for(int dir=0;dir<3;dir++) {
                int nx = cur+dx[dir];
                if(nx>=100005 || nx<0) {continue;} //범위넘어감
                if (dist[nx] != 0) {continue;} //이미 방문함
                dist[nx] = dist[cur]+1;
                q.offer(nx);
            }
        }
        System.out.println(dist[m]-1);
    }
}

지금까지의 BFS는 상하좌우 - int[] dx = {1,-1,0,0}; int[] dy = {0,0,-1,1}; 로의 전파였다면 이 문제는 +1, -1, *2로 전파하는 BFS라고도 볼 수 있다

• dx = {1, -1, cur} 로 둬서 +1, -1, *2로의 전파를 수행했다

P1697 - 반례

같은 곳에 있는 경우 : 0 0

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

public class Main {
    public static void main(String[] args) throws IOException {
        boolean success = false;
        int[] dist = new int[100005];
        int[] dx = new int[3]; dx[0]=1; dx[1]=-1;
        Queue<Integer> q = new LinkedList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken());
        dist[n]=1; //초기화귀찮으니깐 시작점을 1로 두자
        q.offer(n);
        while(!success) {
            int cur = q.poll();
            dx[2]=cur;
            for(int dir=0;dir<3;dir++) {
                int nx = cur+dx[dir];
                if(nx>=100000 || nx<0) {continue;} //범위넘어감
                if(dist[nx]!=0) {continue;} //이미 방문함
                if(nx==m) { //발견
                    System.out.println(dist[cur]);
                    success=true;
                    break;
                }
                dist[nx] = dist[cur]+1;
                q.offer(nx);
            }
        }
    }
}

이렇게 하면 본인자리는 안 보고 +1, -1, *2만 보므로 발견하지 못한채 q가 비게 되므로 nullpointerException이 뜬다.

성공한 풀이를 보면 동생자리의 dist가 0이 아닌경우에만 반복하므로 동생과 같은 자리에 있다면 아예 반복문을 실행하지 않는다. 이래서 테스트케이스에만 묶여있는 조건을 걸지 않고 문제의 본질적인 종료조건을 생각해보는 것이 중요한 가보다

* P2583 - 영역 구하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Queue<Pair> q = new LinkedList<>();
    public static int[][] board;
    public static int[][] visited;
    public static int[] dx = {1,-1,0,0};
    public static int[] dy = {0,0,-1,1};
    public static Pair cur;
    public static int n; public static int m;
    public static int cnt=0;
    public static ArrayList<Integer> dists = new ArrayList();

    public static void BFS() {
        int dist=0;
        while(!q.isEmpty()) {
            cur = q.poll(); dist++;
            for(int dir=0;dir<4;dir++) {
                int nx = cur.x+dx[dir];
                int ny = cur.y+dy[dir];
                if(nx<0 || nx>=n || ny<0 || ny>=m) {continue;}
                if(visited[nx][ny]==1 || board[nx][ny]==1) {continue;} //이미 방문햇거나 박스면
                visited[nx][ny]= 1;
                q.offer(new Pair(nx, ny));
            }
        }
        dists.add(dist);
    }

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        board = new int[n][m]; visited = new int[n][m];

        for(int i=0;i<k;i++) {
            int x1=0; int x2=0; int y1=0; int y2=0;
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<4;j++) { //board 초기화
                if(j==0) {y1 = Integer.parseInt(st.nextToken());}
                else if(j==1) {x1 = Integer.parseInt(st.nextToken());}
                else if(j==2) {y2 = Integer.parseInt(st.nextToken())-1;}
                else if(j==3) {x2 = Integer.parseInt(st.nextToken())-1;}
            }
            for(int j=x1;j<=x2;j++) {
                for(int l=y1;l<=y2;l++) {
                    board[j][l]=1;
                }
            }
        }
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(board[i][j]==0  && visited[i][j]==0) { //사각형이 아니고 && 방문하지 않은 곳
                    q.offer(new Pair(i,j)); visited[i][j]=1;
                    BFS();
                    cnt++;
                }
            }
        }
        sb.append(cnt).append('\n');
        Collections.sort(dists);
        ListIterator<Integer> iter = dists.listIterator();
        while(iter.hasNext()) {sb.append(iter.next()).append(' ');}
        System.out.println(sb);
    }
    public static class Pair {
        int x; int y;
        Pair(int x, int y) {
            this.x = x; this.y = y;
        }
    }
}

• 문제에서 처리해야 할 부분들

1. 입력받은 값들로 보드 구성하기

2. 영역 개수 구하기 : BFS

3. 영역 넓이 (거리가 아닌) 구하기 -> 오름차순으로 정렬 : BFS

4. 입력 받은 값들로 보드 구성하기

   • 입력받은 값을 차례로 y1, x1 / y2, x2로 저장
   • x값은 열(2차원) / y값은 행임 (1차원)
   • 입력 받는 값들은 점의 "좌표"이고 보드는 한 자리를 차지하는 배열이기 때문에 끝점은 -1을 더해 저장
   • 왼쪽 아래가 원점이라 그냥 배열을 사용하면 모양은 예시와 다르게 뒤집어지지만, 크기와 개수를 구하는 데는 상관없으므로 그냥 사용
   • 0 2 4 4 -> (2,0), (3,3)
   • (x1, y1) ~ (x2, y2) 이중for문으로 1 채움
   • 전체적으로 보면 삼중for문이라 괜히 생리적 불안감이 생기지만 어차피 각 수가 100 이하이므로 괜찮음

5. 영역개수

   이중for문으로 보드의 모든 지점 돌면서 BFS 수행 : 아직 방문하지 않고 && 1이 아닌(빈 곳) 지점을 queue에 넣고 bfs 수행할 때마다 영역개수++

6. 영역 넓이

   1. 각 사각형에서 넓이 구하기

   • queue에서 pop 할 때마다 dist++ : 넓이 증가

   2. 한 사각형 끝나고 나면 각 넓이들을 저장한 ArrayList에 add
   3. 가능한 모든 영역에 BFS를 끝낸 후에 넓이들이 저장된 ArrayList를 sort해서 오름차순으로 정렬

* P2667 - 단지번호붙이기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static Queue<Pair> q = new LinkedList<>();
    public static int[][] board; public static int[][] visited;
    public static int cnt=0;
    public static ArrayList dists = new ArrayList();
    public static int[] dx = {1,-1,0,0};
    public static int[] dy = {0,0,-1,1};
    public static int n;

    public static void BFS() {
        int dist = 0;
        Pair cur;
        while(!q.isEmpty()) {
            cur = q.poll(); dist++;
            for(int dir=0;dir<4;dir++) {
                int nx = cur.x+dx[dir];
                int ny = cur.y+dy[dir];
                if(nx<0 || nx>=n || ny<0 || ny>=n) {continue;}
                if(board[nx][ny]==0 || visited[nx][ny]==1) {continue;}
                visited[nx][ny]=1;
                q.offer(new Pair(nx,ny));
            }
        }
        dists.add(dist);
    }

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n][n]; visited = new int[n][n];
        for(int i=0;i<n;i++) {
            String str = br.readLine();
            for(int j=0;j<n;j++) {
                board[i][j] = str.charAt(j)-'0';
            }
        }
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if(board[i][j]==1 && visited[i][j]==0) { //집이면서 && 방문하지 않은 곳
                    q.offer(new Pair(i, j)); visited[i][j]=1;
                    cnt++;
                    BFS();
                }
            }
        }
        Collections.sort(dists);
        ListIterator iter = dists.listIterator();
        sb.append(cnt).append('\n');
        while(iter.hasNext()) {sb.append(iter.next()).append('\n');}
        System.out.println(sb);
    }
    public static class Pair {
        int x; int y;
        Pair(int x, int y) {this.x = x; this.y = y;}
    }
}

2583과 너무너무 비슷한 문제

1. 주어진 그대로 보드 초기화
2. 1이고(집이고) && 아직방문하지 않았으면 BFS
3. 각 거리들 ArrayList에 add 하고 마지막에 sort

* P5014 - 스타트링크

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

public class Main {
    public static void main(String[] args) throws IOException {
        int cur; int next; int result=1;
        StringBuilder sb = new StringBuilder();
        Queue<Integer> q = new LinkedList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int f = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken()); //현재위치
        int g = Integer.parseInt(st.nextToken()); //도착위치
        int u = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int[] dir = {u, -d};
        int[] building = new int[2*f+1];
        building[s]=1;
        q.offer(s);
        while(!q.isEmpty() && building[g]==0) {
            cur = q.poll();
            for(int i=0;i<2;i++) {
                next = cur+dir[i];
                if(next<=0 || next>f) {continue;}
                if(building[next]!=0) {continue;}
                building[next]=building[cur]+1;
                if(next==g) {result = building[next];}
                q.offer(next);
            }
        }
        if(building[g]!=0) {sb.append(result-1);}
        else {sb.append("use the stairs");}
        System.out.println(sb);
    }
}

P1697 - 숨바꼭질과 비슷한 문제다 그래서 틀린 것도 똑같은 부분에서 틀렸다ㅋㅋ +u, -d를 탐색하는 BFS로 풀었다

P5014 반례 : 30프로에서 틀리는 경우

풀어놓고 보니 1697이랑 정말 똑같이 해서 틀렸다.. s==g인 경우가 반례였다 조건을 고치는게 애매해질 것 같아서 시작지점을 1로 하고 결과에서 -1을 해줬다.

* P2468 - 안전 영역

https://www.acmicpc.net/problem/2468

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

public class P2468 {
    public static int n;
    public static int cnt=0;
    public static Queue<Pair> q = new LinkedList<>();
    public static int[][] board; public static int[][] visited;
    public static int maxH=0; public static int max=0;
    public static int[] dx = {1,-1,0,0};
    public static int[] dy = {0,0,-1,1};
    public static Pair cur;

    public static void BFS(int k) {
        while(!q.isEmpty()) {
            cur = q.poll();
            for(int dir=0;dir<4;dir++) {
                int nx = cur.x+dx[dir];
                int ny = cur.y+dy[dir];
                if(nx<0 || nx>=n || ny<0 || ny>=n) {continue;}
                if(board[nx][ny]<=k || visited[nx][ny]!=0) {continue;}
                visited[nx][ny]=1;
                q.offer(new Pair(nx,ny));
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n][n]; visited = new int[n][n];
        for(int i=0;i<n;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<n;j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                maxH = Math.max(board[i][j],maxH);
            }
        }
        for(int k=0;k<maxH;k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(board[i][j]>k && visited[i][j]==0) {
                        q.offer(new Pair(i,j));
                        BFS(k);
                        cnt++;
                    }
                }
            }
            max = Math.max(cnt,max);
            cnt=0;
            for(int[] a : visited) {Arrays.fill(a,0);}
        }
        System.out.println(max);
    }

    public static class Pair {
        int x; int y;
        Pair(int x, int y) {this.x = x; this.y = y;}
    }
}

사실 처음엔 문제가 뭔지 정확히 이해를 못 했다 물 높이가 주어져야 영역을 구하는 게 아닌가? 라고 생각했었는데 그게 아니라 여러가지 물 높이가 주어졌을 때, 영역이 많아지는 최대영역을 구하는 것이다.

• 지형의 최대높이 이상의 강수는 어차피 의미가 없으므로, 지형 최대높이만큼 BFS를 돌려보고 지역개수가 최대가 되는 값을 구함

1. 보드 초기화 하면서 지형의 최대높이 저장 : maxH
2. 강수 높이 0 ~ maxH 까지 board에 대해 BFS 수행
3. cnt : 해당 시행에서의 안전지역 개수

알게된 점

• Arrays.fill은 1차원 배열에만 가능하다
  • 2차원 배열을 채우려면 위에처럼 1차원 단위로 채워줘야 함
• BFS를 여러 번 수행해야 하는 경우 : 매 시행마다 cnt, visited 초기화 잊지말기

* P6593 - 상범빌딩

https://www.acmicpc.net/problem/6593

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


public class Main {
    public static int l, r, c;
    public static int[][][] building; public static int[][][] visited;
    public static Queue<Pair> q = new LinkedList<>();
    public static int result=-1;
    public static int[] dy = {1,-1,0,0,0,0};
    public static int[] dz = {0,0,-1,1,0,0};
    public static int[] dx = {0,0,0,0,1,-1};
    public static Pair cur;

    public static int BFS() {
        while(!q.isEmpty()) {
            cur = q.poll();
            for(int dir=0;dir<6;dir++) {
                int nx = cur.x + dx[dir];
                int ny = cur.y + dy[dir];
                int nz = cur.z + dz[dir];
                if(nx<0 || nx>=l || ny<0 || ny>=r || nz<0 || nz>=c) {continue;}
                if(visited[nx][ny][nz]!=0 || building[nx][ny][nz]=='#') {continue;}
                visited[nx][ny][nz] = visited[cur.x][cur.y][cur.z]+1;
                if(building[nx][ny][nz]=='E') {System.out.println("Escaped in "+(visited[nx][ny][nz]-1)+" minute(s)."); return -1;}
                q.offer(new Pair(nx, ny, nz));
            }
        }
        System.out.println("Trapped!");
        return -1;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            if(!st.hasMoreTokens()) { st = new StringTokenizer(br.readLine()); }
            l = Integer.parseInt(st.nextToken());
            r = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            if(l==0 && r==0 && c==0) {break;}
            building = new int[l][r][c]; visited = new int[l][r][c];
            for(int i=0;i<l;i++) {
                for(int j=0;j<r;j++) {
                    String str = br.readLine();
                    if(str.equals("")) { str = br.readLine(); }
                    for(int k=0;k<c;k++) {
                        building[i][j][k] = str.charAt(k);
                        if(building[i][j][k]=='S') {q.offer(new Pair(i,j,k)); visited[i][j][k]=1;}
                    }
                }
            }
            BFS();
            q.clear();
        }
    }
    static class Pair {
        int x; int y; int z;
        Pair(int x, int y, int z) {this.x = x; this.y = y; this.z = z;}
    }
}

• x, y, z 3차원배열에 BFS를 적용하는 문제

• " 3차원 배열 + 각 점마다의 출발점에서의 거리 구하기 " 인 문제이다

16%에서 틀렸습니다

• 그냥 첫 번째 케이스부터 틀리는 것 같다

1. 큐 초기화 안 함
2. 입력 공백처리 오류

   둘 중 하나일 것 같다 여긴 매 케이스마다 board,visited는 새로 할당되어 초기화 하지 않아도 된다고 안심했는데, 큐를 초기화 하는 것을 잊었다

!! BFS를 여러 번 수행하는 경우, 초기화를 절대 잊지 말자 !!

* P2206 - 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206

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

public class Main {
    public static int[][] board; public static int[][][] dist;
    public static Queue<Pair> q = new LinkedList<>();
    public static Pair cur;
    public static int[] dx = {1,-1,0,0};
    public static int[] dy = {0,0,-1,1};
    public static int n; public static int m;
    public static int result;

    public static void BFS() {
        while(!q.isEmpty()) {
            cur = q.poll();
            for(int dir=0;dir<4;dir++) {
                int nx = cur.x+dx[dir];
                int ny = cur.y+dy[dir];
                if(nx<0 || nx>=n || ny <0 || ny>=m) {continue;} //board 벗어나면
                if(nx==(n-1) && ny==(m-1)) {result = Math.min(result,dist[cur.x][cur.y][cur.cnt]+1); break;} //목적지에 도착하면
                if(dist[nx][ny][cur.cnt]!=0) {continue;} //이미 방문한 데면
                //1이고 아직 안 부셨다면
                if(board[nx][ny]==1 && cur.cnt==0) {
                    q.offer(new Pair(nx,ny,1));
                    dist[nx][ny][1] = dist[cur.x][cur.y][cur.cnt]+1;
                    continue;
                }
                if(board[nx][ny]==1 && cur.cnt!=0) {continue;}
                dist[nx][ny][cur.cnt] = dist[cur.x][cur.y][cur.cnt]+1;
                q.offer(new Pair(nx, ny,cur.cnt));
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());
        result = n*m+1;
        board = new int[n][m]; dist = new int[n][m][2];
        for(int i=0;i<n;i++) {
            String str = br.readLine();
            for(int j=0;j<m;j++) {
                board[i][j]=str.charAt(j)-'0';
            }
        }
        if(n==1 && m==1) {result=1;} //출발지 = 도착지인 경우
        else {
            q.offer(new Pair(0, 0,0)); dist[0][0][0] = 1;
            BFS();
        }
        if(result==(n*m+1)) {System.out.println("-1");}
        else {System.out.println(result);}
    }
    public static class Pair {
        int x; int y; int cnt;
        public Pair(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}

* P2573 - 빙산

https://www.acmicpc.net/problem/2573

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

public class P2573 {
    public static int[][] board, visited, ex_board;
    public static int n, m, nx, ny;
    public static int result=0;
    public static Queue<Pair> q = new LinkedList<>();
    public static Queue<Pair> q_ice = new LinkedList<>();
    public static int size; public static Pair cur;
    public static int cnt=0;
    public static int[] dx = {1,-1,0,0};
    public static int[] dy = {0,0,-1,1};

    public static void after() {
        // 1. 1년후 상태 만들기
        // 2. 덩어리 수 체크하기 : 개수만큼 cnt++
        // 3. cnt>1이면 성공 / q_ice가 비면 불가능
        // n, m < 300 : 배열크기 90000  / 빙하는 10000 이하 : 물이 80000 -> 빙하인 곳을 저장하자

        // 1. 1년후 상태 만들기
        //문제1. 같은 턴에 0이 돼버린 부분이 이웃한 빙산에 영향을 줌 : 1,1 -> 1,2
        size=0;
        while(size++<q_ice.size()) {
            cur = q_ice.poll();
            visited[cur.x][cur.y]=0;
            for(int dir=0;dir<4;dir++) {
                nx = cur.x+dx[dir];
                ny = cur.y+dy[dir];
                if(nx<0 || nx>=n || ny<0 || ny>=m) {continue;}
                //바다 만난만큼 감소
                if(ex_board[nx][ny]==0) {
                    if(board[cur.x][cur.y]>0) {board[cur.x][cur.y]-=1;}
                }
            }
            q_ice.offer(cur);
        }

        //복사
        for(int i=0;i< (size-1);i++) {
            cur = q_ice.poll();
            ex_board[cur.x][cur.y] = board[cur.x][cur.y];
            if(board[cur.x][cur.y]!=0) { q_ice.offer(cur); }
        }
    }

    // 2. 덩어리 수 체크하기
    public static void BFS() {
        cnt=0;
        size = q_ice.size();
        while(size-->0) {
            int breadth=0;
            cur = q_ice.poll();
            q.offer(cur); q_ice.offer(cur);
            while (true) {
                cur = q.poll();
                if(visited[cur.x][cur.y]!=1) {breadth++;}
                for (int dir = 0; dir < 4; dir++) {
                    nx = cur.x + dx[dir];
                    ny = cur.y + dy[dir];
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) {continue;}
                    if (visited[nx][ny] == 1 || board[nx][ny] == 0) {continue;}
                    visited[nx][ny]=1;
                    q.offer(new Pair(nx,ny));
                }
                //문제2. 끊어져서 q가 비었을때만 카운트 되는게 아니라 일단 q_ice의 모든 점을 조사하기 때문에 q_ice의 크기만큼 cnt++돼버림
                if(q.isEmpty()) {
                    if(breadth!=0) {cnt++;}
                    break;
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        int years=0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());
        board = new int[n][m]; visited = new int[n][m]; ex_board =  new int[n][m];
        for(int i=0;i<n;i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<m;j++) {
                board[i][j]=Integer.parseInt(st.nextToken());
                ex_board[i][j] = board[i][j];
                if(board[i][j]!=0) {q_ice.offer(new Pair(i,j));}
            }
        }
        while(true) {
            after(); years++;
            BFS();
            // 성공시
            if(cnt>1) { System.out.println(years); break; }
            // -> 전부 다 녹아버리면
            if(q_ice.isEmpty()) { System.out.println(0); break; }
        }
    }

    static class Pair {
        int x; int y;
        public Pair(int x, int y) {this.x = x;this.y = y;}
    }
}

1. board 상황대로 빙산 녹이기 (1년후 상황 만들기)
2. 빙산 개수 세기 -> 전역변수 cnt 갱신
3. cnt>1 : 성공 / q_ice.isEmpty : 빙산이 전부 녹으면 끝

   • q_ice : 빙산이 있는 곳의 위치를 저장한 큐

• board : 빙산 상황 저장하느 보드
• ex_board : after()를 실행한 당시의 board를 기록
• visited : 빙산 개수세기에서 사용하는 방문여부를 기록하는 배열

• board 상황대로 빙산 녹이기 (1년후 상황 만들기)

1. cur = q_ice.poll : 빙산위치에 대해서 전부 수행 1-1. 이 과정에서 q_ice의 요소를 전부 순회하므로, 다음에 빙산개수 판별에서 사용할 방문여부배열 visited를 0으로 초기화 함
2. ex_board 기준으로 주변에 사방에 있는 0개수 판별
3. 실제 감소는 board에 수행
4. 판별, 감소 끝냈으면 q_ice에 cur 다시 집어넣기
5. board -> ex_board 복사 5-1. 이 과정에서 0이 돼버린 전 빙산의 위치는 q_ice에서 빼버림

• 빙산 개수 세기

1. 끊어짐의 여부를 판단하는데 q.isEmpty를 활용하고 싶으므로 개수 탐색에 큐를 한 개 더 사용
2. 이번 탐색에 방문여부를 표시하는 visited, 바다여부를 판단해서 q에 넣음
3. q가 비었고 && 너비가 있는(즉 이미 셌던 빙하가 아닌) 경우에 cnt++

• 녹이기 -> 개수세기 -> 결과판단

1. cnt가 1이상이 되면 끊어졌다는 의미이
2. 빙산이었던 자리가 다 녹아버리면 q_ice에서 빼버리므로 q_ice가 비면 전부 녹았다는 의미이므로 0 출력하고 끝

개수세기에서 보드 전체를 순회하고 싶지 않았고, 그래서 q_ice에 있는 요소들만 순회하고 싶어서 큐를 두 개 사용하다보니 이런 저런 오류가 생겨서 너비를 재는 변수도 쓰고 ex_board도 쓰고 .... 어찌저찌 풀긴 했는데 뭔가 굉장히 누덕누덕한 코드가 돼버렸다 ^-^..

- 반례

1. 9 8 0 0 0 0 0 0 0 0 0 7 9 3 6 4 6 0 0 1 7 2 5 2 2 0 0 9 7 2 2 2 4 0 0 5 4 6 4 6 4 0 0 1 4 5 7 7 4 0 0 9 9 7 6 9 4 0 0 9 2 5 3 8 9 0 0 0 0 0 0 0 0 0 https://www.acmicpc.net/board/view/134531

• 시도마다 q_ice의 사이즈가 줄어서 ex_board를 갱신하는데 오류가 생겼음
• ex_board를 갱신할 때 q_ice.size()를 직접 쓰는게 아니라, size를 미리 저장한 변수를 사용해서 해결

2. 5 5 0 0 0 0 0 0 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 0 0

• 50몇프로 언저리에서 NullPointerException이 발생했을 때 테스트 해봄
• 첫 시도에 전부 녹아서 q_ice가 비어버릴 때 오류가 발생했음

- 다시 생각해본 점

• 반복문으로 큐를 순회할때 q.size()를 변수로 쓰지말자
• 당연히 조건문에 따라 poll, offer를 하면 개수가 달라지므로 의도했던 것과 다른 작동이 일어날 수 있는데, 자꾸 간과하게 된다

* P2146 - 다리 만들기

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

public class p2146 {
    //1. map을 섬의 번호로 초기화한다
    //2. 거리 재는 BFS 하다가 다른 섬으로 도착하면 기록 -> 최소값 갱신
    static int n;
    static int result;
    static int[][] map, visited;
    static Queue<Pair> q = new LinkedList<>();
    static Pair cur;
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,-1,1};

    static void BFS_cnt(int k) {
        while(!q.isEmpty()) {
            cur = q.poll();
            for(int dir=0;dir<4;dir++) {
                int nx = cur.x+dx[dir];
                int ny = cur.y+dy[dir];
                if(nx<0 || nx>=n || ny<0 || ny>=n) {continue;}
                if(visited[nx][ny]==1 || map[nx][ny]==0) {continue;}
                visited[nx][ny]=1; map[nx][ny]=k;
                q.offer(new Pair(nx,ny));
            }
        }
    }

    static void BFS(int k) {
        while(!q.isEmpty()) {
            int cnt=0;
            cur = q.poll();
            //현재 최소거리보다 길어지면 어차피 탐색할 필요 X
            if(cnt>visited[cur.x][cur.y]) {break;}
            for(int dir=0;dir<4;dir++) {
                int nx = cur.x+dx[dir];
                int ny = cur.y+dy[dir];
                if(nx<0 || nx>=n || ny<0 || ny>=n) {continue;}
                if(visited[nx][ny]!=0 || map[nx][ny]==k) {continue;}
                //다른 섬 만남
                if(map[nx][ny]!=k && map[nx][ny]!=0) {result = Math.min(result,visited[cur.x][cur.y]);}
                visited[nx][ny]=visited[cur.x][cur.y]+1;
                q.offer(new Pair(nx,ny));
            }
        }
        visited = new int[n][n];
    }

    static void clear() {
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                visited[i][j]=0;
            }
        }
    }
    public static void main(String[] args) throws IOException {
        int k=1;
        StringTokenizer st;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n]; visited = new int[n][n];
        result=n*n;
        for(int i=0;i<n;i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<n;j++) {
                map[i][j]=Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if(map[i][j]==1 && visited[i][j]==0) {
                    q.offer(new Pair(i,j));
                    visited[i][j]=1;
                    map[i][j]=k;
                    BFS_cnt(k);
                    k++;
                }
            }
        }
        clear();
        //visited를 매 번 초기화해서 재사용?????
        for(int i=0;i<n;i++) {
            for(int j=0;j<n;j++) {
                if(map[i][j]!=0 && visited[i][j]==0) {
                    q.offer(new Pair(i,j));
                    BFS(map[i][j]);
                }
            }
        }
        System.out.println(result);
    }

    static class Pair {
        int x; int y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

1. BFS로 섬마다 번호 붙이기 : BFS_cnt
2. 각 점에서 BFS로 다른 섬까지의 최소거리 구하기

* P13549 - 숨바꼭질3

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

public class Main {
    static int n, m, cur, next;
    static int[] distance = new int[100001];
    static Queue<Integer> q = new LinkedList<>();
    static int[] dir = new int[3];
    static boolean end = false;
    static void BFS() {
        while(!end) {
            cur = q.poll();
            if(cur==m) {
                System.out.println(distance[cur]-1);
                end = true;
                break;}
            dir[0] = cur;
            for (int d = 0; d < 3; d++) {
                next = cur + dir[d];

                if(next>=100001 || next<0) {continue;}
                if(distance[next]!=0) {continue;}
                if(d!=0) {
                    q.offer(next);
                    distance[next] = distance[cur]+1;
                }
                else {
                    q.offer(next);
                    q.offer(cur);
                    distance[next] = distance[cur];
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        dir[1]=-1; dir[2] = 1;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken());
        if(n==m) {
            System.out.println(0);
        } else {
            q.offer(n); distance[n] = 1;
            BFS();
        }
    }
}

• 탐색순서 : 비용이 없는 *2를 가장 먼저 탐색하고, 더 작아지는 선택지인 -1, 그 다음에 +1을 탐색한다

반례

- 44%

https://www.acmicpc.net/board/view/83938

0-1bfs

* P1600 - 말이 되고픈 원숭이

ㅜㅜ

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

public class P1600 {
    static int w, h, k, nx, ny;
    static int[][] board; static int[][][] distance;
    static Pair cur;
    static int result;
    static Queue<Pair> q = new LinkedList<>();
    static int[] dx = {1,-1,0,0};
    static int[] dy = {0,0,-1,1};
    static int[] hx = {2,1,-2,-1,2,1,-2,-1};
    static int[] hy = {1,2,1,2,-1,-2,-1,-2};

    static int BFS() {
        result = w*h;
        if(w==1 && h==1) {
            result=0;
            return -1;
        }
        while(!q.isEmpty()) {
            cur = q.poll();
            if(cur.x==(h-1)&&cur.y==(w-1)) { result = distance[cur.x][cur.y][cur.cnt]; return -1; }

            for(int dir=0;dir<4;dir++) {
                nx = cur.x+dx[dir];
                ny = cur.y+dy[dir];

                if(nx<0 || nx>=h || ny<0 || ny>=w) {continue;}
                if(board[nx][ny]==1) {continue;}
                if(distance[nx][ny][cur.cnt]!=0) {continue;}

                q.offer(new Pair(nx,ny, cur.cnt));
                distance[nx][ny][cur.cnt] = distance[cur.x][cur.y][cur.cnt]+1;
            }
            if(cur.cnt<k) {
                for (int dir = 0; dir < 8; dir++) {
                    nx = cur.x + hx[dir];
                    ny = cur.y+hy[dir];

                    if(nx<0 || nx>=h || ny<0 || ny>=w) {continue;}
                    if(board[nx][ny]==1) {continue;}
                    //메모리 초과 풀이
                    //if(distance[nx][ny][cur.cnt]!=0) {continue;}
                    if(distance[nx][ny][cur.cnt+1]!=0) {continue;}

                    q.offer(new Pair(nx,ny,cur.cnt+1));
                    distance[nx][ny][cur.cnt+1]=distance[cur.x][cur.y][cur.cnt]+1;
                }

            }
        }
        if(result==w*h) result=-1;
        return -1;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        k = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        w = Integer.parseInt(st.nextToken()); h = Integer.parseInt(st.nextToken());
        board = new int[h][w]; distance = new int[h][w][k+1];
        for (int i=0;i<h;i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<w;j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        q.offer(new Pair(0,0,0));
        BFS();
        System.out.println(result);
    }

    static class Pair {
        int x, y, cnt;
        public Pair(int x, int y, int cnt) { this.x = x; this.y = y; this.cnt = cnt; }
        public Pair(int x, int y) { this.x = x; this.y = y; }
    }
}

나중에 BFS에 대한 모든걸 잊는다면 이걸 다시 풀어보면 될 것 같다 특정 조건에 따라 탐색하는 경로가 달라지는 조건이 걸린 문제다 ( 정해진 횟수 만큼만 나이트 이동을 할 수 있음 ) 따라서 x, y, 현재나이트이동횟수를 함께 기록하는 3차원 배열을 사용해야 한다 (무조건 visited 되었다고 방문할 수 없는 것이 아니라, 나이트이동횟수에 따라 경로가 달라지기 때문)

• 메모리초과 자꾸 메모리 초과가 떠서 3차원 배열이 문젠가..? 라는 허튼 의심을 했지만, 어딘가 잘못된 조건문을 써서 잘못된 탐색, 순회의 결과로 발생하는 것일 가능성이 높다....
• 내가 틀렸던 부분

                    //메모리 초과 풀이
                    //if(distance[nx][ny][cur.cnt]!=0) {continue;}
                    if(distance[nx][ny][cur.cnt+1]!=0) {continue;}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Deque<Integer> d = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            switch (st.nextToken()) {
                case "push_back" :
                    d.offerLast(Integer.parseInt(st.nextToken()));
                    break;
                case "push_front" :
                    d.offerFirst(Integer.parseInt(st.nextToken()));
                    break;
                case "pop_back" :
                    if(!d.isEmpty()) {sb.append(d.pollLast()).append('\n');}
                    else {sb.append("-1").append('\n');}
                    break;
                case "pop_front" :
                    if(!d.isEmpty()) {sb.append(d.pollFirst()).append('\n');}
                    else {sb.append("-1").append('\n');}
                    break;
                case "size" :
                    sb.append(d.size()).append('\n');
                    break;
                case "empty" :
                    if(d.isEmpty()) {sb.append("1").append('\n');}
                    else {sb.append("0").append('\n');}
                    break;
                case "front" :
                    if(!d.isEmpty()) {sb.append(d.peekFirst()).append('\n');}
                    else {sb.append("-1").append('\n');}
                    break;
                case "back" :
                    if(!d.isEmpty()) {sb.append(d.peekLast()).append('\n');}
                    else {sb.append("-1").append('\n');}
                    break;
            }
        }
        System.out.println(sb);
    }
}

* P1021 - 회전하는 큐

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        int cnt=0; int[] list = new int[50];
        int tmpcnt=0; boolean success = false;
        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());

        st = new StringTokenizer(br.readLine()," ");
        for(int i=0;i<k;i++) {list[i]=Integer.parseInt(st.nextToken());}
        Deque<Integer> d = new LinkedList<>();
        for(int i=1;i<=n;i++) {d.offerLast(i);}

        for(int i=0;i<k;i++) {
            success=false; tmpcnt=0;
            int target = list[i];
            while(true) {
                if(target==d.peekFirst()) { //1번연산
                    d.pollFirst();
                    break;
                } else {
                    for(int j=0;j<(d.size()/2+1);j++) { //덱 사이즈 반쪽만큼 왼쪽 츄라이츄라이
                        if(target!=d.peekFirst()) {d.offerLast(d.pollFirst()); tmpcnt++;}
                        else {success=true; cnt+=tmpcnt; break;}
                    }
                    if(!success) { //왼쪽 아니면
                        for(int j=0;j<tmpcnt;j++) {d.offerFirst(d.pollLast());} //원상복구
                        tmpcnt=0;
                        for(int j=0;j<(d.size()/2+1);j++) { //오른쪽으로
                            if(target!=d.peekFirst()) {d.offerFirst(d.pollLast()); tmpcnt++;}
                            else {cnt+=tmpcnt; break;}
                        }
                    }
                }
            }
        }
        System.out.println(cnt);
    }
}

* P5430 - AC

• 시간초과 / 반례 / 정답
• 많이 틀릴 수록 더 얻어가는 부분이 많은 것 같다 ^-^

* 시간초과 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        boolean success = true; boolean isReversed = false;
        int n = Integer.parseInt(br.readLine());
        Deque<Integer> d = new LinkedList<>();
        Deque<Integer> temp = new LinkedList<>();
        for(int i=0;i<n;i++) { //n=100
            success=true; boolean isTemp = false;
            String func = br.readLine();
            int m = Integer.parseInt(br.readLine());
            String inStr = br.readLine();
            String[] inStrArr = inStr.substring(1,inStr.length()-1).split(",");
            d.clear(); temp.clear();
            for(int j=0;j<m;j++) {d.offerLast(Integer.parseInt(inStrArr[j]));}
            //func
            for(int j=0;j<func.length();j++) {
                if(func.charAt(j)=='D') {
                    if(isReversed) {
                        if(isTemp) {
                            int size = temp.size();
                            for(int k=0;k<size;k++) {d.offerLast(temp.pollLast());} //배열개수 < 100000
                            isTemp = false;
                        } else {
                            int size = d.size();
                            for(int k=0;k<size;k++) {temp.offerLast(d.pollLast());}
                            isTemp = true;
                        }
                        if(isTemp) {
                            if(!temp.isEmpty()) {temp.pollFirst();}
                            else {success = false; sb.append("error").append('\n'); break;}
                        } else {
                            if(!d.isEmpty()) {d.pollFirst();}
                            else {success = false; sb.append("error").append('\n'); break;}
                        }
                        isReversed=false;
                    } else { 
                        if(isTemp) { 
                            if(!temp.isEmpty()) {temp.pollFirst();}
                            else {success = false; sb.append("error").append('\n'); break;}
                        } else {
                            if(!d.isEmpty()) {d.pollFirst();}
                            else {success = false; sb.append("error").append('\n'); break;}
                        }
                    }
                } else { // R
                    if(isReversed) {isReversed=false;}
                    else {isReversed=true;}
                }
            }
            if(success) {
                sb.append("[");
                if(isTemp) {
                    int size = temp.size();
                    for (int j = 0; j < size; j++) {sb.append(temp.pollFirst()).append(",");}
                } else {
                    int size = d.size();
                    for (int j = 0; j < size; j++) {sb.append(d.pollFirst()).append(",");}
                }
                sb.deleteCharAt(sb.length()-1);
                sb.append("]").append('\n');
            }
        }
        System.out.println(sb);
    }
}

아무리 생각해도 "테스트케이스만큼 반복 > 함수개수만큼 반복 > 배열뒤집기" 를 수행하면 O(n^3)를 벗어날 수가 없지않나..? 그래도 일단 최대한 줄일 수 있는 부분은 줄여보면서 뒤집어 보려고 했다

• 사용한 방법

1. 뒤집기 : d, temp로 덱 두 개를 사용하여 뒤집기 구현
   • 두 번 옮겨담아서 뒤집는 거 보다는 단축된다고 생각했다
2. isReversed 사용 : 매 번 뒤집는 것이 아니라, R이 홀수번 나왔을 때만 뒤집기 - D를 만났을 때 isReversed 여부를 따져서 뒤집고 잘랐다.
   • 시간초과에 신경이 쏠려서 지금 알았는데 D를 만났을 때만 뒤집고, 실제로 출력할 때는 isReversed 여부를 따지지 않았다. 시간초과가 안 났어도 틀린 풀이였다 ^-^..
   • 정답풀이에서 10% 부족한 생각이었다. 결국 실제로 뒤집기를 실행하는 순간 시간초과가 나므로 여기서 쪼끔만 더 생각해봤으면 됐을텐데..!!!

*P5430 - 정답풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        boolean success = true; boolean isReversed = false;
        int n = Integer.parseInt(br.readLine());
        Deque<Integer> d = new LinkedList<>();
        for(int i=0;i<n;i++) {
            success=true; isReversed=false;
            String func = br.readLine();
            int m = Integer.parseInt(br.readLine());
            String inStr = br.readLine();
            String[] inStrArr = inStr.substring(1,inStr.length()-1).split(",");
            for(int j=0;j<m;j++) { d.offerLast(Integer.parseInt(inStrArr[j])); }
            //func
            for(int j=0;j<func.length();j++) {
                if(func.charAt(j)=='D') {
                    if(d.isEmpty()) {
                        success = false;
                        sb.append("error").append('\n');
                        break;
                    }
                    if (isReversed) { d.pollLast(); } //뒤집힌 상황이면 : R이 홀수번 나왔다면
                    else { d.pollFirst(); }  //안 뒤집힌 상황이면 : R이 짝수번 나왔다면
                } else { // R
                    if(isReversed) { isReversed=false; }
                    else { isReversed=true; }
                }
            }
            if(success) {
                sb.append("[");
                int size = d.size();
                if(isReversed) {
                    for (int j = 0; j < size; j++) { sb.append(d.pollLast()).append(","); }
                } else {
                    for (int j = 0; j < size; j++) { sb.append(d.pollFirst()).append(","); }
                }
                if(sb.charAt(sb.length()-1)!='['){ sb.deleteCharAt(sb.length()-1); }
                sb.append("]").append('\n');
            }
        }
        System.out.println(sb);
    }
}

• 실제로 뒤집지 않고 R이 홀수번 나왔다면 (isReversed == true)
  • offerFirst → pollLast
  • 넣은 방향과 반대로 출력한다
  • 넣은 방향과 반대에서 자른다

- 알게된점

• 배열을 뒤집는 연산이 필요한 경우 : 실제로 뒤집는 것보다, 앞 뒤로 모두 접근이 가능한 덱을 활용하자

* 틀린풀이 - 반례

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        boolean success = true; boolean isReversed = false;
        int n = Integer.parseInt(br.readLine());
        Deque<Integer> d = new LinkedList<>();
        for(int i=0;i<n;i++) {
            success=true; isReversed=false;
            String func = br.readLine();
            int m = Integer.parseInt(br.readLine());
            String inStr = br.readLine();
            String[] inStrArr = inStr.substring(1,inStr.length()-1).split(",");
            for(int j=0;j<m;j++) { d.offerLast(Integer.parseInt(inStrArr[j])); }
            //func
            for(int j=0;j<func.length();j++) {
                if(func.charAt(j)=='D') {
                    if(d.isEmpty()) {
                        success = false;
                        sb.append("error").append('\n');
                        break;
                    }
                    if (isReversed) { d.pollLast(); } //뒤집힌 상황이면 : R이 홀수번 나왔다면
                    else { d.pollFirst(); }  //안 뒤집힌 상황이면 : R이 짝수번 나왔다면
                } else { // R
                    if(isReversed) { isReversed=false; }
                    else { isReversed=true; }
                }
            }
            if(success) {
                sb.append("[");
                int size = d.size();
                if(isReversed) {
                    for (int j = 0; j < size; j++) { sb.append(d.pollLast()).append(","); }
                } else {
                    for (int j = 0; j < size; j++) { sb.append(d.pollFirst()).append(","); }
                }
                sb.deleteCharAt(sb.length()-1);
                sb.append("]").append('\n');
            }
        }
        System.out.println(sb);
    }
}

• 반례 : 0 [] 을 넣는 경우

• 자꾸 16%에서 틀려서 오답처리가 됐다.
• sb.deleteCharAt(sb.length()-1); : 이 부분에서 []인 경우에 sb.length()-1인 '['을 삭제해버려서 ]만 출력되었다. → 이 반례에 대한 조건을 걸어서 해결했지만, 좀 더 쌈뽕한 풀이가 있지 않을까 싶다..

* P10845 - 큐

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Queue<Integer> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        int rear=0;
        for(int i=0;i<n;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            switch (st.nextToken()) {
                case "push" :
                    rear = Integer.parseInt(st.nextToken());
                    q.offer(rear);
                    break;
                case "pop" :
                    if(!q.isEmpty()) {sb.append(q.poll()).append('\n');}
                    else{sb.append(-1).append('\n');}
                    break;
                case "size" :
                    sb.append(q.size()).append('\n');
                    break;
                case "empty" :
                    if(q.isEmpty()) {sb.append(1).append('\n');}
                    else {sb.append(0).append('\n');}
                    break;
                case "front" :
                    if(q.isEmpty()) {sb.append(-1).append('\n');}
                    else {sb.append(q.peek()).append('\n');}
                    break;
                case "back" :
                    if(q.isEmpty()) {sb.append(-1).append('\n');}
                    else {sb.append(rear).append('\n');}
                    break;
            }
        }
        System.out.println(sb);
    }
}

* P2161 - 카드1

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 IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); int l=0;
        Queue<Integer> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=n;i++) {q.offer(i);}
        while(true) {
            if(q.size()==1) { l=q.poll(); break;}
            sb.append(q.poll()).append(' ');
            q.offer(q.poll());
        }
        sb.append(l);
        System.out.println(sb);
    }
}

• head에서 카드를 뽑아 tail에 삽입 : FIFO : push와 pop을 다른 곳에서 : queue 사용

* P11866 - 요세푸스 문제 0

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder().append("<");
        Queue<Integer> q = new LinkedList<>();
        int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken());
        for(int i=1;i<=n;i++) {q.offer(i);}
        while(true) {
            if(q.isEmpty()) {sb.append(">"); break;}
            for(int i=1;;i++) {
                if(i%k==0) { sb.append(q.poll()); break;}
                else { q.offer(q.poll()); }
            }
            if(!q.isEmpty()) {sb.append(", ");}
        }
        System.out.println(sb);
    }
}

• 요세푸스문제 : 연결리스트 or 큐로 풀이 가능

• 연결리스트 : 직접 k만큼 next로 탐색하며 삭제
• 큐 : queue.push(queue.pop()) : tail에서 pop한 걸 그대로 head에 push하면 순서는 그대로 유지하며 탐색 가능 : %k == 0 : 매 k번째마다 pop : queue가 빌 때까지 반복

* P2164 - 카드2

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 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;i++) {  q.offer(i);   }
        while(true) {
            if(q.size()==1) {break;}
            q.poll();
            q.offer(q.poll());
        }
        System.out.println(q.poll());
    }
}

* P15828 - 라우터

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 IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        Queue<Integer> q = new LinkedList<>();
        while(true) {
            int t = Integer.parseInt(br.readLine());
            if(t ==-1) {break;}

            if(t==0) {q.poll();}
            else if(q.size()<n) {q.offer(t);}
        }
        if(q.size()==0) {sb.append("empty");}
        while(!q.isEmpty()) {sb.append(q.poll()).append(" ");}
        System.out.println(sb);
    }
}

\ 버퍼 **** : "입력한 순서대로" 처리한다 => 큐 사용

• 큐의 길이와 버퍼크기 비교하여 -> 넘치지 않으면 push
• 0이 나오면 pop

• 자바의 스택클래스 사용에 관하여 읽어볼만한 글들 https://velog.io/@jhl221123/%EC%9E%90%EB%B0%94%EC%9D%98-Stack%EC%9D%80-%EC%99%9C-%EC%82%AC%EC%9A%A9%ED%95%98%EC%A7%80-%EC%95%8A%EB%8A%94-%EA%B1%B8%EA%B9%8C https://tecoble.techcourse.co.kr/post/2021-05-10-stack-vs-deque/ https://aahc.tistory.com/8

* P10828 - 스택

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

public class P10828 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] stack = new int[10000];
        int c=0;
        int cnt=0;
        while(n-->0) {
            String inStr = br.readLine();
            if(inStr.charAt(1)=='u') {
                StringTokenizer st = new StringTokenizer(inStr," ");
                inStr = st.nextToken();
                c =  Integer.parseInt(st.nextToken());
            }
            if(inStr.equals("push")) {
                stack[cnt++]=c;
            } else if(inStr.equals("pop")) {
                if(cnt==0) {System.out.println(-1); continue;}
                System.out.println(stack[--cnt]);
            } else if(inStr.equals("size")) {
                System.out.println(cnt);
            } else if(inStr.equals("empty")) {
                if(cnt==0) {System.out.println(1);}
                else {{System.out.println(0);}}
            } else if(inStr.equals("top")) {
                if(cnt==0) {System.out.println(-1); continue;}
                System.out.println(stack[cnt-1]);
            }
        }
    }
}

* 10773 - 제로

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.Stack;

public class P10773 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        int result=0;
        for(int i=0;i<n;i++) {
            int k = Integer.parseInt(br.readLine());
            if(k==0) {stack.pop(); continue;}
            stack.add(k);
        }
        Iterator<Integer> iter = stack.iterator();
        while(iter.hasNext()) {result+= iter.next();}
        System.out.print(result);
    }
}

입력받은 수 stack에 push 0 나오면 직전에 받았던 숫자 pop : Last In을 빼야하는 문제이므로 stack 활용

* P1874 - 스택 수열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class P1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        int in =1; int result=0;
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<n;i++) {
            int k = Integer.parseInt(br.readLine());
            if(stack.empty()) {
                while(in<=k) {stack.add(in++); sb.append('+');}
                stack.pop(); sb.append('-');
                continue;
            }
            if(k>stack.peek()) {
                while(k>stack.peek()){stack.add(in++); sb.append('+');}
                stack.pop(); sb.append('-');
            } else if(k<stack.peek()) {
                result=1;
                break;
            } else {
                stack.pop(); sb.append('-');
            }
        }
        if(result==1) {
            System.out.println("NO");
        } else {
            for(int i=0;i<sb.length();i++) {
                System.out.println(sb.charAt(i));
            }
        }
    }
}

*1. *반드시 오름차순으로 정수를 push하므로, 요구받은 수열이 스택의 최상단보다 작으면 불가능한 수열로 판단함

*2. *요구받은 수열이 스택의 최상단보다 크면 해당 수열까지 push한 후 pop

* P9012 - 괄호

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class P9012 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<n;i++) {
            String result="YES";
            String str = br.readLine();
            for(int j=0;j<str.length();j++) {
                if(str.charAt(j)=='(') {stack.add('(');}
                else {
                    if(stack.empty()) {result="NO"; continue;}
                    stack.pop();
                }
            }
            if(!stack.empty()) {result="NO";}
            System.out.println(result);
            stack.clear();
        }
    }
}

• ( 는 무조건 push

• )는 pop

• )를 만났을때 스택이 비어있다면 or 전부 수행한 후에 스택이 비어있지 않으면 : not valid

* P17413 - 단어 뒤집기2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class P17413 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        StringBuilder sb = new StringBuilder();
        int in =0;
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<str.length();i++) {
            switch (str.charAt(i)) {
                case '<' :
                    while(!stack.empty()) {sb.append(stack.pop());}
                    in=1;
                    sb.append('<');
                    break;
                case '>' :
                    in=0;
                    sb.append('>');
                    break;
                case ' ' :
                    while(!stack.empty()) {sb.append(stack.pop());}
                    sb.append(' ');
                    break;
                default :
                    if(in==1) {sb.append(str.charAt(i));}
                    else {stack.add(str.charAt(i));}
            }
        }
        if(!stack.empty()) {while(!stack.empty()) {sb.append(stack.pop());}}
        System.out.println(sb);
    }
}

• 단어뒤집기 : Last In First Out : 스택 사용
• 괄호 안의 문자 / 괄호 밖의 문자(뒤집어야 함)의 구분 : in 변수 (flag)

• 전체를 한 번에 뒤집는 것이 아닌, 괄호를 기점으로 뒤집어야 하므로 괄호를 만나면 스택 전부 비움

* P4949 - 균형잡힌 세상

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class P4949 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean pEnd = true;
        boolean result = true;
        Stack<Character> stack = new Stack<>();
        do {
            String str = br.readLine();
            if (str.equals(".")) { pEnd = false; break; }
            for (int i = 0; i < str.length(); i++) {
                if(str.charAt(i)=='.') { break; }
                switch (str.charAt(i)) {
                    case '(' :
                        stack.push('(');
                        break;
                    case ')' :
                        if (!stack.isEmpty()) {
                            if (stack.peek() == '(') { stack.pop(); break; }
                            else { result = false; break; }
                        } else {
                            result = false;
                            break;
                        }
                    case '[' :
                        stack.push('[');
                        break;
                    case ']' :
                        if (!stack.isEmpty()) {
                            if (stack.peek() == '[') { stack.pop(); break;}
                            else { result = false; break; }
                        } else {
                            result = false;
                            break;
                        }
                }
            }
            if (result && stack.isEmpty()) {
                System.out.println("yes");
            } else {
                System.out.println("no");
            }
            result = true; stack.clear();
        }
        while (pEnd); {}
    }
}

* 틀린풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        boolean pEnd = true;
        boolean result = true;
        Stack<Character> stack = new Stack<>();
        do {
            String str = br.readLine();
            if (str.equals(".")) { pEnd = false; }
            for (int i = 0; i < str.length(); i++) {
                switch (str.charAt(i)) {
                    case '.' :
                        break;
                    case '(' :
                        stack.push('(');
                        break;
                    case ')' :
                        if (!stack.isEmpty()) {
                            if (stack.peek() == '(') { stack.pop(); break; }
                            else { result = false; break; }
                        } else {
                            result = false;
                            break;
                        }
                    case '[' :
                        stack.push('[');
                        break;
                    case ']' :
                        if (!stack.isEmpty()) {
                            if (stack.peek() == '[') { stack.pop(); break;}
                            else { result = false; break; }
                        } else {
                            result = false;
                            break;
                        }
                }
            }
            if (result == true && pEnd==true) {
                System.out.println("yes");
            } else if(result==false && pEnd==true) {
                System.out.println("no");
            }
            result = true;
        }
        while (pEnd); {}
    }
}

배운점 : 스택, 큐를 사용할 땐 반드시 루프마다 clear() 해주는 것을 잊지말자 ^-^

* P3986 - 좋은 단어

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Stack<Character> stack = new Stack<>();
        int result =0;
        for(int i=0;i<n;i++) {
            String str = br.readLine();
            stack.push(str.charAt(0));
            for(int j=1;j<str.length();j++) {
                if(stack.isEmpty()) {
                    stack.push(str.charAt(j));
                } else {
                    if(stack.peek()==str.charAt(j)) {
                        stack.pop();
                    } else {
                        stack.push(str.charAt(j));
                    }
                }
            }
            if(stack.isEmpty()) {result++;}
            stack.clear();
        }
        System.out.println(result);
    }
}

직전에 나온 단어와 짝을 이루는지 확인하는 문제 : Last In First Out -> 스택을 활용

* P28278 - 스택2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        Stack<String> stack = new Stack<>();
        for(int i=0;i<n;i++) {
            String str = br.readLine();
            switch (str.charAt(0)) {
                case '1' :
                    stack.push(str.substring(2));
                    break;
                case '2' :
                    if(!stack.isEmpty()) {sb.append(stack.pop()+"\n");}
                    else {sb.append("-1"+'\n');}
                    break;
                case '3' :
                    sb.append(stack.size()+"\n");
                    break;
                case '4' :
                    if(stack.isEmpty()) {sb.append("1"+'\n');}
                    else {sb.append("0"+'\n');}
                    break;
                case '5' :
                    if(!stack.isEmpty()) {sb.append(stack.peek()+'\n');}
                    else {sb.append("-1"+'\n');}
                    break;
            }
        }
        System.out.println(sb);
    }
}

* P28278 - 시간초과풀이

그냥 주어진 연산을 수행하기만 하면 되는 정말 간단한 문제지만, 시간초과 문제를 마주쳤다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Stack<String> stack = new Stack<>();
        for(int i=0;i<n;i++) {
            String str = br.readLine();
            switch (str.charAt(0)) {
                case '1' :
                    stack.push(str.substring(2));
                    break;
                case '2' :
                    if(!stack.isEmpty()) {System.out.println(stack.pop());}
                    else {System.out.println(-1);}
                    break;
                case '3' :
                    System.out.println(stack.size());
                    break;
                case '4' :
                    if(stack.isEmpty()) {System.out.println(1);}
                    else {System.out.println(0);}
                    break;
                case '5' :
                    if(!stack.isEmpty()) {System.out.println(stack.peek());}
                    else {System.out.println(-1);}
                    break;
            }
        }
    }
}

• 알게된점

• System.out.println()으로 매 루프마다 데이터 출력을 진행하면 속도 현저히 느려진다
• StringBuilder : 내부 내용을 변경시킬 수 없는 String (불변)과 다르게 값을 변경해도 같은 주소공간을 참조하여, 값이 변경할 수 있는 가변성을 갖는다. → 매 번 출력하는 것보다 StringBuilder로 출력할 값들을 append하여 저장해두고, 마지막에 한 번에 출력하는 것이 시간을 줄일 수 있는 방법이다. 출력이 많은 문제에서는 매 번 System.out으로 출력하는 것을 지양할 것!!

* P25497 - 기술 연계마스터 임스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Stack<Character> stack = new Stack<>();
        int cnt =0; int in=0;
        String str = br.readLine();
        for(int i=0;i<n;i++) {
            if(str.charAt(i)-'0'>=1 && str.charAt(i)-'0'<=9) {
                cnt++;
            } else if(str.charAt(i)=='L') {
                stack.push('L');
            } else if(str.charAt(i)=='R') {
                in = stack.search('L');
                if(in!=-1) {
                    stack.remove(stack.size()-in);
                    cnt++;
                } else {
                    break;
                }
            } else if(str.charAt(i)=='S') {
                stack.push('S');
            } else if(str.charAt(i)=='K') {
                in = stack.search('S');
                if(in!=-1) {
                    stack.remove(stack.size()-in);
                    cnt++;
                } else {
                    break;
                }
            }
        }
        System.out.println(cnt);
    }
}

• stack - search() : 스택 내부에 해당 객체가 존재한다면, 위치를 반환한다 : 인덱스가 아닌 빠져나오는 순서, 즉 Last In이 0

• stakc - remove() : 인덱스로 접근하여 삭제한다. → stack.remove(stack.size()-stack.search())를 사용하여 연계기술 사용시 선행기술이 존재하는지 찾고, 존재하면 해당 인덱스로 remove()를 수행했다
• LIFO도 필요했고 + 인덱스로 접근하는 부분도 필요해서 저 메소드를 사용하긴 했지만, 스택을 사용하면서 LIFO를 어기는 메소드를 쓰는게 맞는지는 모르겠다. 무엇보다 인덱스로 접근하므로 O(n)인 점을 생각하면 시간복잡도 상으로도 바람직하지 못 한 것 같다.

• 관련하여 생각해볼만한 글 링크

  https://velog.io/@jhl221123/%EC%9E%90%EB%B0%94%EC%9D%98-Stack%EC%9D%80-%EC%99%9C-%EC%82%AC%EC%9A%A9%ED%95%98%EC%A7%80-%EC%95%8A%EB%8A%94-%EA%B1%B8%EA%B9%8C

* P5957 - Cleaning the Dishes

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Stack<Integer> stack = new Stack<>();
        for(int i=n;i>=1;i--) {stack.push(i);}

        Stack<Integer> dStack = new Stack<>();
        Stack<Integer> cStack = new Stack<>();
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            if(Integer.parseInt(st.nextToken())==1) {
                int d = Integer.parseInt(st.nextToken());
                for(int j=0;j<d;j++) {
                    if(!stack.isEmpty()) {
                        dStack.push(stack.pop());
                    }
                }
            } else {
                int d = Integer.parseInt(st.nextToken());
                for(int j=0;j<d;j++) {
                    if(!dStack.isEmpty()) {
                        cStack.push(dStack.pop());
                    }
                }
            }
            if(cStack.size()==n) {break;}
        }
        while(!cStack.isEmpty()) {
            System.out.println(cStack.pop());
        }
    }
}

* P1406 - 에디터

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

public class P1406 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        int n = Integer.parseInt(br.readLine());

        LinkedList<Character> list = new LinkedList();
        for (int i = 0; i < str.length(); i++) {list.add(str.charAt(i));}

        ListIterator<Character> iter = list.listIterator();
        while(iter.hasNext()) {iter.next();}


        for(int i=0;i<n;i++) {
            String[] command = br.readLine().split(" ");
            if (command[0].equals("P")) {
                char inChar = command[1].charAt(0);
                iter.add(inChar);
            }
            if (command[0].equals("L")) {
                if (iter.hasPrevious() == false) {continue;}
                iter.previous();
            }
            if (command[0].equals("D")) {
                if (iter.hasNext()==false) {continue;}
                iter.next();
            }
            if(command[0].equals("B")) {
                if (iter.hasPrevious() == false) {continue;}
                iter.previous(); iter.remove();
            }
        }
        StringBuilder sb = new StringBuilder();
        for(char c : list) {
            sb.append(c);
        }
        System.out.println(sb);
    }
}

** - Errors** #CocurrentModificationException Collection에 데이터수정메소드 (remove, add, ...)를 호출할 때마다 멤버변수 modCount 값이 증가하는 방식으로 기록함 → next()로 다음 요소를 순환할 때** expectedModCount**와 값을 비교하여 값이 같지 않을 경우 발생함 : 멀티쓰레드 환경에서 객체의 변경을 확인하고 막기 위함

해결방식

• ListIterator 사용 : List에 직접 add, remove를 사용하지 말고, ListIterator에 modify 메소드를 사용하자

* P5397 - 키로거

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

public class P5397 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] inStr = new String[n];
        LinkedList<Character> list = new LinkedList<>();

        for(int i=0;i<n;i++) {
            inStr[i] =  br.readLine();
            ListIterator iter = list.listIterator();
            for(int j=0;j<inStr[i].length();j++) {
                char c = inStr[i].charAt(j);
                switch(c) {
                    case '>' :
                        if(iter.hasNext()) {iter.next();}
                        break;
                    case '<' :
                        if(iter.hasPrevious()) {iter.previous();}
                        break;
                    case '-' :
                        if(iter.hasPrevious()) {iter.previous(); iter.remove();}
                        break;
                    default:
                        iter.add(c);
                }
            }
            StringBuilder sb = new StringBuilder();
            for(char c : list) {sb.append(c);}
            inStr[i] = sb.toString();
            list.clear();
        }
        for(String s : inStr) {
            System.out.println(s);
        }
    }
}

* 1158 - 요세푸스

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

public class P1158 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inStr = br.readLine().split(" ");
        int n = Integer.parseInt(inStr[0]); int k = Integer.parseInt(inStr[1]);
        int[] result = new int[n];
        LinkedList<Integer> list = new LinkedList<>();
        for(int i=0;i<n;i++) {
            list.add(i+1);
        }
        ListIterator<Integer> iter = list.listIterator();
        for(int i=0;i<n;i++) {
            for(int j=0;j<k;j++) {
                if(j==(k-1) && iter.hasNext()) {result[i]=iter.next(); break;}
                else if(j==(k-1) && !iter.hasNext()) {iter=list.listIterator(); result[i]=iter.next(); break;}
                if(iter.hasNext()) {iter.next();}
                else {iter=list.listIterator(); iter.next();}
            }
            iter.remove();
        }

        System.out.print("<");
        for(int i=0;i<n;i++) {
            System.out.print(result[i]);
            if(i!=(n-1)) {System.out.print(", ");}
        }
        System.out.print(">");
    }
}

풀이방식 : LinkedList - ListIterator로 주어진 횟수만큼 next()로 탐색, remove()로 삭제하는 방식 Queue로도 구현이 가능함, 비슷한 문제의 queue 풀이는 queue챕터에 올릴 예정