[알고리즘] 인덱스 회전(feat. 나머지 연산)

인덱스 회전

• 동, 서, 남, 북으로 순차적으로 회전하는 무언가가 있다고 가정할 때, 코드에서 이것을 표현하려면 아래와 같이 표현할 수 있다.

int direction = direction + 1;
if (direction == 4) {
    direction = 0; 
}

• 동서남북을 각각 0, 1, 2, 3이라고 하고 현재 방향에서 +1씩 더하면서 방향을 바꾸는 것이고 만약 북쪽에서 +1을 해서 direction = 4가 되면 동쪽인 0으로 강제로 바꾸어주는 것이다.

 

• 또 다른 방법으로는 나머지 연산을 이용하는 것이다.
• 작은 수를 큰 수로 나누게 되면 작은 수가 나머지가 되는 것을 이용하는 것이다.

int direction = (direction + 1) % 4;

• 동서남북의 범위에서는 direction + 1을 한 결과가 그대로 나오게 되고 direction이 동서남북 범위를 넘어가면 나머지가 0~3 범위에서 계산되어 나온다. 따라서 조건문을 따로 만들어서 강제로 바꾸어줄 필요가 없다!
  • 1 % 4 = 1
  • 2 % 4 = 2
  • 3 % 4 = 3
  • 4 % 4 = 0 (0번 인덱스로 회전)
  • 5 % 4 = 1
  • 6 % 4 = 2
  • 7 % 4 = 3
  • 8 % 4 = 0
• 만약 역방향 회전까지 고려를 해야 한다면,

if (정방향 회전일 경우) {
    direction = direction + 1;
    if (direction == 4) {
        direction = 0;
    }
} else {
    direction = direction - 1;
    if (direction == -1) {
        direciton = 4;
    }
}

• 나머지 연산을 사용하지 않는다면 이처럼 코드가 길어지지만

 

if (정방향 회전) {
    direction = (direction + 1) % 4;
} else
    direction = (4 + (direction - 1)) % 4; 

• 나머지 연산을 사용하면 보다 깔끔하게 적을 수 있다.
• 이 원리는 아스키 코드를 이용한 알고리즘 풀이에서도 사용이 된다.
• 예를 들어 abc 를 각각 3칸씩 밀어야 하는 경우가 있다면 각각의 아스키 코드 + 3을 해서 def 를 구할 수 있겠지만 xyz 를 3칸씩 밀어야 한다면 원하는 abc 라는 답을 얻을 수 없다.
• 물론 이 경우에도 조건문을 이용해 해결할 수 있지만 나머지 연산을 사용하고자 한다면 아래와 같이 할 수 있다!
• ch = 현재 알파벳, n = 이동 거리 라고 가정하고

(char) ('a' + (ch + n - 'a') % 26);

• 나머지 연산은 요소의 개수로 하면 된다. 동서남북일 때는 4이고 알파벳 같은 경우는 총 26개이므로 26으로 하는 것이다.
• 이것 또한 역방향 회전은 아래와 같이 표현할 수 있다!

(char) ('z' + (ch - n - 'z') % 26);

 

참고용 자바스크립트 코드

String.fromCharCode(122 + (ch - n - 122) % 26);

 

 

• [프로그래머스 레벨1] 시저 암호

GitHub - g4dalcom/dev_vault: What I learned / 공부한 것들을 기록합니다!